Edge density of a bipartite graph ($d(A,B)$)

For disjoint nonempty vertex sets $A,B$, their edge density is

If a bipartite graph with parts $X,Y$ has at least $\delta |X||Y|$ edges, then the number of ordered tuples $(x_1,x_2,y_1,y_2)\in X^2\times Y^2$ for which every $x_i{y}_j$ is an edge is at leastIndeed, if $d(x_1,x_2)$ is the number of common neighbours of $x_1,x_2$ in $Y$, two applications of the Cauchy-Schwarz inequality give

This is the part-preserving homomorphism density of a four-cycle in a bipartite graph with independently uniform labels $x,x^{\prime }$ in the first part and $y,y^{\prime }$ in the second. Repeated labels are included. It equals the fourth power of the four-cycle norm of the adjacency indicator function. It differs at finite sizes from a count requiring four distinct vertices.

A pair $(A,B)$ is $\epsilon$-regular whenwhenever $X\subseteq A$, $Y\subseteq B$, $|X|\ge \epsilon |A|$, and $|Y|\ge \epsilon |B|$.

For fixed $r$ and positive density threshold $\lambda$, sufficiently regular pairwise dense bipartite graphs between $r$ disjoint equal-sized vertex classes contain at least $\delta n^r$ transversal cliques, for some $\delta >0$. A greedy embedding maintains common neighbourhoods and discards the small set of vertices with atypical degrees into them. The constants depend only on $r,\lambda$.

If three disjoint vertex classes have size $L$, and their three pairs are $\epsilon$-regular pairs of vertex sets of edge density of a bipartite graph at least $d$, where $0<\epsilon \le d/2$ and $\epsilon <1/2$, they contain at least the displayed number of transversal triangles in a graph. All but $2\epsilon L$ vertices in the first class have at least $(d-\epsilon )L$ neighbours in both other classes. Regularity between those two neighbour sets supplies the third edge. This strengthens a mere triangle embedding lemma for regular pairs to a cubic lower count.

Let $X=X_1\bigsqcup \cdots \bigsqcup X_r$ and $Y=Y_1\bigsqcup \cdots \bigsqcup Y_s$ be set partitions of the two parts of a bipartite graph. The pair of partitions is $\epsilon$-regular whenThus a uniformly random pair in $X\times Y$ lies in an irregular cell pair with probability at most $\epsilon$.

For every $\epsilon >0$ there is a positive integer $K(\epsilon )$ such that every finite bipartite graph has an $\epsilon$-regular pair of partitions with at most $K(\epsilon )$ cells on each side.

To prove this, give $X\times Y$ the uniform probability measure, let $f$ be the indicator function of the edge set, and for partitions $\mathcal{P},\mathcal{Q}$ define their energy byThis conditional expectation is an orthogonal projection, so $0\le \mathcal{E}\le \Vert f{\Vert }_2^2\le 1$. If the partitions are not $\epsilon$-regular, choose witnesses $A_{ij}\subseteq X_i$ and $B_{ij}\subseteq Y_j$ in every irregular cell pair and refine each $X_i$ by all its $A_{ij}$ and each $Y_j$ by all its $B_{ij}$. The refined energy exceeds the old energy byOn $A_{ij}\times B_{ij}$ the absolute value function of the mean of the difference is greater than $\epsilon$, while this rectangle occupies at least an ${\epsilon }^2$ fraction of $X_i\times Y_j$. The Cauchy-Schwarz inequality therefore contributes more than ${\epsilon }^4|X_i||Y_j|/(|X||Y|)$ from that cell pair. Irregular pairs have total weight greater than $\epsilon$, so every refinement raises the energy by more than ${\epsilon }^5$. The process stops after at most $\lceil {\epsilon }^{-5}\rceil$ refinements. If the current cell counts are $r,s$, the construction gives at most $r{2}^s,s{2}^r$ new cells, so a finite iterated bound depending only on $\epsilon$ supplies $K(\epsilon )$.

For every $\epsilon >0$ and $m_0$ there are $M,n_0$ such that every graph on at least $n_0$ vertices has a partitionwhere $m_0\le m\le M$, $|V_0|\le \epsilon |V|$, the other parts have equal size, and all but at most $\epsilon m^2$ pairs $(V_i,V_j)$ are $\epsilon$-regular.

