Szemeredi regularity lemma

Szemeredi’s regularity lemma is a lemma from the general theory of graphs that states that the vertices of any sufficiently large graph can be divided into a finite number of groups such that in almost all bipartite graphs connecting vertices from two different groups, the edges are distributed almost evenly between the vertices. In this case, the minimum required number of groups into which the set of graph vertices must be divided can be arbitrarily large, but the number of groups in the partition is always limited from above.

Speaking informally, the lemma states the presence of a large number of large pseudorandom structures in absolutely any graph of sufficiently large size.

The lemma was proved by Endre Cemeredi in 1975. ^[1] ^[2]

Wording

The concept $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\varepsilon$ -uniformity

Counting the edges shows that this graph can be

\varepsilon

{\ displaystyle \ varepsilon}

\varepsilon

-regular only for

\varepsilon >{\frac {7}{50}}

{\ displaystyle \ varepsilon> {\ frac {7} {50}}}

\varepsilon >{\frac {7}{50}}

(such an assessment is appropriate in this case only because

|S|>|T|>{\frac {7}{50}}|V|={\frac {7}{50}}|U|

{\ displaystyle | S |> | T |> {\ frac {7} {50}} | V | = {\ frac {7} {50}} | U |}

|S|>|T|>{\frac {7}{50}}|V|={\frac {7}{50}}|U|

)

Let a bipartite graph be given $G=(W=U\sqcup V,E)$ ${\ displaystyle G = (W = U \ sqcup V, E)}$ $G=(W=U\sqcup V,E)$ whose edges connect the vertices from the set $U$ ${\ displaystyle U}$ $U$ with vertices from the set $V$ ${\ displaystyle V}$ $V$ .

For $S\subset U,T\subset V$ ${\ displaystyle S \ subset U, T \ subset V}$ $S\subset U,T\subset V$ denote by $d(S,T)$ ${\ displaystyle d (S, T)}$ $d(S,T)$ edge distribution density between these sets, i.e.

