What continuous object represents a sequence of increasingly large graphs?
Consider the balanced complete bipartite graphs $G_m=K_{m,m}$. Their sizes grow, but their structure is unchanged: split the vertices into two equal parts, join every cross-part pair, and include no internal edges. A picture of a large adjacency matrix suggests a continuous object. Replace its equal vertex intervals by coordinates in $[0,1]$ and define
$$W(x,y)=\begin{cases}1,&x\lt1/2\le y\text{ or }y\lt1/2\le x,\\ 0,&\text{otherwise}.\end{cases}$$
The values on boundary lines do not matter for integrals. This symmetric measurable function $W:[0,1]^2\to[0,1]$ is a graphon. It records connection intensity between positions rather than an edge between named vertices. In this example the intensity is always zero or one; other graphons can have fractional values.
For a finite simple graph $F$, a homomorphism to a graph $G$ sends vertices to vertices while preserving edges; distinct source vertices may have the same image. Define
$$t(F,G)=\frac{\operatorname{hom}(F,G)}{\lvert V(G)\rvert^{\lvert V(F)\rvert}}.$$
Equivalently, sample one uniform vertex independently for every vertex of $F$, with replacement, and ask whether all required edges exist. The graphon version samples independent uniform points and multiplies the required intensities:
$$t(F,W)=\int_{[0,1]^{V(F)}}\prod_{ij\in E(F)}W(x_i,x_j)\,\prod_{i\in V(F)}dx_i.$$
For a step graphon made from a finite adjacency matrix, these two definitions agree exactly. They need not equal the probability of finding the pattern on distinct sampled vertices.
For $G_m$, an edge homomorphism has $2m^2$ possibilities, hence $t(K_2,G_m)=1/2$. A three-vertex path has $2m^3$ possibilities, giving density $1/4$. A four-cycle has $2m^4$ homomorphisms, giving $1/8$; opposite cycle vertices may coincide. Triangles have density zero. The same integrals hold for $W$, so this graphon represents the whole sequence without storing ever larger matrices.
The foundation of this chapter consists of this explicit graphon, the sampling definition, and the exact motif calculations. They suffice for the core investigation; all numbered research sections are optional. Earlier connections are extremal graphs, random structures, spectral combinatorics, and modern extremal methods.
What continuous object represents a sequence of increasingly large graphs?
Use $K_{3,3}$ with vertex parts $\{0,1,2\}$ and $\{3,4,5\}$. It has nine edges, but the homomorphism edge density is $18/36=1/2$, whereas distinct unordered-pair edge density is $9/15=3/5$.
For a four-cycle, there are $2\cdot3^4=162$ homomorphisms and $6^4=1296$ maps, so $t(C_4,G)=1/8$. There are only $2\cdot3\cdot2\cdot3\cdot2=72$ injective homomorphisms, out of $6\cdot5\cdot4\cdot3=360$ injective maps, giving $1/5$. There are nine unlabeled four-cycles, each contributing eight injective maps.
Question to revisit. What data distinguishes this graphon from the constant graphon $W\equiv1/2$? Solution: both have edge density $1/2$ and path density $1/4$. Their triangle densities are zero versus $1/8$, and their four-cycle densities are $1/8$ versus $1/16$. Edge density and average degree alone do not identify a limit object.
47.1 Dense graph sequences
Optional extension; not required to complete the chapter foundation.
A sequence $(G_n)$ with vertex counts tending to infinity is left-convergent if $t(F,G_n)$ converges for every fixed finite simple graph $F$. Here “dense” names the normalization and framework; it does not require every convergent sequence to have positive limiting edge density. Sparse sequences can converge to zero and lose their interesting structure in this framework.
The established Lovász–Szegedy limit theorem says that a left-convergent sequence has a graphon $W$ with $t(F,G_n)\to t(F,W)$ for every $F$. Conversely, every graphon arises as such a limit. The object is unique up to weak isomorphism, meaning zero cut distance, rather than a unique pointwise function on a fixed labeling of the interval.
Proof sketch and omitted prerequisites. Approximate each graph by a bounded-complexity step function using weak regularity; select convergent subsequences of the approximations; pass the motif densities through the approximation. Compactness and the representation/uniqueness theorem require measure theory and the cut-metric machinery, not just pointwise convergence of adjacency entries. Their full proofs are omitted.
Solved example. For $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$, order the two parts consecutively and let $a_n=\lfloor n/2\rfloor/n$. Its graphon has cross blocks at the split $a_n$. Moving the split to $1/2$ changes the function only on strips of total area at most $2\lvert a_n-1/2\rvert\le1/n$. Thus its $L^1$ distance to the balanced graphon tends to zero. Telescoping a product of edge factors shows that a fixed motif's density changes by at most $e(F)$ times that $L^1$ distance. This proves convergence in this example without invoking the general existence theorem.
A dense graph limit records all fixed homomorphism densities under the $N^{v(F)}$ normalization. Relabelings do not change these densities, and sparse graphs may collapse to the zero graphon under this normalization.
Exercise. Does alternating $K_{m,m}$ and constant-density random graphs with limiting density $1/2$ produce a left-convergent sequence? Hint: compare triangle densities. Solution: not in general: the bipartite subsequence has triangle density zero while a typical $G(N,1/2)$ subsequence has triangle density tending to $1/8$. Matching edge density does not repair the disagreement.
47.2 Graphons and homomorphism densities
Optional extension; not required to complete the chapter foundation.
Let $\mu$ denote Lebesgue measure. A graphon is symmetric almost everywhere and has values in $[0,1]$. Its degree function is $d_W(x)=\int_0^1W(x,y)\,dy$. Then $t(K_2,W)=\int d_W$ and $t(P_3,W)=\int d_W^2$, where $P_3$ is the two-edge path. The latter identity follows by integrating independently over its two leaves.
For induced densities, include nonedge factors as well:
$$t_{\mathrm{ind}}(F,W)=\int\prod_{ij\in E(F)}W(x_i,x_j)\prod_{ij\notin E(F),\ i\lt j}(1-W(x_i,x_j))\,dx.$$
This formula describes a specific labeled adjacency pattern. The probability of an unlabeled isomorphism type is its labeled density multiplied by $v(F)!/\lvert\operatorname{Aut}(F)\rvert$. This conversion is essential in flag-coefficient tables. The graphon formulas and their probabilistic interpretation are established in Lovász–Szegedy.
Graphons and homomorphism densities: a worked example
Let $W_a$ be one on cross pairs of a partition with masses $a$ and $1-a$, and zero within parts, where $0\lt a\lt1$. A connected bipartite motif with specified bipartition sizes $s,t$ has density
$$a^s(1-a)^t+a^t(1-a)^s.$$
There are exactly two ways to assign its bipartition to the two graphon parts. Applying this rule gives
$$t(K_2,W_a)=2a(1-a),\quad t(P_3,W_a)=a(1-a),\quad t(C_4,W_a)=2a^2(1-a)^2.$$
At $a=1/3$ these are $4/9,2/9,8/81$; triangle density is zero because three graphon positions cannot be pairwise in different parts.
For the three-vertex induced type distribution, the empty type has probability $a^3+(1-a)^3$, the one-edge type has probability zero, and the path type has probability $3a(1-a)$. At $a=1/2$, these are $1/4,0,3/4$. They sum to one. This is the graphon sampling distribution, not the distinct-three-vertex distribution of a small finite graph.
Exercise. Compute $t(K_2,W)$ and $t(K_3,W)$ for constant $W\equiv p$. Hint: every required edge contributes $p$. Solution: the answers are $p$ and $p^3$; more generally $t(F,W)=p^{e(F)}$. An induced labeled pattern also contributes $(1-p)$ for each required nonedge.
47.3 Cut distance and convergence
Optional extension; not required to complete the chapter foundation.
For an integrable kernel $U$, define the cut norm
$$\lVert U\rVert_\square=\sup_{S,T\subseteq[0,1]}\left\lvert\int_{S\times T}U(x,y)\,dx\,dy\right\rvert,$$
where $S,T$ are measurable. The sets may overlap. It measures the largest discrepancy on a rectangle. For graphons $W,V$, define $\delta_\square(W,V)=\inf_\phi\lVert W-V^\phi\rVert_\square$, where $V^\phi(x,y)=V(\phi(x),\phi(y))$ and $\phi$ ranges over measure-preserving bijections, modulo null sets. Equivalent pullback definitions handle weak isomorphism. Zero cut distance need not mean pointwise equality.
The established Borgs–Chayes–Lovász–Sós–Vesztergombi theorem makes convergence of all fixed homomorphism densities equivalent to cut-metric convergence to a graphon. Graphons modulo zero distance form a compact metric space. Proof scope: compactness and the general counting/uniqueness estimates are omitted; an elementary exact relabeling example follows.
Solved example. Divide the interval into four equal cells. One balanced bipartite graphon has part pattern $A,A,B,B$; another has part pattern $A,B,A,B$. Their values are the binary matrices in the SVG. Under the displayed labeling their difference has cut norm $1/8$: the first two cells in both coordinates attain it, and enumerating all sixteen cell unions for each axis verifies the upper bound. Fractional portions of cells cannot improve the supremum, since the objective is bilinear and an extremum occurs at cell-union endpoints. Swap cells two and three in both axes to make the matrices identical. Thus their cut distance is zero despite a positive aligned cut norm.
For contrast, the balanced bipartite graphon and $V\equiv1/2$ have cut distance $1/8$. Write their difference as $-r(x)r(y)/2$, with $r=1$ on the first half and $r=-1$ on the second. The largest absolute integral of $r$ on a measurable set is $1/2$, so the cut norm is $1/8$. Relabeling the bipartition does not change that value against a constant graphon. Their $L^1$ distance is $1/2$; cut distance measures a different notion of closeness.
Exercise. Why can relabeling only rows of a graphon's matrix break the interpretation? Hint: check symmetry. Solution: vertex relabeling acts on both coordinates by the same map. A row-only permutation may produce a nonsymmetric kernel and does not represent relabeling an undirected graph.
47.4 Quasirandom graph characterizations
Optional extension; not required to complete the chapter foundation.
The constant graphon $W\equiv p$ represents dense quasirandomness at density $p$. A central established Chung–Graham–Wilson theorem says that edge density tending to $p$ together with four-cycle homomorphism density tending to $p^4$ forces the graph sequence to converge to this constant graphon. Equivalent formulations control all cuts and all fixed subgraph densities. This is a dense asymptotic characterization, with $p$ fixed; it is not a sparse relative-count theorem.
The basic inequality can be proved at the graphon level. Put $c(x,y)=\int W(x,z)W(y,z)\,dz$ and $p=\int W$. Then
$$t(C_4,W)=\int c(x,y)^2\,dx\,dy\ge\left(\int c(x,y)\,dx\,dy\right)^2=\left(\int d_W(z)^2\,dz\right)^2\ge p^4.$$
Both inequalities are Cauchy–Schwarz on probability spaces. Proof sketch and omitted prerequisite for the characterization: equality forces the relevant degree and codegree fluctuations to vanish, and the operator/counting argument identifies $W$ with the constant graphon up to zero cut distance. The full equivalence proof is not reproduced; proving the inequality alone does not prove quantitative stability near equality.
Solved example. The balanced bipartite graphon has $p=1/2$ but $t(C_4)=1/8$, twice the constant graphon's value $1/16$. Its degree function is constant $1/2$, so the second inequality is equality. The failure comes from codegrees: $c=1/2$ for same-part pairs and zero for cross-part pairs. Degree regularity alone does not give quasirandomness.
Exercise. Evaluate the first inequality in this example. Hint: same-part pairs have total measure one-half. Solution: $\int c^2=(1/2)(1/4)=1/8$, while $(\int c)^2=(1/4)^2=1/16$. The strict gap records variation in common-neighbor intensity.
47.5 Sparse graph limits
Optional extension; not required to complete the chapter foundation.
If a graph sequence has $e(G_n)=o(N_n^2)$, its adjacency graphon has $L^1$ norm $2e(G_n)/N_n^2\to0$. It therefore converges to zero in cut norm. For every fixed motif with at least one edge, $t(F,G_n)\le t(K_2,G_n)$, because the product of required edge indicators is at most any one factor. Dense normalization then erases all these densities.
Sparse theories choose what information to preserve. For graphs with growing but subquadratic edge counts, one may rescale the adjacency graphon by its edge density and study an unbounded kernel. Compactness requires integrability or uniform control of concentrated dense regions; normalizing the mean alone is insufficient. The established $L^p$ sparse graph-limit theory of Borgs, Chayes, Cohn, and Zhao states hypotheses suited to this regime. For bounded-degree graphs, rooted local weak limits preserve neighborhoods instead. There is no single universally interchangeable sparse limit object.
Solved example. An $N$-cycle has $N$ edges and homomorphism edge density $2/N$. A perfect matching has $N/2$ edges and density $1/N$. Both converge to the zero dense graphon. Yet every vertex in the cycle has degree two and every vertex in the matching has degree one; their local weak limits distinguish them immediately.
Proof scope: collapse under the dense normalization has been proved here. The existence and compactness results for rescaled sparse kernels are cited, with their full integrability machinery omitted. It would be incorrect to infer their applicability merely from $e(G_n)=o(N_n^2)$.
Exercise. Does dividing a graphon's values by its vanishing edge density keep it within $[0,1]$? Hint: inspect a present edge cell. Solution: that cell has value $1/p_n$, which diverges when $p_n\to0$. The result is no longer an ordinary bounded graphon; its limit theory must explicitly allow such kernels and control their mass.
47.6 Local weak convergence
Optional extension; not required to complete the chapter foundation.
Choose a root uniformly from a finite graph's vertices. For radius $R$, inspect the rooted induced ball of vertices at distance at most $R$. A bounded-degree graph sequence converges locally weakly if, for every fixed $R$ and every finite rooted ball type, the probability of seeing that type converges. The limit is a probability distribution on rooted locally finite graphs, not a uniform choice from an infinite vertex set.
This framework is established in Benjamini and Schramm's distributional-limit paper. A uniform degree bound gives finitely many rooted ball types at each fixed radius, allowing subsequential compactness by a diagonal argument. Compatibility of the ball distributions yields a rooted limit law. Proof scope: the examples below are direct; the full extension of compatible laws and the paper's deeper planar recurrence theorem are not proved here.
Solved example. For a cycle $C_N$, if $N\gt2R+1$, every radius-$R$ ball is a path of $2R+1$ vertices with root at its midpoint. Thus $C_N$ tends locally to the doubly infinite path. For paths $P_N$, at most $2R$ roots lie near an endpoint, so the same limit follows. For perfect matchings, every rooted ball of radius at least one is a single rooted edge, giving a different limit.
Local convergence does not automatically retain global connectivity, cut structure, or the finite graph's diameter. For example, one long cycle and the disjoint union of two cycles each of growing length have the same local limit despite different component counts. Random fixed-degree regular graphs tend locally to the infinite regular tree: for a fixed-radius exposure, collisions become rare as $N$ grows. This is an established probabilistic statement, distinct from a deterministic assertion about every regular graph sequence.
Exercise. For $P_N$, bound the probability that a radius-$R$ ball differs from the midpoint-rooted infinite-path ball. Hint: count endpoint-near roots. Solution: it is at most $2R/N$, assuming $N\ge2R+1$. This explicit error tends to zero for fixed $R$; letting $R$ grow proportionally to $N$ changes the conclusion.
47.7 Exchangeable random structures
Optional extension; not required to complete the chapter foundation.
An infinite random graph on labeled vertices $1,2,\ldots$ is vertex-exchangeable if its law is invariant under every finite permutation of vertex labels. A fixed graphon generates such a law: sample independent $U_i\sim\operatorname{Unif}[0,1]$, then, conditional on those positions, sample edges independently with probabilities $W(U_i,U_j)$. Edge probabilities are conditionally independent, but edges sharing a vertex need not be independent after the positions are forgotten.
The established exchangeable-array representation gives every exchangeable simple-graph law as a mixture of graphon sampling laws, allowing a global random parameter. A fixed graphon corresponds to a dissociated law, with independence of induced graphs on disjoint vertex sets. A nontrivial mixture can retain dependence even between disjoint edges. See the primary graph-limit/exchangeability treatment of Diaconis and Janson. Omitted prerequisites: the Aldous–Hoover representation theorem and the measurable decomposition into extremal exchangeable laws.
Solved example. Sample the balanced bipartite graphon. Vertex part labels are independent fair bits, and edges connect unequal labels. Any individual edge has probability $1/2$. Two edges sharing a vertex have joint probability $1/4$, so they are pairwise independent. However, all three edges of a triangle are never present. The three edge indicators are not jointly independent. This law is exchangeable even though it contains a latent two-part structure.
For a mixture contrast, choose with equal probability the constant graphon zero or the constant graphon one. Each edge has marginal probability $1/2$, but two disjoint edges are both present with probability $1/2$, not $1/4$. The global random choice must not be omitted from the representation.
Exercise. For the bipartite graphon, compute the probability exactly two of the three triangle-position edges are present. Hint: classify the three part labels. Solution: all labels agree with probability $1/4$, giving zero edges. Otherwise they split two-one, giving exactly two edges, with probability $3/4$. One or three edges have probability zero.
47.8 Flag algebras
Optional extension; not required to complete the chapter foundation.
Flag algebras organize identities between induced pattern densities and nonnegative expressions obtained from rooted sampling. A type specifies labeled root structure; a flag extends it by additional unlabeled vertices. Products sample two extensions sharing the roots, and averaging forgets the root labels. The formal quotient records consistency under enlarging the sample. The established framework is Razborov's Flag Algebras.
A complete small model needs only one root and one extra vertex. There are two flags: $E$, where the extra vertex is adjacent to the root, and $N$, where it is not. At graphon position $x$, their conditional probabilities are $f_E(x)=d_W(x)$ and $f_N(x)=1-d_W(x)$. Thus averaging a square gives
$$s=\int(f_E-f_N)^2\,dx=\int(2d_W(x)-1)^2\,dx\ge0.$$
Let $a,b,c,z$ be the probabilities that a graphon sample on three positions produces, respectively, the empty graph, one edge, a two-edge path, or a triangle. These are unlabeled type probabilities and sum to one. If $p=t(K_2,W)$, then $p=(b+2c+3z)/3$, while root averaging gives
$$s=a-\frac b3-\frac c3+z.$$
To verify the coefficients, uniformly choose the root among the three vertices of each type and multiply the signs of its adjacency to the other two. The empty type always gives $+1$. In either the one-edge or path type, one root gives $+1$ and two give $-1$, averaging to $-1/3$. A triangle always gives $+1$.
Solved example. For the balanced bipartite graphon, $(a,b,c,z)=(1/4,0,3/4,0)$, so $s=0$, consistent with constant degree $1/2$. A positive semidefinite square can have negative coefficients on some individual sampled graph types; only its averaged evaluation must be nonnegative. This is why coefficient inspection and positivity verification are separate steps.
Proof scope: the rooted calculation is supplied in full and agrees with the one-root flag interpretation. The general quotient algebra, product rules for larger types, and positivity of all limit evaluations are omitted. Finite flags sampled without replacement have collision corrections; do not identify their products exactly with independent graphon extensions at fixed finite size.
Exercise. In $K_{3,3}$, what is the empty-type probability when three distinct vertices are sampled? Hint: all three must lie in one part. Solution: it is $2\binom33/\binom63=1/10$, rather than the graphon value $1/4$. The corresponding distinct-sample sign average is $(4/10-1)/3=-1/5$. It is not the nonnegative independent-extension square $s=0$; the sampling convention has changed.
47.9 Semidefinite bounds for extremal problems
Optional extension; not required to complete the chapter foundation.
A matrix $Q$ is positive semidefinite if $v^{\mathsf T}Qv\ge0$ for every real vector $v$. For a vector of rooted flag probabilities, averaging this quadratic expression supplies an inequality valid for every admissible limit. Semidefinite programming searches for matrices and coefficient combinations that certify a target bound. A numerical optimum is a candidate certificate; rigorous certification needs exact or explicitly controlled positivity and coefficient identities.
Here is an exact certificate for the triangle-free graphon bound $p\le1/2$. Use flags ordered $(E,N)$ and
$$Q=\begin{pmatrix}1&-1\\ -1&1\end{pmatrix}=\begin{pmatrix}1\\ -1\end{pmatrix}\begin{pmatrix}1&-1\end{pmatrix}.$$
Its eigenvalues are zero and two, and its averaged evaluation is $s$. The exact identity for all graphons is
$$\frac12-p=\frac12s+\frac13b-z.$$
Verify it type by type:
| Three-vertex type | Edge coefficient $p$ | Square coefficient $s$ | Coefficient in $\frac12s+\frac13b-z$ |
|---|---|---|---|
| Empty | $0$ | $1$ | $1/2$ |
| One edge | $1/3$ | $-1/3$ | $1/6$ |
| Path | $2/3$ | $-1/3$ | $-1/6$ |
| Triangle | $1$ | $1$ | $-1/2$ |
The final column is precisely the coefficient of $1/2-p$ in every row. In a triangle-free graphon, $z=t(K_3,W)=0$, so the right-hand side is a nonnegative square plus a nonnegative density. This proves $p\le1/2$ without an optimizer. It is a small flag-algebra-style semidefinite certificate within the established Razborov framework.
Solved example. For $W_{1/3}$, $p=4/9$, $b=z=0$, and $s=1/9$. The identity gives $1/2-4/9=(1/2)(1/9)=1/18$. For the balanced graphon all terms vanish. Applied to the step graphon of a finite triangle-free graph, it proves $2e(G)/N^2\le1/2$, hence $e(G)\le\lfloor N^2/4\rfloor$. The graphon's with-replacement convention makes this finite consequence exact.
Exercise. Why is checking just the diagonal entries of a proposed $Q$ inadequate? Hint: examine $\begin{pmatrix}1&2\\ 2&1\end{pmatrix}$. Solution: its eigenvalues are three and minus one, so it is not positive semidefinite despite positive diagonals. A factorization such as $Q=R^{\mathsf T}R$ supplies a direct exact positivity witness; blindly rounding a numerical matrix may destroy it.
47.10 Graph-limit applications and extremal stability
Optional extension; not required to complete the chapter foundation.
A graph-limit extremal problem maximizes a continuous density functional over graphons satisfying forbidden-density constraints. Compactness ensures a maximizer exists when the constraint set is closed. If the maximizer is unique modulo zero cut distance, near-optimal graphons must approach it in cut distance: otherwise a subsequence bounded away from it has a convergent further subsequence that is also optimal, contradicting uniqueness. This is a qualitative compactness argument, not an explicit stability rate. The primary metric framework is Borgs and collaborators.
For triangle-free edge maximization, the balanced complete bipartite graphon is the extremizer. A direct finite stability proof supplies a quantitative bridge. In a triangle-free graph $G$ on $N$ vertices with $m\ge N^2/4-\delta N^2$, choose a maximum-degree vertex of degree $d$. Its neighborhood $A$ is independent, and $B$ is the complement. If $b=e(G[B])$, then $m+b\le d(N-d)$. Therefore $b\le\delta N^2$, the number of missing cross edges is at most $2\delta N^2$, and $\lvert d-N/2\rvert\le\sqrt\delta\,N$.
Changing at most $3\delta N^2$ edges reaches a complete bipartite graph with that imbalance. Each changed undirected edge affects two graphon cells, so the $L^1$ error is at most $6\delta$. Moving its split to one-half adds at most $2\sqrt\delta$. Thus
$$\delta_\square(W_G,W_{1/2})\le6\delta+2\sqrt\delta.$$
This complete finite argument proves stability for the specified triangle-free hypothesis. Combined with graphon sampling and continuity, it also gives uniqueness of the optimum in the graphon setting. Omitted prerequisite for that last extension: the almost-sure convergence of graphon-sampled finite graphs; do not replace it by an unproved assertion that every pointwise representation is unique.
Solved example. For the complete bipartite graphon $W_a$, the edge deficit is $1/2-2a(1-a)=2(a-1/2)^2$. A direct aligned $L^1$ comparison with $W_{1/2}$ is at most $2\lvert a-1/2\rvert$, so the part imbalance is controlled by the square root of the density deficit. At $a=1/3$, the deficit is $1/18$, and the bound on that comparison is $1/3$; this is a bound, not a claim that the cut distance equals it.
Dense network modeling gives a cross-disciplinary interpretation. A step graphon is a finite-group interaction model; its motif integrals quantify clustering and common-neighbor structure independently of the total number of vertices. Model comparison modulo relabeling avoids mistaking renamed groups for a structural change. This applies to a chosen dense-network regime; sparse networks need a different normalization or local model.
Exercise. Does equality of edge density alone justify stability toward one fixed graphon? Hint: compare the constant and balanced bipartite examples. Solution: no. Both have density one-half, but their triangle and four-cycle densities differ. The forbidden-triangle constraint and extremal objective are what select the bipartite optimizer.
Estimate homomorphism densities and inspect a flag-algebra certificate
The investigation connects finite sampling, continuous motif densities, and an exact extremal certificate. Its core uses the supplied balanced bipartite graphon and the square identity reproduced below. The extensions explore relabeling and sparse local limits. Random estimates illustrate quantities whose exact values are already proved; they do not establish an extremal theorem by themselves.
Estimate homomorphism densities and inspect a flag-algebra certificate
Inputs and deliverables. Use $G=K_{3,3}$ with parts $\{0,1,2\}$ and $\{3,4,5\}$ and its balanced step graphon. Use motifs $K_2$, the two-edge path $P_3$, $K_3$, and $C_4$. Submit exact map counts, a reproducible estimate table, the semidefinite matrix factorization, a coefficient audit, and a statement of which sampling convention each result uses.
Warm-up — 20 points. Count all edge-preserving maps for each motif, allowing collisions, and divide by $6^{v(F)}$. Worked solution: counts are $18,54,0,162$, giving densities $1/2,1/4,0,1/8$. The four-cycle injective count is seventy-two and its distinct-map density is $1/5$; record it separately rather than using it as the homomorphism density.
Proof and certificate inspection — 30 points. For a general graphon define $p$ as edge density, $b$ as the probability of an unlabeled induced one-edge graph on three positions, $z$ as triangle density, and $s=\int(2d_W-1)^2$. Verify $Q=\begin{pmatrix}1&-1\\ -1&1\end{pmatrix}$ is positive semidefinite and prove
$$\frac12-p=\frac12s+\frac13b-z.$$
Hints: factor $Q$ as the outer product of $(1,-1)$; average the rooted sign product in each of the four three-vertex types. All data needed for the coefficient audit are the four rows in section 47.9, and may also be regenerated from their labeled graphs.
Worked solution. The square evaluates $Q$ on $(d_W,1-d_W)$. The four type coefficients are $1,-1/3,-1/3,1$. Edge coefficients are $0,1/3,2/3,1$ and the type probabilities sum to one. Adding half the square, one-third of the one-edge density, and minus the triangle density gives coefficients $1/2,1/6,-1/6,-1/2$, equal to $1/2-p$. For $z=0$ the identity proves $p\le1/2$. In the balanced graphon $b=z=s=0$, so the bound is attained. Applied to a finite triangle-free adjacency graphon, this proves Mantel's bound exactly; a numerical SDP solver is unnecessary for this certificate.
Sampling and exact computational audit — 35 points. For each motif independently, repeat ten thousand trials. Sample its vertex images independently and uniformly from $0,\ldots,5$ with replacement, and record success if all its edges map to cross-part pairs. Do not require distinct images or reject collisions. A reference run uses Python random.Random(470047), randrange(6), and motif order $K_2,P_3,K_3,C_4$; it samples the images in motif-vertex order before checking all edges.
| Motif | Exact density | Successful trials | Estimate |
|---|---|---|---|
| $K_2$ | $1/2$ | $5019$ | $0.5019$ |
| $P_3$ | $1/4$ | $2480$ | $0.2480$ |
| $K_3$ | $0$ | $0$ | $0$ |
| $C_4$ | $1/8$ | $1230$ | $0.1230$ |
For truly independent random trials, Hoeffding's inequality gives $\Pr(\lvert\widehat t-t\rvert\gt\varepsilon)\le2e^{-2M\varepsilon^2}$. A union bound over the four motifs gives $8e^{-2M\varepsilon^2}$. With $M=10000$ and $\varepsilon=1/50$, this is $8e^{-8}\lt0.003$. The fixed-seed run is a reproducibility record; the probability guarantee concerns ideal independent sampling, not randomness inferred from a deterministic seed.
As an exact audit, enumerate all $6^{v(F)}$ maps and compute rational densities. Also enumerate all $6^3$ three-position samples to recover type probabilities $(1/4,0,3/4,0)$. Use these with the coefficient table to verify the certificate. For contrast, distinct-three-vertex sampling gives empty-type probability $1/10$, explicitly exposing the collision correction rather than hiding it.
Interpretation — 15 points. Connect the dense sequence $K_{m,m}$ to its graphon, its motif estimates, and the triangle-free extremal certificate. Explain that the certificate proves the density bound for every admissible graphon, while the estimate table concerns one model. Relate this to dense group-based network modeling: equal edge densities can hide different clustering, so edge and four-cycle statistics help compare competing latent interaction structures. Such a comparison needs a stated sampling and density regime, not merely a large network.
Optional relabeling extension, ungraded. Use the two four-cell binary graphons from section 47.3. Enumerate sixteen possible row-cell unions and sixteen column-cell unions to verify aligned cut norm $1/8$. Apply the simultaneous row/column swap of cells two and three and verify zero residual. Solution outline: before relabeling the first two cells on both axes attain discrepancy $1/8$; afterward all sixteen entries agree. This proves zero cut distance for this pair, rather than an algorithm for minimizing cut distance between arbitrary graphons.
Optional sparse extension, ungraded. Compare cycles, paths, and matchings under dense and local weak convergence. Solution outline: all have dense graphon limit zero. Cycles and paths tend locally to the infinite path, while matchings tend to a rooted single edge. For paths, the radius-$R$ exceptional-root fraction is at most $2R/N$. The fixed-radius limit does not certify global connectivity.
Rubric and validation scope. Award warm-up points for correct normalization and collision handling; proof points for the exact factorization, coefficients, and forbidden-density hypothesis; sampling points for reproducibility, independent-trial scope, exact enumeration, and confidence calculations; interpretation points for distinguishing finite data from universal proof and choosing the appropriate graph-limit framework. Check rational identities before accepting rounded numerical output. The cited limit, exchangeability, and flag-algebra results are established theorems with omitted prerequisites identified; no unverified conjecture or sampled optimizer is needed to complete the investigation.
Next in the Series
In Chapter 48: Complexity of Counting and Enumeration, we'll explore Classify when exact and approximate counts can be computed efficiently.