Proof of the Brown–Erdős–Sós conjecture in groups
| Autor: | Rajko Nenadov, Mykhaylo Tyomkyn, Benny Sudakov |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Mathematical Proceedings of the Cambridge Philosophical Society. 169:323-333 |
| ISSN: | 1469-8064 0305-0041 |
| DOI: | 10.1017/s0305004119000203 |
| Popis: | The conjecture of Brown, Erdős and Sós from 1973 states that, for any k ≥ 3, if a 3-uniform hypergraph H with n vertices does not contain a set of k +3 vertices spanning at least k edges then it has o(n2) edges. The case k = 3 of this conjecture is the celebrated (6, 3)-theorem of Ruzsa and Szemerédi which implies Roth’s theorem on 3-term arithmetic progressions in dense sets of integers. Solymosi observed that, in order to prove the conjecture, one can assume that H consists of triples (a, b, ab) of some finite quasigroup Γ. Since this problem remains open for all k ≥ 4, he further proposed to study triple systems coming from finite groups. In this case he proved that the conjecture holds also for k = 4. Here we completely resolve the Brown–Erdős–Sós conjecture for all finite groups and values of k. Moreover, we prove that the hypergraphs coming from groups contain sets of size $\Theta (\sqrt k )$ which span k edges. This is best possible and goes far beyond the conjecture. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|