An Exact Result for Hypergraphs and Upper Bounds for the Turán Density of $K^r_{r+1}$
Author(s) -
Linyuan Lü,
Yi Zhao
Publication year - 2009
Publication title -
siam journal on discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.843
H-Index - 66
eISSN - 1095-7146
pISSN - 0895-4801
DOI - 10.1137/070710615
Subject(s) - combinatorics , mathematics , hypergraph , upper and lower bounds , prime (order theory) , mathematical analysis
We first answer a question of de Caen [Extremal Problems for Finite Sets, János Bolyai Math. Soc., Budapest, 1994, pp. 187-197]: given $r\geq3$, if $G$ is an $r$-uniform hypergraph on $n$ vertices such that every $r+1$ vertices span 1 or $r+1$ edges, then $G=K^r_n$ or $K^r_{n-1}$, assuming that $n(p-1)r$, where $p$ is the smallest prime factor of $r-1$. We then show that the Turán density $\pi(K^r_{r+1})\leq1-1/r-(1-1/r^{p-1})(r-1)^2/(2r^p({r+p\choose p-1}+{r+1\choose 2}))$, for all even $r\geq4$, improving a well-known bound $1-\frac{1}{r}$ of de Caen [Ars Combin., 16 (1983), pp. 5-10] and Sidorenko [Vestnik Moskov. Univ. Ser. I Mat. Mekh., 76 (1982), pp. 3-6].
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom