[Szemeredi's regularity lemma](http://en.wikipedia.org/wiki/Szemer%C3%A9di_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?


  



Remarks:


  



Concerning question 1, the closest thing I have found is Section 2.1.2 of [this](https://www.ime.usp.br/~yoshi/MSs/Fortaleza/school10.pdf) 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. 



irregular pairs in half graphs - Szemeredi regularity
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


<http://arxiv.org/pdf/1107.4829v1.pdf>


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).