d(S,T)={\frac {\#\left\lbrace {(u,v)\in E:u\in S,v\in T}\right\rbrace }{|S||T|}}

{\ displaystyle d (S, T) = {\ frac {\ # \ left \ lbrace {(u, v) \ in E: u \ in S, v \ in T} \ right \ rbrace} {| S || T |}}}

d(S,T)={\frac {\#\left\lbrace {(u,v)\in E:u\in S,v\in T}\right\rbrace }{|S||T|}}

.

Definition ^[1] ^[3]

Dicotyledonous graph $G=(U\sqcup V,E)$ ${\ displaystyle G = (U \ sqcup V, E)}$ $G=(U\sqcup V,E)$ called $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\varepsilon$ -uniform if for any $S\subset U,T\subset V$ ${\ displaystyle S \ subset U, T \ subset V}$ $S\subset U,T\subset V$ satisfying the conditions $|S|>\varepsilon |U|,|T|>\varepsilon |V|$ ${\ displaystyle | S |> \ varepsilon | U |, | T |> \ varepsilon | V |}$ $|S|>\varepsilon |U|,|T|>\varepsilon |V|$ , the inequality

|d(S,T)-d(U,V)|\leq \varepsilon

{\ displaystyle | d (S, T) -d (U, V) | \ leq \ varepsilon}

|d(S,T)-d(U,V)|\leq \varepsilon

There are several equivalent definitions (equivalent in the sense of the existence of a monotonic dependence $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\varepsilon$ in one definition from $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\varepsilon$ in the other with the equivalence of the two definitions), but they all use the value $d(S,T)$ ${\ displaystyle d (S, T)}$ $d(S,T)$ and some quantitative comparison of its values for different pairs $S, T$ ${\ displaystyle S, T}$ $S,T$ .

Obviously, full and empty bipartite graphs are $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\varepsilon$ - regular for any $\varepsilon >0$ ${\ displaystyle \ varepsilon> 0}$ $\varepsilon >0$ . It should be noted that this, generally speaking, is not true for an arbitrary regular bipartite graph in the usual sense (for example, the union of several regular graphs disjoint in the set of vertices can be considered as a counterexample).

$\varepsilon$ ${\ displaystyle \ varepsilon}$ -uniform graphs for a given $\varepsilon$ ${\ displaystyle \ varepsilon}$ sometimes also called pseudo-random , because by the uniform distribution of the edges between the vertices, they are similar to randomly generated ones.

The statement of the lemma

A three-part graph with random sets of edges of different densities between shares (for red edges -

0.8

{\ displaystyle 0.8}

for green -

0.5

{\ displaystyle 0.5}

, for blue -

0.25

{\ displaystyle 0.25}

) Similar configurations of edges are formed between the components of the partition from the Szemeredi theorem, since

\varepsilon

{\ displaystyle \ varepsilon}

-regular graphs are similar to random.

Szemeredi regularity lemma ^[3] ^[4]

For any $\varepsilon >0,\ m\geq 2$ ${\ displaystyle \ varepsilon> 0, \ m \ geq 2}$ exist $M,n_{0}$ ${\ displaystyle M, n_ {0}}$ such that for any graph $G=(V,E)$ ${\ displaystyle G = (V, E)}$ with the number of vertices $|V|>n_{0}$ ${\ displaystyle | V |> n_ {0}}$ there is a partition $V=V_{1}\sqcup \dots \sqcup V_{k}\ (m\leq k\leq M)$ ${\ displaystyle V = V_ {1} \ sqcup \ dots \ sqcup V_ {k} \ (m \ leq k \ leq M)}$ as much as possible equal in size $|V_{1}|=\dots =|V_{k-1}|\geq |V_{k}|$ ${\ displaystyle | V_ {1} | = \ dots = | V_ {k-1} | \ geq | V_ {k} |}$ such that for $(1-\varepsilon ){\binom {k}{2}}$ ${\ displaystyle (1- \ varepsilon) {\ binom {k} {2}}}$ of the pairs of these shares, the bipartite graph of edges lying between them is $\varepsilon$ ${\ displaystyle \ varepsilon}$ - regular.

Remarks

The Cemeredi lemma does not impose any restrictions on the edges between the vertices from the same set of partitions.

The assertion of the lemma is nontrivial only for graphs with a sufficiently large number of edges. If a $|E|\leq {\frac {\varepsilon ^{3}}{k^{2}}}|V|^{2}$ ${\ displaystyle | E | \ leq {\ frac {\ varepsilon ^ {3}} {k ^ {2}}} | V | ^ {2}}$ , then any of its bipartite subgraphs on fractions with sizes ${\frac {\varepsilon }{k}}|V|$ ${\ displaystyle {\ frac {\ varepsilon} {k}} | V |}$ will also be rarefied (its density will not exceed $\varepsilon$ ${\ displaystyle \ varepsilon}$ ) - therefore, the condition on the density difference will always be satisfied. ^[five]

It should also be noted that mentioning the same variable $\varepsilon$ ${\ displaystyle \ varepsilon}$ in two different characteristics - a measure of regularity and a share $\varepsilon$ ${\ displaystyle \ varepsilon}$ -regular bipartite subgraphs - does not create any additional connection between these characteristics. Such a formulation would also follow from a weaker formulation, which would require, for example, that $\varepsilon$ ${\ displaystyle \ varepsilon}$ - Ribs were only regularly distributed between $(1-\eta ){\binom {k}{2}}$ ${\ displaystyle (1- \ eta) {\ binom {k} {2}}}$ pairs of sets where $\eta =\eta (\varepsilon )\to 0$ ${\ displaystyle \ eta = \ eta (\ varepsilon) \ to 0}$ at $\varepsilon \to 0$ ${\ displaystyle \ varepsilon \ to 0}$ (i.e., even with $\eta >\varepsilon$ ${\ displaystyle \ eta> \ varepsilon}$ ) In this case, to achieve the original formulation, it would be sufficient to consider $\varepsilon _{0}=\eta ^{-1}(\varepsilon )$ ${\ displaystyle \ varepsilon _ {0} = \ eta ^ {- 1} (\ varepsilon)}$ , insofar as $\varepsilon _{0}$ ${\ displaystyle \ varepsilon _ {0}}$ -regularity of the graph entails $\varepsilon$ ${\ displaystyle \ varepsilon}$ -regularity at $\varepsilon _{0}<\varepsilon$ ${\ displaystyle \ varepsilon _ {0} <\ varepsilon}$ .

Proof

Partition Algorithm

The splitting is done by a greedy algorithm.

First, an arbitrary partition of vertices into sets is chosen $V_{1},\dots ,V_{k}$ ${\ displaystyle V_ {1}, \ dots, V_ {k}}$ where:

$|V_{1}|=\dots =|V_{k-1}|>|V_{k}|$ ${\ displaystyle | V_ {1} | = \ dots = | V_ {k-1} |> | V_ {k} |}$
$k=\max \left({{\frac {1}{\varepsilon }},m}\right)$ ${\ displaystyle k = \ max \ left ({{\ frac {1} {\ varepsilon}}, m} \ right)}$

Then, at each iteration of the algorithm, a new partition is generated in a certain way from the existing partition with smaller sizes of the parts and a large number of them. It is constructed as a subdivision of the initial partition, but then it is normalized by small rearrangements so that the sizes of all (except, perhaps, one) parts are equal.

Such a transformation continues so far in the resulting partition into $k^{'}$ ${\ displaystyle k '}$ at least $\varepsilon {\binom {k'}{2}}$ ${\ displaystyle \ varepsilon {\ binom {k '} {2}}}$ pairs of sets, bipartite graphs between which are not $\varepsilon$ ${\ displaystyle \ varepsilon}$ -regular. The transition from one partition to the next takes place in such a way that it is possible to prove that the algorithm stops exactly for a finite and bounded constant (depending on $\varepsilon$ ${\ displaystyle \ varepsilon}$ and $m$ ${\ displaystyle m}$ ) number of steps. In addition, the number of resulting sets in the partition at each particular iteration of the algorithm is also limited, so the maximum number of sets that can be formed at the last iteration will be the desired value $M$ ${\ displaystyle M}$ . ^[3]

Transition from subdivision to subdivision

Let the current partition ${\mathcal {P}}=(V_{1},\dots ,V_{k})$ ${\ displaystyle {\ mathcal {P}} = (V_ {1}, \ dots, V_ {k})}$ does not satisfy the conditions of the lemma, i.e., there is $\varepsilon {\binom {k}{2}}$ ${\ displaystyle \ varepsilon {\ binom {k} {2}}}$ steam $(V_{i},V_{j}),i\not =j$ ${\ displaystyle (V_ {i}, V_ {j}), i \ not = j}$ for which the bipartite graph between them is not $\varepsilon$ ${\ displaystyle \ varepsilon}$ -regular. We denote this condition as $P_{\varepsilon }(V_{i},V_{j})$ ${\ displaystyle P _ {\ varepsilon} (V_ {i}, V_ {j})}$ .

If a $P_{\varepsilon }(V_{i},V_{j})$ ${\ displaystyle P _ {\ varepsilon} (V_ {i}, V_ {j})}$ , then there are some specific “problem” subsets $S_{ij}\in V_{i},S_{ji}\in V_{j}$ ${\ displaystyle S_ {ij} \ in V_ {i}, S_ {ji} \ in V_ {j}}$ violating $\varepsilon$ ${\ displaystyle \ varepsilon}$ -regularity of the bipartite graph connecting these components. That is, for them it is executed:

$|S_{ij}|>\varepsilon |V_{i}|$ ${\ displaystyle | S_ {ij} |> \ varepsilon | V_ {i} |}$
$|S_{ji}|>\varepsilon |V_{j}|$ ${\ displaystyle | S_ {ji} |> \ varepsilon | V_ {j} |}$
$|d(S_{ij},S_{ji})-d(V_{i},V_{j})|>\varepsilon$ ${\ displaystyle | d (S_ {ij}, S_ {ji}) - d (V_ {i}, V_ {j}) |> \ varepsilon}$

It seems reasonable to get rid of these problematic subsets by simply selecting them as a separate component, forming instead of a pair of components $(V_{i},V_{j})$ ${\ displaystyle (V_ {i}, V_ {j})}$ four $(S_{ij},V_{i}\setminus S_{ij},S_{ji},V_{j}\setminus S_{ji})$ ${\ displaystyle (S_ {ij}, V_ {i} \ setminus S_ {ij}, S_ {ji}, V_ {j} \ setminus S_ {ji})}$ . However, the same component $V_{i}$ ${\ displaystyle V_ {i}}$ may conflict with several other components at once, so the partition should be done not one at a time, but several multiple problem sets at once.

To formalize this process, for each individual component $V_{i}$ ${\ displaystyle V_ {i}}$ all "problematic" subsets arising in it are considered:

{\mathcal {S}}(V_{i})=\left\lbrace {S_{ij}:1\leq j\leq k,P_{\varepsilon }(V_{i},V_{j})}\right\rbrace

{\ displaystyle {\ mathcal {S}} (V_ {i}) = \ left \ lbrace {S_ {ij}: 1 \ leq j \ leq k, P _ {\ varepsilon} (V_ {i}, V_ {j} )} \ right \ rbrace}

and the σ-algebra formed by ${\mathcal {S}}(V_{i})$ ${\ displaystyle {\ mathcal {S}} (V_ {i})}$ on $V_{i}$ ${\ displaystyle V_ {i}}$ (i.e $V_{i}$ ${\ displaystyle V_ {i}}$ is divided into parts such that any two vertices, one of which belongs to some $S_{ij}$ ${\ displaystyle S_ {ij}}$ , and the other does not belong to him, they were in different parts of the subdivision).

Because for an individual $V_{i}$ ${\ displaystyle V_ {i}}$ there is no more $k-1$ ${\ displaystyle k-1}$ problematic subsets (and therefore no more $2^{k-1}$ ${\ displaystyle 2 ^ {k-1}}$ elements of the σ-algebra built on them), then as a result of no more than one component is formed $2^{k-1}$ ${\ displaystyle 2 ^ {k-1}}$ new ones.

If you divide each component in this way $V_{i}$ ${\ displaystyle V_ {i}}$ then we get a new subdivision ${\mathcal {P}}'$ ${\ displaystyle {\ mathcal {P}} '}$ .

Further in ${\mathcal {P}}'$ ${\ displaystyle {\ mathcal {P}} '}$ it is necessary to align the dimensions of the components (of which there are no more than $k2^{k-1}$ ${\ displaystyle k2 ^ {k-1}}$ ) For this, each of its components can be divided into new size components. $\left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor$ ${\ displaystyle \ left \ lfloor {\ frac {n} {{(k2 ^ {k-1})} ^ {2}}} \ right \ rfloor}$ (and, possibly, the one remaining smaller component is the “remainder”), and all the vertices from the “residues” should be arbitrarily combined into new components of the same size $\left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor$ ${\ displaystyle \ left \ lfloor {\ frac {n} {{(k2 ^ {k-1})} ^ {2}}} \ right \ rfloor}$ and possibly one smaller component.

The resulting partition will be the result of one iteration of the algorithm.

Estimating the Number of Algorithm Steps

The proof that the algorithm stops after a finite number of steps is done by introducing a potential function — a numerical value that depends on the current partition — and tracking its changes when changing the iterations of the algorithm.

"Potential" may be defined, for example, as follows:

\Phi ({\mathcal {P}})=\sum \limits _{1\leq i<j\leq |{\mathcal {P}}|}{{\frac {|V_{i}||V_{j}|}{|V|^{2}}}d(V_{i},V_{j})^{2}}

{\ displaystyle \ Phi ({\ mathcal {P}}) = \ sum \ limits _ {1 \ leq i <j \ leq | {\ mathcal {P}} |} {{\ frac {| V_ {i} | | V_ {j} |} {| V | ^ {2}}} d (V_ {i}, V_ {j}) ^ {2}}}

This function has a number of important properties:

$0\leq \Phi ({\mathcal {P}})\leq 1$ ${\ displaystyle 0 \ leq \ Phi ({\ mathcal {P}}) \ leq 1}$

if the partition ${\mathcal {Q}}$ ${\ displaystyle {\ mathcal {Q}}}$ formed from ${\mathcal {P}}=(V_{1},\dots ,V_{k})$ ${\ displaystyle {\ mathcal {P}} = (V_ {1}, \ dots, V_ {k})}$ subdivision of one component $V_{1}$ ${\ displaystyle V_ {1}}$ into two sets $S\subset V_{1}$ ${\ displaystyle S \ subset V_ {1}}$ and $V_{1}\setminus S$ ${\ displaystyle V_ {1} \ setminus S}$ then $\Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})$ ${\ displaystyle \ Phi ({\ mathcal {Q}}) \ geq \ Phi ({\ mathcal {P}})}$

Evidence

This follows from the inequality $(x+y)^{2}\leq {\frac {1}{\alpha }}x^{2}+{\frac {1}{\beta }}y^{2}$ ${\ displaystyle (x + y) ^ {2} \ leq {\ frac {1} {\ alpha}} x ^ {2} + {\ frac {1} {\ beta}} y ^ {2}}$ true at $\alpha +\beta =1$ ${\ displaystyle \ alpha + \ beta = 1}$ which entails inequality

{\frac {E(V_{1},V_{j})^{2}}{|V_{1}|}}\leq {\frac {E(S,V_{j})^{2}}{|S|}}+{\frac {E(V_{1}\setminus S,V_{j})^{2}}{|V_{1}\setminus S|}}

{\ displaystyle {\ frac {E (V_ {1}, V_ {j}) ^ {2}} {| V_ {1} |}} \ leq {\ frac {E (S, V_ {j}) ^ { 2}} {| S |}} + {\ frac {E (V_ {1} \ setminus S, V_ {j}) ^ {2}} {| V_ {1} \ setminus S |}}}

for splitting ${\mathcal {P}}'$ ${\ displaystyle {\ mathcal {P}} '}$ from the algorithm described in the previous section is true $\Phi ({\mathcal {P}}')>\Phi ({\mathcal {P}})+\Omega (\varepsilon ^{5})$ ${\ displaystyle \ Phi ({\ mathcal {P}} ')> \ Phi ({\ mathcal {P}}) + \ Omega (\ varepsilon ^ {5})}$

