Regular Pairs and Induced Counting — Examples

In the complete case, [L2] gives $d(X,Y)=1$, and every nonempty subpair $(A,B)$ also has density $1$.

In the anticomplete case, [L2] gives $d(X,Y)=0$, and every nonempty subpair has density $0$.

Thus the density difference is zero in either case, which is exactly the $0$-regular convention in [L1].

The number of cross-edges is $n+(n-1)+\cdots +1=n(n+1)\mathrm{/}2$, so $d(X_n,Y_n)=(n+1)\mathrm{/}(2n)$.

Put $q=\lceil n\mathrm{/}4\rceil$, $A=\{a_1,\dots ,a_q\}$, and $B=\{b_{n-q+1},\dots ,b_n\}$. Then $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge n\mathrm{/}4>n\mathrm{/}5$, and every $a_i\in A$ satisfies $i\le j$ for every $b_j\in B$, so $d(A,B)=1$.

For $n\ge 4$, one has $\mathrm{\mid }d(A,B)-d(X_n,Y_n)\mathrm{\mid }=(n-1)\mathrm{/}(2n)\ge 3\mathrm{/}8>1\mathrm{/}5$. Together with the size bounds in step 1.2, [L1] shows that $(X_n,Y_n)$ is not $1\mathrm{/}5$-regular.

Substitute $ϵ=1\mathrm{/}100$ and $\alpha =\beta =1\mathrm{/}2$ in [L1]. Each of $ϵ\mathrm{/}\alpha$, $ϵ\mathrm{/}\beta$, and $2ϵ$ equals $1\mathrm{/}50$.

The same application of [L1] retains the density-shift bound $1\mathrm{/}100$, proving both decimal-form assertions in the Statement.

For the one-part partition, the ordered-pair density is $d(V,V)=2m\mathrm{/}{n}^2$, so [L1] gives energy $(2m\mathrm{/}{n}^2{)}^2$.

In the singleton partition, an ordered pair of distinct singleton parts has squared density $1$ exactly when its two vertices are adjacent; diagonal densities and nonedge densities are $0$. Every edge contributes its two orientations, so [L1] gives energy $2m\mathrm{/}{n}^2$.

Since $0\le 2m\mathrm{/}{n}^2\le 1$, its square is no larger than itself, agreeing with [L2] because the singleton partition refines the trivial one. The null case is the convention in [L1].

By [L2], each cross-pair has density $1$. Every nonempty subpair is also complete and has density $1$, so each pair is $0$-regular by [L3].

Every $(x,y,z)\in X\times Y\times Z$ has all three required edges and therefore spans a triangle. Conversely, each ordered transversal triangle is one such product choice, giving exactly $\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }\mathrm{\mid }Z\mathrm{\mid }$.

Substitution $a=b=c=1$ and $ϵ=0$ into [L1] yields the same lower bound $\mathrm{\mid }X\mathrm{\mid }\mathrm{\mid }Y\mathrm{\mid }\mathrm{\mid }Z\mathrm{\mid }$, so the bound is exact here.

Every triple $(x_1,x_2,x_3)$ in the product has edges $x_1{x}_2,x_2{x}_3$ and nonedge $x_1{x}_3$. By [L3] it induces the labelled path $1-2-3$.

Conversely every part-respecting labelled triple is one of these product choices, so their number is exactly $\mathrm{\mid }{X}_1\mathrm{\mid }\mathrm{\mid }{X}_2\mathrm{\mid }\mathrm{\mid }{X}_3\mathrm{\mid }$.

The two complete pairs have density $1$ and the anticomplete pair density $0$; every nonempty subpair retains its density. Hence [L2] gives $0$-regularity, making this the zero-error model of [L1].

Join $X$ to $Y$ and $Y$ to $Z$ exactly when the endpoint labels agree, and join $X$ to $Z$ exactly when their labels differ.

For each cross-pair and each vertex, exactly half the vertices on the other side are neighbours. Thus all three densities are $1\mathrm{/}2$ by [L1].

Suppose, for contradiction, that $(x,y,z)$ is a transversal triangle. Its $XY$ and $YZ$ edges force the three labels to satisfy $x=y=z$, while its $XZ$ edge forces $x\mathrm{\ne }z$.

This contradiction shows that no transversal triangle exists. Therefore density alone does not imply the conclusion of [L2]; its regularity hypothesis carries real content.

Begin with $K_n$, choose a triple $S$, and delete exactly its three internal edges. By [L2] and [L3], $S$ induces the empty three-vertex graph.

It is the unique unlabelled empty triple: every triple other than $S$ contains a vertex outside $S$, and that vertex is adjacent to both other vertices.

Deleting more edges never changes any of the three nonedges within $S$ into an edge, so the induced empty triple on $S$ survives every deletion-only operation.

Adding any one of the three missing edges within $S$ destroys this copy, and step 2.1 shows the resulting graph has no empty triple. Thus allowing additions, as [L1] does, is indispensable.