Note on Upper Density of Quasi-Random Hypergraphs

Abstract

In 1964, Erdős proved that for any $\alpha > 0$, an $l$-uniform hypergraph $G$ with $n \geq n_0(\alpha, l)$ vertices and $\alpha \binom{n}{l}$ edges contains a large complete $l$-equipartite subgraph. This implies that any sufficiently large $G$ with density $\alpha > 0$ contains a large subgraph with density at least $l!/l^l$.In this note we study a similar problem for $l$-uniform hypergraphs $Q$ with a weak quasi-random property (i.e. with edges uniformly distributed over the sufficiently large subsets of vertices). We prove that any sufficiently large quasi-random $l$-uniform hypergraph $Q$ with density $\alpha > 0$ contains a large subgraph with density at least $\frac{(l-1)!}{l^{l-1}-1}$. In particular, for $l=3$, any sufficiently large such $Q$ contains a large subgraph with density at least $\frac{1}{4}$ which is the best possible lower bound.We define jumps for quasi-random sequences of $l$-graphs and our result implies that every number between 0 and $\frac{(l-1)!}{l^{l-1}-1}$ is a jump for quasi-random $l$-graphs. For $l=3$ this interval can be improved based on a recent result of Glebov, Král' and Volec. We prove that every number between [0, 0.3192) is a jump for quasi-random $3$-graphs.

Locations

• The Electronic Journal of Combinatorics - View - PDF