Note on upper density of quasi-random hypergraphs
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.
- Quasi-random hypergraphs revisited
- On the upper tail problem for random hypergraphs
- Quasi-random graphs of given density and Ramsey numbers
- Quasi-random hypergraphs
- Quasi-random hypergraphs
- Quasirandomness in hypergraphs
- Quasirandomness in hypergraphs
- Hypergraphs, quasi-randomness, and conditions for regularity
- Quasi-randomness and the regularity method in hypergraphs
- Flag algebras
- scientific article; zbMATH DE number 3303831 (Why is no real title available?)
- Hypergraphs do not jump
- On extremal problems of graphs and generalized graphs
- ON THE METHOD OF PAIRED COMPARISONS
- On universality of graphs with uniformly distributed edges
- Random sampling and approximation of MAX-CSP problems
- Uniform edge distribution in hypergraphs is hereditary
This page was built for publication: Note on upper density of quasi-random hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396781)
