Abstract

An $r$-uniform hypergraph has the $(q,p)$-property if any set of $q$ vertices spans a complete subhypergraph on $p$ vertices. Let $t_r(n,q,p)$ be the minimum edge density of an $n$-vertex $r$-uniform hypergraph with the $(q,p)$-property and let $t_r(q,p)=\underset{n\to \infty }{\lim <!--FUNCTION\; APPLICATION-->}{t}_r(n,q,p)$. A disjoint union of $k$ complete hypergraphs has the $(q,\lceil q∕k\rceil )$-property, which gives $t_r((q,\lceil q∕k\rceil ))\le 1∕k^{r-1}$. The first author, Huang and Rödl showed that these constructions are the best asymptotically, that is, $\underset{q\to \infty }{\lim <!--FUNCTION\; APPLICATION-->}{t}_r((q,\lceil q∕k\rceil ))=1∕k^{r-1}$. They asked whether it is true for all real numbers $\gamma \ge 1$ that $\underset{q\to \infty }{\lim <!--FUNCTION\; APPLICATION-->}{t}_r((q,\lceil q∕\gamma \rceil ))=1∕{\lfloor \gamma \rfloor }^{r-1}$. We give positive answers to this question for a small range of real numbers, and, on the other hand, provide new constructions that give negative answers for many other ranges.

Keywords

Mathematical Subject Classification

Milestones

Authors