### Recognizing Vertex

Posted:

**22 May 2011, 22:52**Dear Polymake people,

Can anybody say anything useful regarding the following question?

Let P be an integer polyhedron (in particular polytope) in R^n. So, all its vertices are integer points.

Asume also that we don’t know the facets of P and even the inequalities defining P explicitly; as is in the case when P is defined as the convex hull of some set of points.

Consider the problem: ‘Is a given integer point $t$ in P a vertex of P?’ (1)

(1) is equivalent to:

‘Is it true that $t$ is not a convex combination of any $k\geq 2$ points in P?’, (2)

which is hardly useful to solve (1).

(2) can be reformulated in the combinatorial language for $k=2$.

The question is:

Can you reformulate (2) in any fruitful way for $k=3,$ $k=4,$ … or in the general case?

I don’t think that using the hyperplanes separating $t$ from other points in P

or the facets passing through $t$ is a good idea. Is this right?

Any reference to a special polyhedron, for which this has been done would be favorably accepted.

Thank you,

Vladimir Shlyk

Can anybody say anything useful regarding the following question?

Let P be an integer polyhedron (in particular polytope) in R^n. So, all its vertices are integer points.

Asume also that we don’t know the facets of P and even the inequalities defining P explicitly; as is in the case when P is defined as the convex hull of some set of points.

Consider the problem: ‘Is a given integer point $t$ in P a vertex of P?’ (1)

(1) is equivalent to:

‘Is it true that $t$ is not a convex combination of any $k\geq 2$ points in P?’, (2)

which is hardly useful to solve (1).

(2) can be reformulated in the combinatorial language for $k=2$.

The question is:

Can you reformulate (2) in any fruitful way for $k=3,$ $k=4,$ … or in the general case?

I don’t think that using the hyperplanes separating $t$ from other points in P

or the facets passing through $t$ is a good idea. Is this right?

Any reference to a special polyhedron, for which this has been done would be favorably accepted.

Thank you,

Vladimir Shlyk