Exact solution of the hypergraph Turán problem for $k$-uniform linear paths

Details Exact solution of the hypergraph Turán problem for $k$-uniform linear paths Exact solution of the hypergraph Turán problem for $k$-uniform linear paths

2011-08-05

arxiv.org/abs/1108.1247v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Exact solution of the hypergraph Turán problem for $k$-uniform linear paths does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Exact solution of the hypergraph Turán problem for $k$-uniform linear paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact solution of the hypergraph Turán problem for $k$-uniform linear paths will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-667902