A short proof of Erdős' conjecture for triple systems

DOI10.1007/S10474-017-0692-8zbMATH Open1399.05219arXiv1609.00530OpenAlexW2513784308WikidataQ123263365 ScholiaQ123263365MaRDI QIDQ1701428FDOQ1701428

Authors: Peter Frankl, Vojtěch Rödl, Andrzej Ruciński 

Publication date: 22 February 2018

Published in: Acta Mathematica Hungarica (Search for Journal in Brave)

Abstract: In 1965 ErdH os conjectured that for all $kge2$, $sge1$ and $ngek(s+1)$, an $n$-vertex $k$-uniform hypergraph $F$ with $u(F)=s$ cannot have more than ewline $$ edges. It took almost fifty years to prove it for triple systems. In 2012 we proved the conjecture for all $s$ and all $nge4(s+1)$. Then {L}uczak and Mieczkowska (2013) proved the conjecture for sufficiently large $s$ and all $n$. Soon after, Frankl proved it for all $s$. Here we present a simpler version of that proof which yields ErdH os's conjecture for $sge33$. Our motivation is to lay down foundations for a possible proof in the much harder case $k=4$, at least for large $s$.

Full work available at URL: https://arxiv.org/abs/1609.00530

Recommendations

• On the maximum number of edges in a triple system not containing a disjoint family of a given size
• Proof of a conjecture of Erdős on triangles in set-systems
• On Erdős' extremal problem on matchings in hypergraphs
• The Brown-Erdős-Sós conjecture in finite abelian groups
• Proof of the Erdős matching conjecture in a new range

zbMATH Keywords

matching\(3\)-uniform hypergraph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Extremal set theory (05D05)

Cites Work

• On maximal paths and circuits of graphs
• On the maximum number of edges in a triple system not containing a disjoint family of a given size
• On Erdős' extremal problem on matchings in hypergraphs
• Improved bounds for Erdős' matching conjecture
• On the maximum number of edges in a hypergraph with given matching number

Cited In (9)

• Proof of the Brown-Erdős-Sós conjecture in groups
• The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphs
• On the maximum size of subfamilies of labeled set with given matching number
• A proof of Frankl–Kupavskii's conjecture on edge‐union condition
• On the maximum number of edges in a triple system not containing a disjoint family of a given size
• The Turán density of triple systems is not principal
• The maximum number of cliques in hypergraphs without large matchings
• Proof of a conjecture of Erdős on triangles in set-systems
• The Brown-Erdős-Sós conjecture in finite abelian groups

This page was built for publication: A short proof of Erdős' conjecture for triple systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1701428)