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
