A problem of Erdős and Sós on 3-graphs

By Roman Glebov, Daniel Král', Jan Volec. 2013

58 citations recorded by the source corpus.

AbstractWe show that for every ɛ > 0 there exist δ > 0 and n0 ∈ ℕ such that every 3-uniform hypergraph on n ≥ n0 vertices with the property that every k-vertex subset, where k ≥ δn, induces at least $$\left( {\frac{1} {2} + \varepsilon } \right)\left( {\begin{array}{*{20}c} k \\ 3 \\ \end{array} } \right)$$ edges, contains K4− as a subgraph, where K4− is the 3-uniform hypergraph on 4 vertices with 3 edges. This question was originally raised by Erdős and Sós. The constant 1/4 is the best possible.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/38a2c14824b1fce83361ea6b4239e0335b535cf6