Linear dependence between hereditary quasirandomness conditions (Q1991420)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Linear dependence between hereditary quasirandomness conditions |
scientific article |
Statements
Linear dependence between hereditary quasirandomness conditions (English)
0 references
30 October 2018
0 references
Summary: Answering a question of \textit{M. Simonovits} and \textit{V. T. Sós} [Combinatorica 17, No. 4, 577--596 (1997; Zbl 0906.05066)], \textit{D. Conlon} et al. [Math. Proc. Camb. Philos. Soc. 164, No. 3, 385--399 (2018; Zbl 1391.05227)] proved that for any nonempty graph \(H\), and any \(\varepsilon>0\), there exists \(\delta>0\) polynomial in \(\varepsilon\), such that if \(G\) is an \(n\)-vertex graph with the property that every \(U\subseteq V(G)\) contains \(p^{e(H)}|U|^{v(H)}\pm\delta n^{v(H)}\) labeled copies of \(H\), then \(G\) is \((p,\varepsilon)\)-quasirandom in the sense that every subset \(U\subseteq G\) contains \(\frac{1}{2}p|U|^{2}\pm\varepsilon n^{2}\) edges. They conjectured that \(\delta\) may be taken to be linear in \(\varepsilon\) and proved this in the case that \(H\) is a complete graph. We study a labelled version of this quasirandomness property proposed by Reiher and Schacht. Let \(H\) be any nonempty graph on \(r\) vertices \(v_{1},\ldots,v_{r}\), and \(\varepsilon>0\). We show that there exists \(\delta=\delta(\varepsilon)>0\) linear in \(\varepsilon\), such that if \(G\) is an \(n\)-vertex graph with the property that every sequence of \(r\) subsets \(U_{1},\ldots,U_{r}\subseteq V(G)\), the number of copies of \(H\) with each \(v_{i}\) in \(U_{i}\) is \(p^{e(H)}\prod|U_{i}|\pm\delta n^{v(H)}\), then \(G\) is \((p,\varepsilon)\)-quasirandom.
0 references
pseudorandomness
0 references
regularity lemma
0 references
0 references