Cutting corners

doi:10.1016/j.jctb.2025.11.008

Cutting corners

2025-12-01

1

PRE

AI

DOI：10.1016/j.jctb.2025.11.008

Original

Original request for help

Save

Abstract

En 中文

We say that a subset M of R-n is exponentially Ramsey if there exists epsilon > 0 and n(0) such that chi(R-n, M) > (1 + epsilon)(n) for any n > n(0), where chi(R-n, M) stands for the minimum number of colors in a coloring of Rnsuch that no copy of M is monochromatic. One important result in Euclidean Ramsey theory is due to Frankl and Rodl, and states the following (under some mild extra conditions): if both N-1 and N-2 are exponentially Ramsey then so is their Cartesian product. Applied several times to simple two-point sets N-i, this result implies that any subset M of a 'hyperrectangle' N(1)x ... x N-k is exponentially Ramsey. However, generally, such 'embeddings' of M result in very inefficient bounds on the aforementioned epsilon. In this paper, we present another way of combining exponentially Ramsey sets, which gives much better estimates in some important cases. In particular, we show that the chromatic number of Rnwith a forbidden equilateral triangle satisfies chi(R-n, Delta) >= (1.0742...+ o(1))(n), greatly improving upon the previous constant 1.0144. We also obtain similar strong results for regular simplices of larger dimensions, as well as for related geometric Ramsey-type questions in Manhattan norm. We then show that the same technique implies several interesting corollaries in other combinatorial problems. In particular, we give an explicit upper bound on the size of a family F subset of 2([n]) that contains no weak k-sunflowers, i.e. no collection of k sets with pairwise intersections of the same size. This bound improves upon previously known results for all k >= 4. Finally, we also present a simple deduction of the (other) celebrated Frankl-Rodl theorem from an earlier result of Frankl and Wilson. It gives probably the shortest known proof of Frankl and Rodl result with the most efficient bounds.

Keywords:

Weak sunflowers

Forbidden intersections

Euclidean Ramsey theory

Cutting corners

Abstract

Journal

Organization

Cited Papers