if the partition ${\mathcal {Q}}$ ${\ displaystyle {\ mathcal {Q}}}$ obtained from the partition ${\mathcal {P}}=(V_{1},\dots ,V_{k})$ ${\ displaystyle {\ mathcal {P}} = (V_ {1}, \ dots, V_ {k})}$ repartitioning the vertices of several components $V_{1},\dots ,V_{s}$ ${\ displaystyle V_ {1}, \ dots, V_ {s}}$ to some other components (not necessarily subdivision), then $\Phi ({\mathcal {Q}})\geq \Phi ({\mathcal {P}})-{\frac {|V_{1}|+\dots +|V_{s}|}{|V|}}$ ${\ displaystyle \ Phi ({\ mathcal {Q}}) \ geq \ Phi ({\ mathcal {P}}) - {\ frac {| V_ {1} | + \ dots + | V_ {s} |} { | V |}}}$

Evidence

It is enough to show that the union $V_{1},\dots ,V_{s}$ ${\ displaystyle V_ {1}, \ dots, V_ {s}}$ reduces $\Phi$ ${\ displaystyle \ Phi}$ no more than ${\frac {|V_{1}|+\dots +|V_{s}|}{|V|}}$ ${\ displaystyle {\ frac {| V_ {1} | + \ dots + | V_ {s} |} {| V |}}}$ (further subdivision does not reduce $\Phi$ ${\ displaystyle \ Phi}$ , according to another property).

When combining components from the sum $\Phi$ ${\ displaystyle \ Phi}$ some terms disappear and some new ones appear. Since all terms are positive, it suffices to consider those that disappear. The sum of such terms is easy to estimate:

$\sum \limits _{i=1}^{s}{\sum \limits _{j>i}{{\frac {|V_{i}||V_{j}|}{|V|^{2}}}d(V_{i},V_{j})}}\leq \sum \limits _{i=1}^{s}{|V_{i}|\sum \limits _{j>i}{\frac {|V_{j}|}{|V|^{2}}}}\leq {\frac {1}{|V|^{2}}}\sum \limits _{i=1}^{s}{|V_{i}|\sum \limits _{j=1}^{k}{|V_{j}|}}={\frac {|V_{1}|+\dots +|V_{s}|}{|V|}}$ ${\ displaystyle \ sum \ limits _ {i = 1} ^ {s} {\ sum \ limits _ {j> i} {{\ frac {| V_ {i} || V_ {j} |} {| V | ^ {2}}} d (V_ {i}, V_ {j})}} \ leq \ sum \ limits _ {i = 1} ^ {s} {| V_ {i} | \ sum \ limits _ {j > i} {\ frac {| V_ {j} |} {| V | ^ {2}}}} \ leq {\ frac {1} {| V | ^ {2}}} \ sum \ limits _ {i = 1} ^ {s} {| V_ {i} | \ sum \ limits _ {j = 1} ^ {k} {| V_ {j} |}} = {\ frac {| V_ {1} | + \ dots + | V_ {s} |} {| V |}}}$

Since when obtaining a new partition according to the algorithm in the subdivision ${\mathcal {P}}'$ ${\ displaystyle {\ mathcal {P}} '}$ rebuilt no more than $k2^{k-1}\left\lfloor {\frac {n}{{(k2^{k-1})}^{2}}}\right\rfloor \leq {\frac {n}{k2^{k-1}}}$ ${\ displaystyle k2 ^ {k-1} \ left \ lfloor {\ frac {n} {{(k2 ^ {k-1})} ^ {2}}} \ right \ rfloor \ leq {\ frac {n} {k2 ^ {k-1}}}}$ tops and since ${\frac {1}{k2^{k-1}}}<c\varepsilon ^{5}$ ${\ displaystyle {\ frac {1} {k2 ^ {k-1}}} <c \ varepsilon ^ {5}}$ at large enough $k$ ${\ displaystyle k}$ for any constant $c$ ${\ displaystyle c}$ , then from the properties of the potential function it follows that the algorithm stops after $O\left({\frac {1}{\varepsilon ^{2}}}\right)$ ${\ displaystyle O \ left ({\ frac {1} {\ varepsilon ^ {2}}} \ right)}$ steps.

In the first work on this subject, Szemerédi used a slightly different potential function ^[1] :

\Phi ({\mathcal {P}})={\frac {1}{|{\mathcal {P}}|^{2}}}\sum \limits _{1\leq i<j\leq |{\mathcal {P}}|}{d(V_{i},V_{j})^{2}}

