A Ramsey variant of the Brown–Erdős–Sós conjecture. Issue 5 (7th June 2021)

• Record Type: Journal Article
• Authors: Shapira, Asaf; Tyomkyn, Mykhaylo
• Is Part Of: Bulletin of the London Mathematical Society. Volume 53:Issue 5(2021)
• Page Start: 1453
• Page End: 1469
• Publication Date: 2021-06-07
• Subjects: 05C15 -- 05C65 (primary); Mathematics -- Periodicals; 510
• DOI: 10.1112/blms.12510
• Languages: English
• ISSNs: 0024-6093

Abstract

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 .