Degenerate Turán densities of sparse hypergraphs

Abstract

For fixed integers $r>k\ge 2,e\ge 3$, let $f_r(n,er-(e-1)k,e)$ be the maximum number of edges in an $r$-uniform hypergraph in which the union of any $e$ distinct edges contains at least $er-(e-1)k+1$ vertices. A classical result of Brown, Erdős and Sós in 1973 showed that $f_r(n,er-(e-1)k,e)=\Theta (n^k).$ The degenerate Turán density is defined to be the limit (if it exists) $$\pi (r,k,e):=\underset{n\to \infty }{\lim }\frac{f_r(n,er-(e-1)k,e)}{n^k}.$$ Extending a recent result of Glock for the special case of $r=3,k=2,e=3$, we show that $$\pi (r,2,3):=\underset{n\to \infty }{\lim }\frac{f_r(n,3r-4,3)}{n^2}=\frac{1}{r^2-r-1}$$ for arbitrary fixed $r\ge 4$. For the more general cases $r>k\ge 3$, we show that $$\frac{1}{r^k-r}\le \underset{n\to \infty }{\mathrm{liminf}}\frac{f_r(n,3r-2k,3)}{n^k}\le \underset{n\to \infty }{\mathrm{limsup}}\frac{f_r(n,3r-2k,3)}{n^k}\le \frac{1}{k!\left(\genfrac{}{}{0ex}{}{r}{k}\right)-\frac{k!}{2}}.$$ The main difficulties in proving these results are the constructions establishing the lower bounds. The first construction is recursive and purely combinatorial, and is based on a (carefully designed) approximate induced decomposition of the complete graph, whereas the second construction is algebraic, and is proved by a newly defined matrix property which we call {\it strongly 3-perfect hashing}.

20 pages, JCTA, to appear. (Wuhan Jiayou!)