Note on upper density of quasi-random hypergraphs (Q396781): Difference between revisions

Summary: \textit{P. Erdős} [Isr. J. Math. 2, 183--190 (1964; Zbl 0129.39905)] 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 \textit{R. Glebov} et al. [Centro di Ricerca Matematica Ennio De Giorgi (CRM) Series 16, 3--8 (2013; Zbl 1300.05141)]. We prove that every number between [0, 0.3192) is a jump for quasi-random 3-graphs.