{\ displaystyle \ Phi ({\ mathcal {P}}) = {\ frac {1} {| {\ mathcal {P}} | ^ {2}}} \ sum \ limits _ {1 \ leq i <j \ leq | {\ mathcal {P}} |} {d (V_ {i}, V_ {j}) ^ {2}}}

Despite the differences, both of these functions are united by the idea of averaging the squares of densities.

Estimating the size of a break

As follows from the description of the algorithm, the upper bound on the number of components in the partition on $n$ ${\ displaystyle n}$ -th iteration of the algorithm is expressed by the recurrence relation

a_{n}={a_{n}}^{2}2^{a_{n}-1}

{\ displaystyle a_ {n} = {a_ {n}} ^ {2} 2 ^ {a_ {n} -1}}

The number of iterations that the algorithm will work is estimated as $O\left({\frac {1}{\varepsilon ^{5}}}\right)$ ${\ displaystyle O \ left ({\ frac {1} {\ varepsilon ^ {5}}} \ right)}$ .

Therefore, the total number of components can only be estimated by the tower of exponents. $2^{2^{\cdot ^{\cdot ^{\cdot ^{k}}}}}$ ${\ displaystyle 2 ^ {2 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {k}}}}}}$ heights $O\left({\frac {1}{\varepsilon ^{5}}}\right)$ ${\ displaystyle O \ left ({\ frac {1} {\ varepsilon ^ {5}}} \ right)}$ .

Efficient Partition Search Algorithm

A typical mathematical proof of the Cemeredi lemma does not care about the computational complexity of the algorithm.

However, a group of five mathematicians in a separate work investigated the algorithmic aspect of finding the desired partition - in particular, they described an algorithm that allows you to find the partition $n$ ${\ displaystyle n}$ vertex graph in time $O(n^{2.376})$ {\ displaystyle O (n ^ {2.376})} at fixed $\varepsilon$ ${\ displaystyle \ varepsilon}$ and $m$ ${\ displaystyle m}$ . The running time of their algorithm is limited by the time of multiplication of two matrices $n\times n$ ${\ displaystyle n \ times n}$ consisting of zeros and ones. Also, the algorithm can be parallelized and executed in time. $O(\log {n})$ ${\ displaystyle O (\ log {n})}$ on polynomially dependent on $n$ ${\ displaystyle n}$ number of processors. ^[6]

Lower bound for the size of the required partition

In 1997, William Gowers showed that the estimate for the size of the number of components in the desired partition cannot be improved more than to the exponential tower $2^{2^{\cdot ^{\cdot ^{\cdot ^{k}}}}}$ ${\ displaystyle 2 ^ {2 ^ {\ cdot ^ {\ cdot ^ {\ cdot ^ {k}}}}}}$ heights $O\left({\log {\left({\frac {1}{\varepsilon }}\right)}}\right)$ ${\ displaystyle O \ left ({\ log {\ left ({\ frac {1} {\ varepsilon}} \ right)}} \ right)}$ . Namely, he showed that there always exists a graph, any partition of which into fewer parts does not satisfy the conditions of the lemma.

He considered an even more generalized concept. $(\varepsilon ,\delta )$ ${\ displaystyle (\ varepsilon, \ delta)}$ -regularities, where on a subset of shares of a bipartite graph $S\subset U,T\subset V$ ${\ displaystyle S \ subset U, T \ subset V}$ , the density deviation of which is limited by the definition, restrictions are imposed $|S|\geq \delta |U|,|T|\geq \delta |V|$ ${\ displaystyle | S | \ geq \ delta | U |, | T | \ geq \ delta | V |}$ instead $|S|\geq \varepsilon |U|,|T|\geq \varepsilon |V|$ ${\ displaystyle | S | \ geq \ varepsilon | U |, | T | \ geq \ varepsilon | V |}$ , and for him he also proved the existence of a counterexample.

