Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just refer to the the Wikipedia link.

My question is about the part of the lemma saying "all except $\epsilon k^2$ of the pairs $V_i$, $V_j$ are $\epsilon$-pseudo random". (Note: "pseudo-random" and "regular" seem to be somewhat interchangeable in this context.) Concerning the necessity of these "irregular" pairs, a frequently cited example is the "half-graph".

In particular, given $n>0$, the half-graph of height $n$, $H_n$, is described as follows:

  • $V(H_n)=\{v_1,\ldots,v_n,w_1,\ldots,w_n\}$,

  • given, $1\leq i,j\leq n$, $(v_i,w_j)\in E(H_n)$ if and only if $i\leq j$,

  • no other edges are present in $H_n$ (so $(\{v_1,\ldots,v_n\},\{w_1,\ldots,w_n\})$ is a bipartition for $H_n$).

The graphs $H_n$ were the first observed example of where irregular pairs in Szemeredi's Lemma are necessary. I have two questions about this.

1) What is the precise statement of this claim about irregular pairs in half graphs?

2) Is there a source where this claim is explained in detail?


Concerning question 1, the closest thing I have found is Section 2.1.2 of this survey paper, which says:

"The reader is invited to prove that, for small enough $\epsilon>0$, any $(\epsilon,k)$-equitable, $\epsilon$-regular partition of $H_n$ requires at least $ck$ $\epsilon$-irregular pairs, where $c=c(\epsilon)>0$ is some constant that depends only on $\epsilon$."

But I am still uncertain on exactly how $n$ and $k$ are being quantified in this statement. My best guess is:

"For any small enough $\epsilon>0$, there is $c=c(\epsilon)>0$ such that for all $k$ there is some large enough $n$ such that any $(\epsilon,k)$-equitable, $\epsilon$-regular partition of $H_n$ requires at least $ck$ $\epsilon$-irregular pairs."

Concerning question 2, I have only found sources that mention half-graphs as examples of irregular pairs. So it would be nice to know if this is worked out in detail somewhere.


Your guess at the quantification for (1) is correct. I don't know anywhere where this is explicitly worked out. It is a fairly tedious analysis, more or less you need to argue that the partition sets essentially respect the bipartition and that if a part among the $v_i$ isn't adjacent to any irregular pairs then its largest and smallest elements in the $v_i$ are not too far apart and the corresponding interval in the $w_j$ is split among too many parts to apply regularity. From this you conclude that either you have the desired irregular pairs or that the parts among the $v_i$ are closer to linear order than those in the $w_j$, and then you conclude that each part in the $w_i$ gives you an irregular pair.

However there is now a stronger statement available: in


the authors construct graphs needing about as many irregular pairs as the Regularity Lemma will give you (one can take $\varepsilon$ to be something like $\log_* k$) in the Regularity Lemma).

  • $\begingroup$ I didn't understand what you've said. How to find irregular pairs? How to find just one? $\endgroup$ – leticia May 10 '17 at 18:21

It is worth mentioning that in a strong sense half-graphs are the only thing which can cause irregular pairs. In the paper Regularity lemma for stable graphs by Malliaris and Shelah it is shown that when you bound the size of the half-graphs which can occur in your graph four remarkable things happen:

(1) Irregular pairs are not needed.

(2) The density of edges across regular pairs is very close to either 0 or 1, i.e. for any regular pair "almost surely" there is an edge connecting any two elements or "almost surely" there is no edge connecting two elements.

(3) Every element of the partition is very close to either a complete graph or an independent set.

(4) Then number of pieces needed to get an epsilon-regular partition is only approximately (1/epsilon)^k where k depends on the maximum size of the half graph which can exist.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.