Some Recent Combinatorial Applications of Borsuk-Type Theorems
Noga Alon · Cambridge University Press eBooks · 1988
INTRODUCTION The well known theorem of Borsuk [Bo] is the following. Theorem 1.1 (Borsuk) For every continuous mapping f : S n → R n , there is a point x ϵ S n such that f (x) = f (−x) . In particular, if f is antipodal (i.e. f(x) = −f(−x) for all x ϵ S n ) then there is a point of S n which maps into the origin. This theorem and its many generalizations have numerous applications in various branches of mathematics, including Topology, Functional Analysis, Measure Theory, Differential Equations, Approximation Theory, Geometry, Convexity and Combinatorics. An extensive list of these applications, some of which are about fifty years old, appears in [Ste]. Most combinatorial applications of Borsuk's Theorem were found during the last ten years. The best known of these is undoubtfully Lovasz's ingenious proof of the Kneser conjecture. Kneser [Kn] conjectured in 1955 that if n ≥ 2 r + t − 1 and all the r -subsets of an n -element set are colored by t colors then there are two disjoint r -sets having the same color. This was proved by Lovász twenty years later in [Lo]. Shortly afterwards, Bárány [Ba] gave a charming short proof. Both proofs apply Borsuk's theorem.