A combinatorial proof of a theorem of Freund - École des Ponts ParisTech Access content directly
Journal Articles Journal of Combinatorial Theory, Series A Year : 2008

A combinatorial proof of a theorem of Freund


In 1989, Robert W. Freund published an article about generalizations of the Sperner lemma for triangulations of n-dimensional polytopes, when the vertices of the triangulations are labeled with points of Rn. For y ? Rn, the generalizations ensure, under various conditions, that there is at least one simplex containing y in the convex hull of its labels. Moreover, if y is generic, there is generally a parity assertion, which states that there is actually an odd number of such simplices. For one of these generalizations, contrary to the others, neither a combinatorial proof, nor the parity assertion were established. Freund asked whether a corresponding parity assertion could be true and proved combinatorially. The aim of this paper is to give a positive answer, using a technique which can be applied successfully to prove several results of this type in a very simple way. We prove actually a more general version of this theorem. This more general version was published by van der Laan, Talman and Yang in 2001, who proved it in a non-combinatorial way, without the parity assertion. © 2007 Elsevier Inc. All rights reserved.



Dates and versions

hal-00835237 , version 1 (18-06-2013)



Frédéric Meunier. A combinatorial proof of a theorem of Freund. Journal of Combinatorial Theory, Series A, 2008, 115 (2), pp.317-325. ⟨10.1016/j.jcta.2007.04.003⟩. ⟨hal-00835237⟩
65 View
0 Download



Gmail Facebook Twitter LinkedIn More