# Extreme direction Sperner for square 0-1 matrix

From Egres Open

Let *A* be an [math]n \times n[/math] 0-1 matrix, and suppose that the facets of the polyhedron [math]P=\{x: A x \leq {\mathbf 1},\ x \leq {\mathbf 1}\} [/math] are coloured by [math]n[/math] colours such that a facet with extreme direction [math]-e_i[/math] does not get colour [math]i[/math], and every colour appears twice. Can we find in polynomial time a vertex that is incident to facets of every colour (a *panchromatic vertex*)?

## Remarks

A panchromatic vertex exists by a polyhedral version of Sperner's Lemma ^{[1]}. It was shown by T. Király and J. Pap ^{[2]} that if we relax the condition that *A* is 0-1, or that *A* is square and every colour is used twice, then the problem becomes PPAD-complete.

## References

- ↑ T. Király, J. Pap,
*A note on kernels and Sperner's Lemma*, DOI link - ↑ T. Király, J. Pap,
*PPAD-completeness of polyhedral versions of Sperner's Lemma*, DOI link, EGRES Technical Report