z-logo
open-access-imgOpen Access
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].

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom