We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A short proof of Erdős' conjecture for triple systems.
- Authors
Frankl, P.; Rödl, V.; Ruciński, A.
- Abstract
Erdős [1] conjectured that for all $${k \geq 2}$$ , $${s \geq 1}$$ and $${n \geq {k(s+1)}}$$ , an n-vertex k-uniform hypergraph $${\mathcal{F}}$$ with $${\nu(\mathcal{F})=s}$$ cannot have more than $${\max\{\binom{sk+k-1}k,\binom nk-\binom{n-s}k\}}$$ edges. It took almost fifty years to prove it for triple systems. In [5] we proved the conjecture for all s and all $${n \geq 4(s+1)}$$ . Then Łuczak and Mieczkowska [6] 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 Erdős' conjecture for $${s \geq 33}$$ . Our motivation is to lay down foundations for a possible proof in the much harder case k = 4, at least for large s.
- Subjects
MATHEMATICAL proofs; STEINER systems; HYPERGRAPHS; MATCHING theory; UNIFORM algebras
- Publication
Acta Mathematica Hungarica, 2017, Vol 151, Issue 2, p495
- ISSN
0236-5294
- Publication type
Article
- DOI
10.1007/s10474-017-0692-8