Note on upper density of quasi-random hypergraphs
type: Item
instance of: scholarly article
title: Note on upper density of quasi-random hypergraphs
zbMATH Open document ID: 1298.05235
author: Vindya Bhat
author: Vojtěch Rödl
published in: The Electronic Journal of Combinatorics
publication date: 2014-08-14T00:00:00Z
full work available at URL: v20i2p59
review text: 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.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C42
zbMATH DE Number: 6330267
zbMATH Keywords: hypergraphs
zbMATH Keywords: density
zbMATH Keywords: quasi-random
zbMATH Keywords: jumps
MaRDI profile type: Publication
cites work: Random sampling and approximation of MAX-CSP problems
cites work: On extremal problems of graphs and generalized graphs
cites work: Hypergraphs do not jump
cites work: A problem of Erdős and Sós on 3-graphs
cites work: ON THE METHOD OF PAIRED COMPARISONS
cites work: Q5585195
cites work: Uniform edge distribution in hypergraphs is hereditary
cites work: Flag algebras
cites work: On universality of graphs with uniformly distributed edges
Recommended article: Quasi-random hypergraphs revisited
Recommended article: On the upper tail problem for random hypergraphs
Recommended article: Quasi-random graphs of given density and Ramsey numbers
Recommended article: Quasi-random hypergraphs
Recommended article: Quasirandomness in hypergraphs
Recommended article: Hypergraphs, quasi-randomness, and conditions for regularity
Recommended article: Q5371208
description: scientific article; zbMATH DE number 6330267