Borsuk and Ramsey type questions in Euclidean space. (English) Zbl 1400.05257
Butler, Steve (ed.) et al., Connections in discrete mathematics. A celebration of the work of Ron Graham. Cambridge: Cambridge University Press (ISBN 978-1-316-60788-6/pbk; 978-1-107-15398-1/hbk; 978-131-665029-5/ebook). 259-277 (2018).
Summary: We give a short survey of problems and results on (1) diameter graphs and hypergraphs, and (2) geometric Ramsey theory. We also make some modest contributions to both areas. Extending a well-known theorem of Kahn and Kalai that disproved Borsuk’s conjecture, we show that for any integer \(r\geq 2\), there exist \(\varepsilon=\varepsilon(r)>0\) and \(d_0= d_0(r)\) with the following property. For every \(d\geq d_0\), there is a finite point set \(P\subset\mathbb{R}^d\) of diameter 1 such that no matter how we color the elements of \(P\) with fewer than \((1+\varepsilon)^{{\sqrt d}}\) colors, we can always find \(r\) points of the same color, any two of which are at distance 1.
P. Erdős et al. [J. Comb. Theory, Ser. A 14, 341–363 (1973; Zbl 0276.05001)] called a finite point set \(P\subset\mathbb{R}^d\) Ramsey if for every \(r\geq 2\), there exists a set \(R= R(P,r)\subset\mathbb{R}^D\) for some \(D\geq d\) such that no matter how we color all of its points with \(r\) colors, we can always find a monochromatic congruent copy of \(P\). If such a set \(R\) exists with the additional property that its diameter is the same as the diameter of \(P\), then we call \(P\) diameter-Ramsey. We prove that, in contrast to the original Ramsey property, (1) the condition that \(P\) is diameter-Ramsey is not hereditary, and (2) not all triangles are diameter-Ramsey. We raise several open questions related to this new concept.
For the entire collection see [Zbl 1390.05002].
P. Erdős et al. [J. Comb. Theory, Ser. A 14, 341–363 (1973; Zbl 0276.05001)] called a finite point set \(P\subset\mathbb{R}^d\) Ramsey if for every \(r\geq 2\), there exists a set \(R= R(P,r)\subset\mathbb{R}^D\) for some \(D\geq d\) such that no matter how we color all of its points with \(r\) colors, we can always find a monochromatic congruent copy of \(P\). If such a set \(R\) exists with the additional property that its diameter is the same as the diameter of \(P\), then we call \(P\) diameter-Ramsey. We prove that, in contrast to the original Ramsey property, (1) the condition that \(P\) is diameter-Ramsey is not hereditary, and (2) not all triangles are diameter-Ramsey. We raise several open questions related to this new concept.
For the entire collection see [Zbl 1390.05002].
