Exact solution of the hypergraph Turán problem for $k$-uniform linear paths
Preprint
Abstract
A $k$-uniform linear path of length $\ell$, denoted by $P^{(k)}_\ell$, is a family of $k$-sets $\{F_1,..., F_\ell\}$ such that $|F_i\cap F_{i+1}|=1$ for each $i$ and $F_i\cap F_j=\emptyset$ whenever $|i-j|>1$. Given a $k$-uniform hypergraph $H$ and a positive integer $n$, the {\it $k$-uniform hypergraph Tur\'an number} of $H$, denoted by $\ex_k(n,H)$, is the maximum number of edges in a $k$-uniform hypergraph $\cF$ on $n$ vertices that does not contain $H$ as a subhypergraph. With an intensive use of the delta-system method, we determine $\ex_k(n,P^{(k)}_\ell)$ exactly for all fixed $\ell\geq 1, k\geq 4$, and sufficiently large $n$. We show that $$\ex_k(n,P^{(k)}_{2t+1})={n-1\choose k-1}+{n-2\choose k-1}+...+{n-t\choose k-1}.$$ The only extremal family consists of all the $k$-sets in $[n]$ that meet some fixed set of $t$ vertices. We also show that $$\ex(n, P^{(k)}_{2t+2})={n-1\choose k-1}+{n-2\choose k-1}+...+{n-t\choose k-1}+{n-t-2\choose k-2},$$ and describe the unique extremal family. Stability results on these bounds and some related results are also established.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Linear paths and trees in uniform hypergraphsElectronic Notes in Discrete Mathematics, 2011
- Unavoidable subhypergraphs: a-clustersJournal of Combinatorial Theory, Series A, 2011
- Monochromatic Hamiltonian t‐tight Berge‐cycles in hypergraphsJournal of Graph Theory, 2008
- Extremal k-edge-hamiltonian hypergraphsDiscrete Mathematics, 2008
- An approximate Dirac-type theorem for k-uniform hypergraphsCombinatorica, 2008
- Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degreeJournal of Combinatorial Theory, Series B, 2006
- Stability theorems for cancellative hypergraphsJournal of Combinatorial Theory, Series B, 2004
- On finite set-systems whose every intersection is a Kernel of a starDiscrete Mathematics, 1983
- On coloring graphs to maximize the proportion of multicolored k-edgesJournal of Combinatorial Theory, 1968
- On maximal paths and circuits of graphsActa Mathematica Hungarica, 1959