Skip to main content
Contents
Search Book
Search Results:
No results.
Readability settings Prev Up Next \( \providecommand{\glspostdescription}{}
\renewcommand{\glspostdescription}{}
\def\cprime{\char"7E }
\def\cdprime{\char"7F }
\def\eoborotnoye{\char'013}
\def\Eoborotnoye{\char'003}
\newcommand{\beq}[1]{\begin{equation}\label{#1}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\weakstar}{weak${}^*$ }
\newcommand{\rng}{\operatorname{rng}}
\newcommand{\ex}{\operatorname{ex}}
\newcommand{\colex}{\prec_{\operatorname{colex}}}
\newcommand{\lex}{\prec_{\operatorname{lex}}}
\newcommand{\per}{\operatorname{per}}
\newcommand{\permat}{\operatorname{pm}}
\renewcommand{\hom}{\operatorname{hom}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\degree}{d}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Chapter 5 The Regularity Lemma
In the previous two chapters, we have encountered two main types of “extremal” constructions of graphs which minimize or maximize the number of copies of a given graph, under certain constraints:
Partition the vertex set into a bounded number of “parts.” Join two vertices with an edge if they are in different parts, but not if they are in the same part. (Mantel’s Theorem, Turán’s Theorem, the Erdős–Stone Theorem)
The focus of this chapter is on the remarkable fact that the structure of any graph
\(G\) can be described as a mixture of these two types of constructions, up to small errors; this is known as the SzemerĂ©di Regularity LemmaÂ
[278] . Note that, unlike in previous chapters, we are speaking about
any graph here, with no assumptions on it being an extremal configuration for any particular combinatorial problem. Therefore, the Regularity Lemma is more than just a useful tool for extremal combinatorics; it is a profound statement about the nature of graphs themselves.
