Small subsets inherit sparse \(\varepsilon\)-regularity
type: Item
instance of: scholarly article
title: Small subsets inherit sparse \(\varepsilon\)-regularity
zbMATH Open document ID: 1111.05090
author: Stefanie Gerke
author: Yoshiharu Kohayakawa
author: Vojtěch Rödl
author: Angelika Steger
published in: Journal of Combinatorial Theory. Series B
publication date: 2007-01-11T00:00:00Z
review text: Nowadays, even babies know the Szemerédi regularity lemma. Roughly: If \(G\) is a large enough graph, its vertex set can be broken down into a constant number of blocks \(V_{0},\dots V_{k}\) such that most pairs induce so-called \(\varepsilon\)-regular graphs, that is ones where the number of edges between two sets of vertices is close to what it would be if the graph were a random graph of the same density. This fact is, in the context of dense graphs (those which have \(n\) vertices and \(\geq cn^{2}\) edges for some constanc \(c>0\)) used to show that the graph induced by an \(\varepsilon\)-regular pair \((V_{i},V_{j})\) contains every fixed \(k\)-chromatic graph, provided the \(V_{i}\) are sufficiently large and \(\varepsilon\) is sufficiently small relative to the densities of edges between the partition classes: this last fact is called the embedding lemma. It has been known for a long time that the situation becomes harder when the graph is sparse. Crudely speaking, this is because the definition of \(\varepsilon\)-regular is that, for subsets \(A\) and \(B\) we have \[ \left| \frac{e(A,B)}{| A| | B|}-d\right| \leq \varepsilon \] where \(e(A,B)\) denotes the number of edges from \(A\) to \(B\) and \(d\) is the density. The point is that if \(e(G)=o(n^{2})\), this is too easy to get: very often, both terms on the left hand-side will be \(o(1)\) so their difference will indeed be \(o(1)\). Further complications include the fact that there is no sensible embedding lemma here. Thus we need a more sophisticated definition in these cases. This is done by considering bipartite graphs \((V_{1}\cup V_{2},E)\) with density \(d=| E|/| V_{1}| | V_{2}|\) and saying it is \((\varepsilon,p)\)-regular if we have \[ \left| \frac{e(A,B)}{| A| | B|}-d\right| \leq \varepsilon \] so that the old definition of \(\varepsilon\)-regular is equivalent to our new \((\varepsilon,1)\)-regularity. A special case is \((\varepsilon,d)\)-regular, which we call \((\varepsilon)\)-regular (note…
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 5115318
zbMATH Keywords: sparse regularity lemma
zbMATH Keywords: quasi-randomness
zbMATH Keywords: small witness to high chromatic number
zbMATH Keywords: \(C_{\ell}\)-free graph
reviewed by: David B. Penman
Wikidata QID: Q105583648
MaRDI profile type: Publication
full work available at URL: j.jctb.2006.03.004
OpenAlex ID: W2030380672
cites work: On graphs with small subgraphs of large chromatic number
cites work: Large triangle-free subgraphs in graphs without \(K_ 4\)
cites work: Random Ramsey graphs for the four-cycle
cites work: Q3576710
cites work: \(K_4\)-free subgraphs of random graphs revisited
cites work: K5‐free subgraphs of random graphs
cites work: Q3416250
cites work: Turán's extremal problem in random graphs: Forbidding even cycles
cites work: Turán's extremal problem in random graphs: Forbidding odd cycles
cites work: Q4519896
cites work: Szemerédi’s Regularity Lemma for Sparse Graphs
cites work: Q4361714
cites work: An extremal problem for random graphs and the number of graphs with large even-girth
cites work: Arithmetic progressions of length three in subsets of a random set
cites work: On \(K^ 4\)-free subgraphs of random graphs
cites work: Regular pairs in sparse random graphs I
cites work: Q4407452
cites work: The Turn Theorem for Random Graphs
cites work: Q4878666
cites work: Q4736881
cites work: On triangle-free random graphs
cites work: Q3872505
cites work: On universality of graphs with uniformly distributed edges
cites work: Turán's theorem in sparse random graphs
cites work: Q4200109
DOI: 10.1016/J.JCTB.2006.03.004
description: scientific article; zbMATH DE number 5115318