Gowers used the probabilistic method to search for a counterexample, so his proof is not constructive . We considered weighted graphs with weights from the interval $(0;1)$ ${\ displaystyle (0; 1)}$ . For such graphs, we can consider a completely similar formulation of the lemma, where as the density $d(U,V)$ ${\ displaystyle d (U, V)}$ the sum of the weights of the edges will be considered instead of their number. By constructing a counterexample in the form of a weighted graph, Gowers also showed that a random graph generated by the Bernoulli scheme with edge probabilities corresponding to the weights in this weighted graph will, with high probability, be a counterexample for the usual lemma (moreover, with a high probability of density $d(U,V)$ ${\ displaystyle d (U, V)}$ will not deviate strongly from similar densities in the weighted graph, provided that $|U|$ ${\ displaystyle | U |}$ and $|V|$ ${\ displaystyle | V |}$ large enough). ^[7]

Gowers Design

Illustration of the type of graph structure used by Gowers to construct a counterexample. For convenience, the number of blocks

B_{i}

{\ displaystyle B_ {i}}

(in the picture they are visually distant from each other) and the size of the groups is chosen equal to three. Note that in each dicotyledonous subgraph formed between the blocks, vertices of the same color that are next to each other always fall in one share - these are the groups

X_{i}

{\ displaystyle X_ {i}}

in which the vertices are combined in advance. When constructing the next graph, the vertices of each individual block are combined into one such group.

Weighted graph serving as a counterexample for the lemma with the usual definition $\varepsilon$ ${\ displaystyle \ varepsilon}$ -regularity, is constructed as a combination with different weights of several specifically arranged large graphs. When constructing each next graph from this set, the vertices are combined into larger and larger groups of equal size such that the vertices from two different groups are either joined together by a complete bipartite graph or not connected at all (new groups are always a union of the previous ones).

Let the vertices be divided into groups $X_{1},\dots ,X_{s}$ ${\ displaystyle X_ {1}, \ dots, X_ {s}}$ the same size. Combine these groups into blocks.

B_{1}=(X_{1},\dots ,X_{t})

{\ displaystyle B_ {1} = (X_ {1}, \ dots, X_ {t})}

B_{2}=(X_{t+1},\dots ,X_{2t})

{\ displaystyle B_ {2} = (X_ {t + 1}, \ dots, X_ {2t})}

\dots

{\ displaystyle \ dots}

B_{k}=(X_{(m-1)t+1},\dots ,X_{s})

{\ displaystyle B_ {k} = (X _ {(m-1) t + 1}, \ dots, X_ {s})}

,

Where $k={\frac {s}{t}}$ ${\ displaystyle k = {\ frac {s} {t}}}$ (assuming this is an integer).

For each pair of different blocks $(B_{i},B_{j})$ ${\ displaystyle (B_ {i}, B_ {j})}$ choose a partition $B_{i}=B_{ij}^{(1)}\sqcup B_{ij}^{(2)}$ ${\ displaystyle B_ {i} = B_ {ij} ^ {(1)} \ sqcup B_ {ij} ^ {(2)}}$ groups from $B_{i}$ ${\ displaystyle B_ {i}}$ into two parts and splitting $B_{j}=B_{ji}^{(1)}\sqcup B_{ji}^{(2)}$ ${\ displaystyle B_ {j} = B_ {ji} ^ {(1)} \ sqcup B_ {ji} ^ {(2)}}$ groups from $B_{j}$ ${\ displaystyle B_ {j}}$ into two parts. Add to the graph all the edges of the complete bipartite graphs. $(B_{ij}^{(1)},B_{ji}^{(1)})$ ${\ displaystyle (B_ {ij} ^ {(1)}, B_ {ji} ^ {(1)})}$ and $(B_{ij}^{(2)},B_{ji}^{(2)})$ ${\ displaystyle (B_ {ij} ^ {(2)}, B_ {ji} ^ {(2)})}$ .

If you choose partitions in such a way that for any $X_{j},X_{j'}$ ${\ displaystyle X_ {j}, X_ {j '}}$ belonging to one $B_{i}$ ${\ displaystyle B_ {i}}$ was no more ${\frac {3}{4}}k$ ${\ displaystyle {\ frac {3} {4}} k}$ blocks in which there are vertices adjacent to both of them, then with the right selection $s$ ${\ displaystyle s}$ and $t$ ${\ displaystyle t}$ the resulting construction will be the Gowers construction. But this is a construction of only one graph - for the construction of the next graph, blocks $B_{1},\dots ,B_{m}$ ${\ displaystyle B_ {1}, \ dots, B_ {m}}$ put in place of groups $X_{1},\dots ,X_{s}$ ${\ displaystyle X_ {1}, \ dots, X_ {s}}$ and the whole process starts again until all the vertices are combined into one group.

