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

DOI10.1007/S10474-017-0692-8MaRDI QIDQ1701428zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

matching\(3\)-uniform hypergraph

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

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)