For fixed forbidden induced patterns, a regularity and Ramsey refinement uses internal clique/independent types and sparse, almost-complete, or intermediate cross pairs. A clique of intermediate pairs realizes every bounded induced pattern consistent with those internal types, using both edge and nonedge regularity. This is the induced embedding consequence used in hereditary graph enumeration theorem; the exceptional-pair budget can be arbitrarily small.

For fixed $r\ge 2$ and every $\epsilon >0$, some $\delta >0$ has the following property for all sufficiently large $n$: a graph with fewer than $\delta n^r$ copies of $K_r$ can be made $K_r$-free by deleting at most $\epsilon n^2$ edges. A Szemerédi regularity lemma partition and the regular clique counting lemma prove this. It converts sparse counts of a forbidden clique into a small edit distance from clique-freeness.

For every $\eta >0$, some $\rho >0$ and $N_0$ have this property: a graph on $N\ge N_0$ vertices with fewer than $\rho N^3$ unordered triangles in a graph can be made triangle-free by deleting at most $\eta N^2$ edges. A Szemerédi regularity lemma partition deletes exceptional, intraclass, irregular and sparse-pair edges cheaply. A surviving triangle in a graph would force a positive cubic count by the regular triangle counting lemma.

For a set partition $\mathcal{P}$ of the vertices of a graph of order $n$, definewhere the sum is ordered, the adjacency indicator defines the density also on diagonal pairs, and exceptional vertices are treated as singleton parts. Refinement cannot decrease this energy, by the Cauchy-Schwarz inequality. An irregular pair of equal cells of size $m$, with witnesses of relative size at least $\epsilon$ and density discrepancy greater than $\epsilon$, increases the energy by more than ${\epsilon }^4{m}^2/n^2$ for each orientation. Splitting refined atoms into equal chunks and leftover singleton parts is a further refinement, so restoring equitability causes no energy loss.

In a proof of the Szemerédi regularity lemma, suppose $k$ equal classes have size $L$ and witness splitting creates at most $2^k$ atoms per class. Divide every atom into blocks of size $\ell =\lfloor L/4^k\rfloor$, putting leftovers into the exceptional set. At most $k{2}^k\ell \le kL{2}^{-k}$ vertices are lost. When $L\ge 2\cdot 4^k$, at most $2k{4}^k$ blocks remain. For equitable regularity energy defined by omitting exceptional vertices, the loss from discarding a fraction $r$ is at most $2r$: only ordered pairs incident with discarded vertices are removed, and every squared edge density of a bipartite graph is at most one. This provides a quantitative way to restore equal class sizes after each energy increment.

If a set partition refines a rectangle $U\times V$ of a graph into rectangles $U_a\times V_b$, write $d=d(U,V)$ for its edge density of a bipartite graph. The weighted variance identity isIt follows by expanding the square and using ${\sum }_{a,b}|U_a||V_b|d(U_a,V_b)=|U||V|d$. In particular, equitable regularity energy cannot decrease under refinement. If a witness rectangle has relative sizes at least $\epsilon$ and edge density of a bipartite graph discrepancy greater than $\epsilon$, its contribution, after division by the squared total vertex count, exceeds ${\epsilon }^4|U||V|/N^2$.

For every finite graph $H$ and density $\delta >0$, sufficiently large vertex classes joined according to $H$ by regular pairs of density at least $\delta$ contain a copy of $H$. The regularity parameter must be sufficiently small in terms of $H$ and $\delta$.

For any fixed odd length $\ell \ge 3$, positive triangle in a graph density forces positive density of $\ell$-cycles. A Szemerédi regularity lemma partition retains a triangle in a graph of regular dense pairs after the sparse and exceptional pairs are removed. Count embeddings of a proper three-colouring of $C_{\ell }$ into those three clusters. The constants depend on $\beta$ and $\ell$, not on graph order.

If the three pairs among vertex sets $A,B,C$ are $\epsilon$-regular and each has density at least $2\epsilon$, where $0<\epsilon <1/2$, then the graph contains a triangle with one vertex in each set.

Given a regularity partition and a density cutoff $\delta$, its reduced graph has one vertex for each nonexceptional class and joins two classes when their pair is regular and has density at least $\delta$.