A Ramsey variant of the Brown–Erdős–Sós conjecture. Issue 5 (7th June 2021) - Shapira, Asaf; Tyomkyn, Mykhaylo
Abstract: An r ‐uniform hypergraph ( r ‐graph for short) is called linear if every pair of vertices belongs to at most one edge. A linear r ‐graph is complete if every pair of vertices is in exactly one edge. The famous Brown–Erdős–Sós conjecture states that for every fixed k and r, every linear r ‐graph with Ω ( n 2 ) edges contains k edges spanned by at most ( r − 2 ) k + 3 vertices. As an intermediate step towards this conjecture, Conlon and Nenadov recently suggested to prove its natural Ramsey relaxation. Namely, that for every fixed k, r and c, in every c ‐colouring of a complete linear r ‐graph, one can find k monochromatic edges spanned by at most ( r − 2 ) k + 3 vertices. We prove that this Ramsey version of the conjecture holds under the additional assumption that r ⩾ r 0 ( c ), and we show that for c = 2 it holds for all r ⩾ 4 .