The resulting graph chain $G_{1},\dots ,G_{s}$ ${\ displaystyle G_ {1}, \ dots, G_ {s}}$ combined into a weighted graph by the formula $G=\sum \limits _{r=1}^{s}{2^{r-s-1}G_{r}}$ ${\ displaystyle G = \ sum \ limits _ {r = 1} ^ {s} {2 ^ {rs-1} G_ {r}}}$ (graphs in which the combined vertex groups are very large have the largest weights).

Counterexample for $(\varepsilon ,\delta )$ ${\ displaystyle (\ varepsilon, \ delta)}$ -regularity is built in a similar way, but with several differences:

groups within one block $B_{i}$ ${\ displaystyle B_ {i}}$ not divided into two, into an arbitrary number $d$ ${\ displaystyle d}$ sets $B_{i}=B_{i}^{(1)}\sqcup \dots \sqcup B_{i}^{(d)}$ ${\ displaystyle B_ {i} = B_ {i} ^ {(1)} \ sqcup \ dots \ sqcup B_ {i} ^ {(d)}}$ ;

by the number of groups in each set $B_{i}^{(j)}$ ${\ displaystyle B_ {i} ^ {(j)}}$ size restrictions are imposed (they should not be too small);

at the end the resulting graphs $G_{1},\dots ,G_{s}$ ${\ displaystyle G_ {1}, \ dots, G_ {s}}$ are combined not in the form of a weighted graph, but by the excluding "or" (only those edges that were present in an odd number of columns are included in the final graph $G_{r},1\leq r\leq s$ ${\ displaystyle G_ {r}, 1 \ leq r \ leq s}$ )

Generalizations

In 2007, William Gowers generalized the regularity lemma to hypergraphs and used the generalization to prove the multidimensional Szemeredi theorem. ^[eight]

There is also an analogue of the Cemeredi lemma for sparse graphs (in the usual statement, the lemma is trivial for such graphs, since any decomposition satisfies the necessary conditions). ^[9]

Applications

It is best known to use the regularity lemma for the combinatorial proof of the Cemeredi theorem and its generalizations (e.g., corner theorems ). ^[5] However, the lemma and its ideas have a number of applications in the general theory of graphs ^[10] - the first article by Szemeredi on this lemma is cited in more than 500 works on a variety of topics. ^[one]

Also of particular interest is the lemma on the removal of triangles , which is deduced from the regularity lemma and is used in the proof of the Cemeredi theorem.

Notes

[Szemeredi_first-1] ¹ ² ³ ⁴ E. Szemeredi, "Regular partitions of graphs", Computer science department, School of Humanities and Sciences, Stanford University, 1975

[2] E. Szemeredi, "Regular partitions of graphs", Computer science department, School of Humanities and Sciences, Stanford University, 1975

[Prinston-3] ¹ ² ³ "Mini course of additive combinatorics", notes from Princeton University lectures

[4] Mathematical Laboratory Chebyshev, lecture course "Additive combinatorics", lecture 3

[Shkredov-5] ¹ ² I. D. Shkredov, "Cemeredi theorem and problems on arithmetic progressions"

[6] N. Alon, RA Duke, H. Lefmann, V. Rodl, R. Yusterk, "The Algorithmic Aspects of the Regularity Lemma", Tel Aviv University

[7] WT Gowers, "Lower bounds of tower type for Szemerédi's uniformity lemma", Geometric & Functional Analysis GAFA, May 1997, Volume 7, Issue 2, pp 322–337

[8] WT Gowers, "Hypergraph regularity and the multidimensional Szemer´edi theorem", Annals of Mathematics, 166 (2007), 897–946

[9] Y. Kohayakawa, "Szemerédi's Regularity Lemma for Sparse Graphs"

[10] Janos Komlos, Miklos Simonovits, "Szemeredi's Regularity Lemma and its applications in graph theory", Rutgers University, Hungarian Academy of Sciences

Szemeredi regularity lemma

Wording

The concept $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\varepsilon$ -uniformity

The statement of the lemma

Remarks

Proof

Partition Algorithm

Transition from subdivision to subdivision

Estimating the Number of Algorithm Steps

Estimating the size of a break

Efficient Partition Search Algorithm

Lower bound for the size of the required partition

Generalizations

Applications

See also

Notes

More articles:

Szemeredi regularity lemma

Wording

The conceptε {\ displaystyle \ varepsilon} -uniformity

The statement of the lemma

Remarks

Proof

Partition Algorithm

Transition from subdivision to subdivision

Estimating the Number of Algorithm Steps

Estimating the size of a break

Efficient Partition Search Algorithm

Lower bound for the size of the required partition

Generalizations

Applications

See also

Notes

More articles:

The concept $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\varepsilon$ -uniformity