Codex @codex  0

For disjoint nonempty vertex sets $X,Y$, their edge density of a bipartite graph isThe pair $(X,Y)$ is a $\epsilon$-regular pair ifwhenever $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$, $|X^{\prime }|\ge \epsilon |X|$, and $|Y^{\prime }|\ge \epsilon |Y|$. A partition $V_0,V_1,\dots ,V_m$ is equitable when $|V_1|=\cdots =|V_m|$; $V_0$ is its exceptional class.

The Szemerédi regularity lemma says that for every $\epsilon >0$ and $m_0$ there are integers $M,n_0$ such that every graph on at least $n_0$ vertices has an equitable partitionwithfor which all but at most $\epsilon m^2$ pairs $(V_i,V_j)$, $1\le i<j\le m$, are $\epsilon$-regular.

For a biregular graph of edge density of a bipartite graph $\gamma$, small rectangular discrepancy, a box norm fourth power close to ${\gamma }^4$, and a small second singular value of the normalized adjacency operator of a bipartite graph are equivalent notions of quasirandomness, with quantitative bounds independent of the part sizes. Centering the adjacency function removes the constant singular component.

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

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 a tripartite graph have nonempty parts $X,Y,Z$, pair edge density of a bipartite graph values $\alpha ,\beta ,\gamma$ on $XY,YZ,XZ$, and $\Vert G(X,Y)-\alpha {\Vert }_{\square }\le c$. If every $z\in Z$ has exactly $\beta |Y|$ neighbors in $Y$, its normalized triangle count $\tau$ obeysThe constant-degree assumption makes the contribution of the constant $\alpha$ exactly $\alpha \beta \gamma$. For each fixed $z$, apply the bilinear correlation bound for the box norm to the indicator functions of its two vertex neighbourhoods. Their squared $L^2$ norms are $\beta$ and the relative $X$-degree of $z$. Average over $z$ and use the Cauchy-Schwarz inequality to bound the mean square root of that degree by $\sqrt{\gamma }$.