Some old and new problems in combinatorial geometry I: around Borsuk's problem
Gil Kalai · Cambridge University Press eBooks · 2015
Borsuk [16] asked in 1933 if every set of diameter 1 in R d can be covered by d + 1 sets of smaller diameter. In 1993, a negative solution, based on a theorem by Frankl and Wilson [42], was given by Kahn and Kalai [65]. In this paper I will present questions related to Borsuk's problem. 1 Introduction The title of this paper is borrowed from Paul Erdős who used it (or a similar title) in many lectures and papers, e.g., [39]. I will describe several open problems in the interface between combinatorics and geometry, mainly convex geometry. In this part, I describe and pose questions related to the Borsuk conjecture. The selection of problems is based on my own idiosyncratic tastes. For a fuller picture, the reader is advised to read the review papers on Borsuk's problem and related questions by Raigorodskii [105, 106, 107, 110, 112]. Among other excellent sources are [13, 14, 18, 89, 99]. Karol Borsuk [16] asked in 1933 if every set of diameter 1 in R d can be covered by d + 1 sets of smaller diameter. That the answer is positive was widely believed and referred to as the Borsuk conjecture . However, some people, including Rogers, Danzer, and Erdős, suggested that a counterexample might be obtained from some clever combinatorial configuration. In hindsight, the problem is related to several questions that Erdős asked and its solution was a great triumph for Erdősian mathematics. 2 Better lower bounds to Borsuk's problem The asymptotics Let f ( d ) be the smallest integer such that every set of diameter one in R d can be covered by f ( d ) sets of smaller diameter. The set of vertices of a regular simplex of diameter one demonstrates that f ( d ) ≥ d + 1. The famous Borsuk–Ulam theorem [16] asserts that the d -dimensional ball of diameter 1 cannot be covered by d sets of smaller diameter.