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 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 Answer

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

Browse other questions tagged or ask your own question.