A counterexample to Borsuk’s conjecture

Kahn, Jeff; Kalai, Gil

doi:10.1090/S0273-0979-1993-00398-7

A counterexample to Borsuk’s conjecture
HTML articles powered by AMS MathViewer

by Jeff Kahn and Gil Kalai PDF

Bull. Amer. Math. Soc. 29 (1993), 60-62 Request permission

Abstract:

Let $f(d)$ be the smallest number so that every set in ${R^d}$ of diameter 1 can be partitioned into $f(d)$ sets of diameter smaller than 1. Borsuk’s conjecture was that $f(d) = d + 1$. We prove that $f(d) \geq (1.2)\sqrt d$ for large d.

References

V. G. Boltjansky and I. Ts. Gohberg, Results and problems in combinatorial geometry, Cambridge University Press, Cambridge, 1985. Translated from the Russian. MR 821465, DOI 10.1017/CBO9780511569258

Drei Sätze über die n-dimensionale euklidische Sphäre

20

J. Bourgain and J. Lindenstrauss, On covering a set in $\textbf {R}^N$ by balls of the same diameter, Geometric aspects of functional analysis (1989–90), Lecture Notes in Math., vol. 1469, Springer, Berlin, 1991, pp. 138–144. MR 1122618, DOI 10.1007/BFb0089220
Hallard T. Croft, Kenneth J. Falconer, and Richard K. Guy, Unsolved problems in geometry, Problem Books in Mathematics, Springer-Verlag, New York, 1991. Unsolved Problems in Intuitive Mathematics, II. MR 1107516, DOI 10.1007/978-1-4612-0963-8

On the k-th diameter in ${E^d}$ and a problem of Grünbaum

R. Daniel Mauldin (ed.), The Scottish Book, Birkhäuser, Boston, Mass., 1981. Mathematics from the Scottish Café; Including selected papers presented at the Scottish Book Conference held at North Texas State University, Denton, Tex., May 1979. MR 666400
Peter Frankl and Vojtěch Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), no. 1, 259–286. MR 871675, DOI 10.1090/S0002-9947-1987-0871675-6
P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 10.1007/BF02579457

Borsuk’s problem and related questions

Jeff Kahn and Gil Kalai, A problem of Füredi and Seymour on covering intersecting families by pairs, J. Combin. Theory Ser. A 68 (1994), no. 2, 317–339. MR 1297176, DOI 10.1016/0097-3165(94)90109-0
Jeff Kahn and P. D. Seymour, A fractional version of the Erdős-Faber-Lovász conjecture, Combinatorica 12 (1992), no. 2, 155–160. MR 1179253, DOI 10.1007/BF01204719
D. G. Larman and C. A. Rogers, The realization of distances within sets in Euclidean space, Mathematika 19 (1972), 1–24. MR 319055, DOI 10.1112/S0025579300004903

Open problem

Marek Lassak, An estimate concerning Borsuk partition problem, Bull. Acad. Polon. Sci. Sér. Sci. Math. 30 (1982), no. 9-10, 449–451 (1983) (English, with Russian summary). MR 703571
C. A. Rogers, Some problems in the geometry of convex bodies, The geometric vein, Springer, New York-Berlin, 1981, pp. 279–284. MR 661785, DOI 10.1007/978-1-4612-5648-9_{1}9
Oded Schramm, Illuminating sets of constant width, Mathematika 35 (1988), no. 2, 180–189. MR 986627, DOI 10.1112/S0025579300015175

Graph intersection theorems