Graphon.lean

/-
Copyright (c) 2026 Cameron Freer. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Cameron Freer
-/

import Graphon.PermutationExtension
import Graphon.RelationalSignature
import Graphon.RelationalStructure
import Graphon.RelationalTopology
import Graphon.RelExchangeableLaw
import Graphon.RelInfiniteLaw
import Graphon.RelLawEquivalence
import Graphon.RelRestrictionBlocks
import Graphon.RelRestrictionIndependence
import Graphon.RelInvariantAction
import Graphon.RelErgodicLinks
import Graphon.RelErgodicExtreme
import Graphon.RelExtremality
import Graphon.RelEqualityPattern
import Graphon.RelKernelEvaluator
import Graphon.RelKernelSampler
import Graphon.KernelRandomization
import Graphon.ForMathlib.CondExpRepresentable
import Graphon.ForMathlib.RelativeFactorCoupling
import Graphon.UniformFactorCoupling
import Graphon.RelRankOneTransfer
import Graphon.RelFixingAlgebra
import Graphon.RelRankAlgebra
import Graphon.RelLowerFactor
import Graphon.RelRankSuccessor
import Graphon.RelRankLatents
import Graphon.RelRankOneCondIndep
import Graphon.RelPollingInfrastructure
import Graphon.RelFixingCondIndep
import Graphon.SeparableFactor
import Graphon.RelCoherentBasis
import Graphon.RelFactorLaws
import Graphon.RelStepKernel
import Graphon.RelBasisSyntax
import Graphon.RelBasisSaturation
import Graphon.DigraphMaps
import Graphon.InfiniteDigraph
import Graphon.SimpleGraphDigraphBridge
import Graphon.InfiniteDigraphLaw
import Graphon.ExchangeableLawBlueprint
import Graphon.Digraphon
import Graphon.SamplerSources
import Graphon.DigraphSampler
import Graphon.DigraphonConstructors
import Graphon.DigraphSamplerFamilies
import Graphon.Basic
import Graphon.Step
import Graphon.HomDensity
import Graphon.Pullback
import Graphon.Operations
import Graphon.Operator
import Graphon.CutNorm
import Graphon.CutDistance
import Graphon.LevyDownward
import Graphon.MeasureIso
import Graphon.Approximation
import Graphon.Counting
import Graphon.Regularity
import Graphon.Overlay
import Graphon.Compactness
import Graphon.GraphonSpace
import Graphon.InfiniteGraph
import Graphon.Sampling
import Graphon.CaiGovorov
import Graphon.Lovasz
import Graphon.CrossSuper
import Graphon.SimpleRank
import Graphon.CycleKrylov
import Graphon.MatrixDetermination
import Graphon.SamplingICL
import Graphon.SamplingConcentration
import Graphon.SamplingRounding
import Graphon.SamplingPointwise
import Graphon.SamplingLemma
import Graphon.SamplingLaw
import Graphon.SamplingExamples
import Graphon.SamplingDetermination
import Graphon.SamplingCoordinates
import Graphon.ExchangeableGraphLaw
import Graphon.MixtureConvergence
import Graphon.HomDensityAlgebra
import Graphon.MixtureCoordinates
import Graphon.MixtureUniqueness
import Graphon.InverseCounting
import Graphon.InjectionCounting
import Graphon.SamplingFinite
import Graphon.SubgraphDensities
import Graphon.SubgraphDensityBridges
import Graphon.SubgraphDensityBlueprint
import Graphon.MixtureExistence
import Graphon.MixtureRepresentation
import Graphon.MixtureExtremality
import Graphon.InfiniteLaw
import Graphon.InfiniteExchangeability
import Graphon.InfiniteRepresentation
import Graphon.MixtureKernel
import Graphon.InfiniteSamplingConvergence
import Graphon.McDiarmid
import Graphon.SampleExposure
import Graphon.AlmostSureSampling
import Graphon.LimitGraphon
import Graphon.InfiniteSampleLaw
import Graphon.EmpiricalGraphon
import Graphon.InfiniteExtremality
import Graphon.InfiniteSampler
import Graphon.DissociatedSampler
import Graphon.VertexTail
import Graphon.InvariantAction
import Graphon.RestrictionIndependence
import Graphon.RestrictionIndependenceReverse
import Graphon.ErgodicDecomposition
import Graphon.Convergence

/-!
# Graphons in Lean 4

A formalization of graphons — the theory of limits of dense graph sequences —
in Lean 4 using Mathlib.

## Stable core

* `Graphon.Basic` — Graphon definition, symmetry, boundedness
* `Graphon.Pullback` — Pullback under measure-preserving maps
* `Graphon.Step` — Measurable partitions, step functions
* `Graphon.HomDensity` — Homomorphism density definition
* `Graphon.CutNorm` — Cut norm, graphon integrability
* `Graphon.Approximation` — Rectangle averages, cut norm approximation
* `Graphon.CutDistance` — Cut distance, pseudometric properties, three of the four Rokhlin cores
* `Graphon.LevyDownward` — **Lévy's downward theorem, L¹ version** (Mathlib-upstream candidate, #24): orthogonal projections along an antitone sequence of subspaces converge to the projection onto the infimum; the `Lᵖ`-subspace of an infimum σ-algebra is the intersection; conditional expectations along an antitone sequence of σ-algebras converge in `L¹` to the conditional expectation on the infimum; and conditional expectation over a `0`-`1` σ-algebra is the mean
* `Graphon.MeasureIso` — Atomless standard-Borel measure-isomorphism theorem (graphon-independent; mod-0 iso + everywhere upgrade)
* `Graphon.Overlay` — Overlay theorem: an MP bijection nearly achieves the cut distance (fourth Rokhlin core)
* `Graphon.Regularity` — Energy increment, Frieze–Kannan weak regularity lemma
* `Graphon.Counting` — Homomorphism density, counting lemma
* `Graphon.Compactness` — Total boundedness, completeness
* `Graphon.GraphonSpace` — The graphon space: compact Polish standard-Borel metric quotient under weak isomorphism (`GraphonSpace`, `StandardGraphonSpace`)
* `Graphon.InfiniteGraph` — The infinite graph space: `SimpleGraph ℕ` as a compact Polish standard-Borel space; continuous finite restrictions, cylinder π-system, finite-restriction measure extensionality (Aldous–Hoover brick A1)
* `Graphon.CaiGovorov` — Graph-free Vandermonde argument (Cai–Govorov §4), for #70 orbit separation
* `Graphon.Lovasz` — Connection-matrix algebra scaffolding (Lovász §3), incl. the Cai–Govorov #70 orbit theorem and rank theorem
* `Graphon.CrossSuper` — Cross-matrix super-surjective transfer (Cai–Govorov Lemma 5.1, two-matrix partition form)
* `Graphon.SimpleRank` — K=1 simple-graph rank theorem, algebra-atom framing (#70)
* `Graphon.CycleKrylov` — spectral slice of the cycle–Krylov square-moment proof (#70)
* `Graphon.MatrixDetermination` — Algebraic determination of step graphons
* `Graphon.SamplingICL` — Sampling route to the partition-size-independent quantitative inverse counting lemma
* `Graphon.SamplingConcentration` — Concentration scaffold for the First Sampling Lemma (conditional distribution, weighted sample, two-stage reduction)
* `Graphon.SamplingRounding` — The rounding half of the First Sampling Lemma, proved (cut certificate + finite Chernoff)
* `Graphon.SamplingPointwise` — The pointwise half of the First Sampling Lemma: AFKK cut-guessing bound, McDiarmid-at-MGF + soft-max infrastructure
* `Graphon.SamplingLemma` — The First Sampling Lemma, assembled from the two proved concentration events
* `Graphon.SamplingLaw` — The finite sample law of a graphon: `samplePMF`/`sampleLaw`, Möbius/upper-transform engine, relabeling invariance, arbitrary-injection consistency
* `Graphon.SamplingExamples` — The constant graphon samples Mathlib's binomial random graph `G(V, p)`
* `Graphon.SamplingDetermination` — The sample laws determine the graphon: `(∀ k, samplePMF U k = samplePMF W k) ↔ WeaklyIsomorphic U W`, and its `GraphonSpace` form
* `Graphon.SamplingCoordinates` — Continuous point-separating sample-law coordinates on the graphon space; compact coordinate embedding
* `Graphon.ExchangeableGraphLaw` — Exchangeable graph laws (consistent finite marginals) and graphon mixtures; mixtures are exchangeable
* `Graphon.MixtureConvergence` — Weak-convergence layer: mixture coordinates as integrals, Prokhorov extraction, empirical mixing measures
* `Graphon.HomDensityAlgebra` — Hom-density coordinates on the graphon space; multiplicativity over disjoint unions (`homDensity_sum`)
* `Graphon.MixtureCoordinates` — Shared mixture-coordinate layer: hom-density coordinates as bounded continuous functions; their integrals are mixture upper masses
* `Graphon.MixtureUniqueness` — Uniqueness of the graphon mixture: the coordinate StarSubalgebra separates points; `mixtureExchangeableLaw` is injective
* `Graphon.InjectionCounting` — pure counting of vertex maps `Fin k → Fin n` (#94 shared infrastructure): the union (birthday) bound `card_not_injective_le` with its `k²/(n+1)` proportion form, the reciprocal vertex-map-count weight, and the descending-factorial injective-map count `card_filter_injective_eq_descFactorial` — extracted from the mixture-existence collision estimate
* `Graphon.SamplingFinite` — The exact finite-sampling formula: sampling from an embedded finite graph is uniform vertex-map pullback
* `Graphon.SubgraphDensities` — the finite subgraph densities `t`, `t_inj`, `t_ind` (#94): labeled hom / injective-hom / induced-copy counts with their normalization conventions (`n ^ k` all maps vs the `descFactorial` injective count), the all-maps exact-pullback count, with the small-host zero convention (combinatorics-only import closure)
* `Graphon.SubgraphDensityBlueprint` — annotation-only blueprint wrapper for the finite density triangle (keeping `Graphon.SubgraphDensities` Architect-free)
* `Graphon.SubgraphDensityBridges` — the analytic bridges `homDensity_ofSimpleGraphOn_eq_t` / `sampleMass_ofSimpleGraphOn_eq_pullbackCount_div` from the finite densities to the empirical-graphon sampling formulas
* `Graphon.MixtureExistence` — Existence of the graphon mixture: the collision estimate for empirical mixing measures; every exchangeable law is a mixture (`exists_mixtureExchangeableLaw_eq`)
* `Graphon.MixtureRepresentation` — The Diaconis–Janson representation theorem: exchangeable graph laws = graphon mixtures, uniquely (`graphon_mixture_representation`, `mixtureExchangeableLawEquiv`)
* `Graphon.MixtureExtremality` — Diaconis–Janson extremality: dissociated exchangeable laws are exactly the Dirac mixtures (`isDissociated_mixtureExchangeableLaw_iff`)
* `Graphon.InfiniteLaw` — The infinite exchangeable graph law: unique extension of consistent finite marginals to `InfiniteGraph`, via Prokhorov compactness (Aldous–Hoover brick A2)
* `Graphon.InfiniteExchangeability` — Exchangeability of the infinite law under every relabeling; the equivalence `ExchangeableGraphLaw ≃ InfiniteExchangeableGraphLaw` (Aldous–Hoover brick A3)
* `Graphon.InfiniteRepresentation` — The infinite Diaconis–Janson/Aldous–Hoover correspondence: `ProbabilityMeasure (GraphonSpace α μ) ≃ InfiniteExchangeableGraphLaw` (`infiniteMixtureLawEquiv`)
* `Graphon.InfiniteSampleLaw` — The canonical infinite law of a graphon class: quotient descent, finite-restriction marginals, weak continuity, closed embedding into infinite laws
* `Graphon.EmpiricalGraphon` — Empirical graphons of an infinite exchangeable graph: their law is the empirical mixing measure; convergence in distribution to the representing measure
* `Graphon.InfiniteExtremality` — Extremality for infinite exchangeable laws: dissociated ↔ canonical law of a single graphon class ↔ Dirac representing measure
* `Graphon.InfiniteSampler` — Explicit infinite sampler for a fixed graphon: i.i.d. sources via `Measure.infinitePi`; the measurable sampler realizes `infiniteLaw (sampleExchangeableLaw W)` exactly
* `Graphon.MixtureKernel` — The barycenter interpretation: the represented infinite law is the `Measure.bind` mixture of the canonical fiber laws (`mixtureInfiniteLaw_eq`)
* `Graphon.InfiniteSamplingConvergence` — Convergence in probability: the sampled empirical graphons of a `W`-random infinite graph tend to the class of `W` in measure
* `Graphon.McDiarmid` — Bounded-differences concentration at MGF level, packaged as `HasSubgaussianMGF` (Mathlib-upstreaming candidate)
* `Graphon.SampleExposure` — The padded vertex-exposure sampler and the fixed-`F` exponential hom-density tail `2·exp(−ε²k/(2q²))` for `G(k, W)` (Lovász Cor 10.4 form), with the explicit-sampler tail and Borel–Cantelli summability bridge
* `Graphon.AlmostSureSampling` — Almost-sure convergence of the sampled empirical graphons to the class of `W` (Lovász Prop 11.32; Borel–Cantelli over the concentration tails)
* `Graphon.LimitGraphon` — The empirical graphon limit as a universal measurable random variable: `limitGraphon` with law `infiniteMixtureLawEquiv.symm M` under every exchangeable law
* `Graphon.DissociatedSampler` — Functional Aldous–Hoover for dissociated laws: an infinite exchangeable law is dissociated iff it is the law of the explicit `W`-random graph (`isDissociated_iff_exists_sampler`)
* `Graphon.VertexTail` — Vertex-tail infrastructure: the tail shift and σ-algebras, finite-deletion stability of empirical limits, and vertex-tail measurability of `limitGraphon`
* `Graphon.RestrictionIndependence` — Toward DJ Theorem 5.5: the vertex-tail σ-algebra and restriction independence; `RestrictionIndependent ⟹ VertexTailTrivial ⟹ dissociated` (via the tail-measurable empirical limit)
* `Graphon.RestrictionIndependenceReverse` — The reverse arc closing DJ Theorem 5.5: dissociation ⟹ restriction independence (two-block Möbius factorization), and the five-way extremality `tfae_extremality`
* `Graphon.InvariantAction` — The finite-permutation action toward ergodic decomposition (#59): `limitGraphon` is invariant under every finite relabeling, hence invariant-σ-algebra measurable; `IsErgodic`
* `Graphon.ErgodicDecomposition` — The ergodic-decomposition form of extremality (#59 part 2): the six-way equivalence `tfae_ergodic_extremality` adjoining ergodicity under the finite-permutation action, and `invariant_ae_eq_limitGraphon_classifier` — `limitGraphon` generates the invariant σ-algebra modulo null sets; built from fixed-fiber ergodicity (block swap + initial-cylinder approximation)
* `Graphon.PermutationExtension` — `exists_perm_extend`: every `Fin k ↪ ℕ` extends to a permutation of `ℕ` (graph-independent; reused by the graph and relational exchangeability APIs)
* `Graphon.RelationalSignature` — Generic AHK program (umbrella #103), R0 design checkpoint (#110): purely relational multi-sorted `RelSignature`, the `RelCoord`/`RelStructure` carriers, external `NoNullary`, finite/infinite value carriers, the sortwise `RelCoord.map`/`RelStructure.comap` action, and worked digraph/bipartite/ternary examples (the ternary `(i,i,j)` exercising repeated coordinates); no topology/probability yet
* `Graphon.RelationalStructure` — Generic AHK program R1a (#104): sortwise actions on relational structures — `map`/`comap` functoriality, `restrict`/`relabel`, finite restrictions `restrictFin`/`restrictLE`, padding `pad` with the section `restrict_pad`, and restriction composition `restrictLE_restrictFin`/`restrictLE_restrictLE`; still no topology/measure (that is R1b)
* `Graphon.RelExchangeableLaw` — Generic AHK program R2a (#105): exchangeable relational laws — size-vector-indexed `ProbabilityMeasure` marginals with arbitrary sortwise-injection consistency (`RelExchangeableLaw`), the measurable sortwise restriction, diagonal cofinality, and finite-exchangeability of the marginals; no infinite extension yet (R2b/R2c)
* `Graphon.RelInfiniteLaw` — Generic AHK program R2b (#105): the compactness-based infinite extension **realizing the marginals** — diagonal padded laws (`paddedLaw`), Prokhorov subsequence extraction on the compact metrizable structure space, and marginal identification via continuity, giving `infiniteLaw` with `infiniteLaw_map_restrictFin`; exchangeability/uniqueness/equivalence is R2c
* `Graphon.RelLawEquivalence` — Generic AHK program R2c (#105): the finite/infinite exchangeable relational law equivalence — the arbitrary-injection marginal theorem, exchangeability of `infiniteLaw`, `InfiniteRelExchangeableLaw`, the permutation extension, and `relExchangeableLawEquiv : RelExchangeableLaw S ≃ InfiniteRelExchangeableLaw S`
* `Graphon.InfiniteDigraph` — Directed umbrella (#84) D1 (#85): `InfiniteDigraph` as the one-sort binary R1 instance (`digraphSig`) — inheriting compact/standard-Borel, measurable finite restrictions, and measure extensionality (all topology on `InfiniteDigraph`); `Adj` (Prop) / `adjBit` (Bool); `digraphStructureEquiv V` the plain carrier equivalence with Mathlib's `Digraph V`, giving both the infinite `digraphEquiv` and the finite `finiteDigraphEquiv` (for D2); no exchangeable-law theory (that is D2)
* `Graphon.SimpleGraphDigraphBridge` — the symmetric loopless embedding `SimpleGraph.toFiniteDigraph` with its coordinate lemma, injectivity, and range classification, in its own module preserving D1's relational/directed dependency boundary
* `Graphon.RelRestrictionBlocks` — Generic AHK program R3a (#106): sortwise vertex shift `RelStructure.drop` and block embeddings `shiftEmb`; the labeling-free restriction invariance `InfiniteRelExchangeableLaw.law_map_restrict` and shift invariance `law_map_drop`; the initial / after-block / vertex-tail σ-algebras with monotonicity and `iSup_initialAlgebra_eq`; and `IsDissociated` — dissociation as exact finite-event block factorization, with its marginal API
* `Graphon.RelRestrictionIndependence` — Generic AHK program R3b (#106): `RestrictionIndependent` and `VertexTailTrivial` for exchangeable relational laws; **dissociation ↔ restriction independence** (comap-σ-algebra independence of the block maps *is* the block-pair factorization, and the finite windows exhaust the after-block σ-algebra) and **restriction independence → vertex-tail triviality** (independence from every initial σ-algebra upgrades to self-independence); and the **representation-free closing arrow** tail-trivial → dissociated (condition on successively later diagonal tail algebras; Lévy downward + triviality + exchangeability force the block factorization), completing dissociated ↔ restriction-independent ↔ tail-trivial
* `Graphon.RelInvariantAction` — R3c (#106): the finitely supported sortwise relabeling action (`SortwiseFinSupp` with group closure), the strictly invariant σ-algebra, `IsErgodic`, and the **invariant probability simplex** `invariantProbabilityMeasures` with the finitary-invariance bridge (finitary invariance ⇒ full sortwise invariance, via finite-restriction extensionality and finitely supported window extensions) identifying it with the laws of `InfiniteRelExchangeableLaw`
* `Graphon.RelErgodicLinks` — R3c: ergodicity linked into the dissociation triangle — the sortwise block swap, in-measure approximation by initial cylinders, the 4ε approximate-independence core (restriction independence ⇒ ergodicity), vertex-tail ⊆ invariant (ergodicity ⇒ tail triviality), and the iff chain
* `Graphon.RelErgodicExtreme` — R3c: the ergodic ↔ extreme-point theorem for the relabeling group (port of Mathlib's `Ergodic.iff_mem_extremePoints`), with the new absolute-continuity lemma `eq_of_absolutelyContinuous` and the a.e.-to-strict invariant hull upgrade over the countable group
* `Graphon.RelExtremality` — R3c headline: the **five-way extremality equivalence** `tfae_extremality` (dissociated ↔ restriction-independent ↔ tail-trivial ↔ ergodic ↔ extreme), representation-free, with the `digraphSig` regression examples
* `Graphon.RelEqualityPattern` — R4 design checkpoint (#107): sort-tagged values (`RelCoord.taggedValue`), the **equality pattern** as its kernel with the **bundled label-free `EqualityPattern`** (sort-compatible setoid + `blockSort`), the **support** as a finset of tagged values (blocks ≃ support), global and **local latent indices** (`LatentIndex`; `PatternLatentIndex` — the kernel's order-free domain — and `CoordLatentIndex`, canonically equivalent and two-way relabeling-equivariant via `congrMap`), and the `Sigma.map id` transport — the interface for the functional AHK representation (sampler and representation theorem deliberately held back); binary/diagonal/ternary/bipartite examples in their own namespace
* `Graphon.RelKernelEvaluator` — R4 evaluator layer (#107): `RelKernelFamily` (the label-free measurable representing kernels `f_{r,π}` on the finite pattern-local latent product), `RelCoord.localLatents` (the coordinate's window into the global latent source), the measurable `evalStructure`, and the **equivariance theorem** `evalStructure_relabel` (relabeling the evaluated structure = precomposing the source with the latent-index action) with the pattern↔image transport square `patternLatentIndexEquivCoord_map` — latent source measure, sampler pushforward, and representation theorem deliberately held for the next layers
* `Graphon.RelKernelSampler` — R4 sampler layer (#107): the evaluator over an arbitrary carrier (`RelKernelFamily.eval`, definitionally `evalStructure` on `Vinfinite`) with the pullback transport `eval_comap`; the i.i.d. uniform `latentSource` over global subset-latent indices with relabeling invariance (via `LatentIndex.relabelEquiv`); and the **evaluated exchangeable law** `RelKernelFamily.evalLaw` with its **dissociation** `evalLaw_isDissociated` (disjoint vertex windows read disjoint nonempty subset-latent collections, so the i.i.d. source factorizes) — the forward half of the dissociated functional AHK representation; the converse representation theorem is the remaining content of #107
* `Graphon.KernelRandomization` — R4 converse piece 1 (#107): the small adapter from Mathlib's kernel representation theorem (`Kernel.exists_measurable_map_eq_unitInterval`, Kallenberg Lemma 4.22) to the project's uniform source — `Kernel.exists_measurable_map_eq_uniform01` (a Markov kernel into a standard Borel space is the pushforward of `uniform01` by a jointly measurable map, the `[0,1]`-subtype input adapted through `Set.projIcc`) and the single-measure corollary `Measure.exists_measurable_map_eq_uniform01` — the randomization ("noise outsourcing") input for the converse representation theorem
* `Graphon.ForMathlib.CondExpRepresentable` — **upstream candidate** (signature-free, Mathlib-only imports): conditioning is insensitive to replacing a σ-algebra by one that represents it **modulo the measure**. Given `m₂ ≤ m₁` and an eventwise representative in `m₂` for every `m₁`-set, `condExp_eq_condExp_of_ae_representable` gives `μ[f | m₁] =ᵐ μ[f | m₂]`, and `iCondIndepFun_congr_of_ae_representable` transfers mutual conditional independence between the two. This is the recurring R4 situation where an abstractly defined conditioning algebra has a concrete factor-map realization that generates it only eventwise: no σ-algebra equality is available or claimed, but everything conditional expectation can see transfers. **The proof deliberately does not lift the hypothesis from sets to functions** — Mathlib's `EventuallyMeasurable` warns that eventual measurability is strictly weaker than a.e. equality to a measurable function and leaves the equivalence a TODO, so that route would mean redoing simple-function approximation. Instead the uniqueness argument runs in the other direction: `μ[f | m₂]` is the *candidate* at `m₁`, already `m₁`-strongly measurable since `m₂ ≤ m₁` is raw, and its set integrals over `m₁`-sets are computed by moving to an `m₂` representative. The conditional-expectation statement needs only `[IsFiniteMeasure μ]`; the standard Borel hypothesis on the `iCondIndepFun` corollary is forced by Mathlib defining `iCondIndepFun` through `condExpKernel`, not by the argument
* `Graphon.ForMathlib.RelativeFactorCoupling` — **upstream candidate** (signature-free, Mathlib-only imports): the **relatively independent joining over a common factor**, `relativeFactorCoupling μ ν q r = (condDistrib id q μ ×ₖ condDistrib id r ν) ∘ₘ μ.map q`, for measurable `q : Ω → Z`, `r : Ξ → Z` with `ν.map r = μ.map q`. Both sides are disintegrated over `Z` and the fibres multiplied independently; the independent product `μ.prod ν` would not identify the factors, and an arbitrary coupling that did could still let each side see more of the other. The engine is `map_condDistrib_id`, **fibre concentration**: pushing `condDistrib id q μ` through `q` is the deterministic identity kernel, i.e. conditioning on `q` pins down `q`. From it: both marginals, the common-factor identity `q ∘ Prod.fst =ᵐ r ∘ Prod.snd` (proved from the two fibre-concentration statements, one per side — equality of the factor *marginals* says nothing about the joint), and `condIndepFun_fst_snd_relativeFactorCoupling`, conditional independence of the two coordinates given `comap (q ∘ Prod.fst)`. The conditioning is deliberately on that variable, defined on the coupling space, rather than on the disintegration variable `∘ₘ` integrates out: only the former is visible to consumers, who see the coupling and not its construction. No σ-algebra equality `σ(q ∘ fst) = σ(snd)` is claimed — the latent may carry strictly more than the factor, as `U` carries more than `1_{U < p}`; what conditional independence excludes is that the surplus says anything further about the first coordinate
* `Graphon.UniformFactorCoupling` — R4 converse piece 3 (#107): the uniform specialization of the joining above, `exists_relativeFactorCoupling_uniform01`. The only uniform-specific input is `Measure.exists_measurable_map_eq_uniform01` (#140), which supplies the coding map `f : ℝ → Z` matching the two factor laws; everything after is generic. It runs in the direction `Graphon.KernelRandomization` does not — that module manufactures a variable with a prescribed law *out of* a uniform, whereas here a uniform is manufactured *alongside* an already-given variable — and it is reusable at every rank, so it replaces a port of an external de Finetti package with the narrow transfer step the recursion actually needs
* `Graphon.RelRankOneTransfer` — R4 converse piece 3 (#107): **I(1)**, the base of the rank recursion, instantiating the relative joining at `q = lowerFactorMap 1`. `lowerFactorMap_one_relabel` is the rank-one degeneracy that makes this work: `LowerIndex 1` holds exactly the indices anchored at `∅`, whose events are `invariantAlgebra`-measurable, so the rank-one factor map is relabeling invariant **on the nose** — not merely equivariant, no null sets, no transport of the factor space — and the equivariance square of `Graphon.RelLowerFactor` degenerates. Hence `map_prodMap_relabel_rankOneCoupling`: every finitely supported sortwise relabeling of the structure coordinate preserves the coupling, acting inside the fibres of the disintegration. At higher rank this fails and the statement will have to move the factor space by `lowerFactorSpaceEquiv` on the other side. `exists_rankOneUniformCoupling` bundles the six clauses; the conditional-independence clause is the one that cannot be dropped, since marginals plus the resolution identity `lowerFactorMap 1 X = f ξ` still permit a latent encoding arbitrary information about what rank one leaves unresolved. It is stated over the whole structure coordinate, so any particular unresolved reading follows by composition — recorded explicitly as `condIndepFun_comp_fst_snd_rankOne`
* `Graphon.RelFixingAlgebra` — R4 converse piece 2a (#107): the **law-independent** factor-algebra layer — `SortwiseFixing` (the `A`-fixing stabilizer of finitely supported sortwise permutations, closed under `1`/`*`/`⁻¹`/conjugation), the raw `RelStructure.fixingAlgebra` (events invariant under the `A`-fixing group; deliberately *not* "generated by relations inside `A`", which loses hidden vertex information), monotonicity, `fixingAlgebra_empty = invariantAlgebra` (near-definitional), and the **transport equality** `fixingAlgebra_comap_relabel : comap (relabel σ) (fixingAlgebra A) = fixingAlgebra (image σ A)` via stabilizer conjugation — no completions, no law; the conditional-independence theorem is its own later PR
* `Graphon.RelPollingInfrastructure` — R4 (#107): the reusable polling engine, extracted from `RelFixingCondIndep` once the rankwise relative-independence argument became its second consumer. Three public declarations: the tail engine `condExp_ae_eq_condExp_of_comap_eq` (a measure-preserving `T` fixing `f` a.e. and pulling `m₁` back to `m₂ ≤ m₁` forces `μ[f|m₁] =ᵐ μ[f|m₂]`), `InfiniteRelExchangeableLaw.measurePreserving_relabel`, and `InfiniteRelExchangeableLaw.relabel_preimage_ae_eq_of_fixingAlgebra`. The `L²` squeeze and the conditional-expectation transport along `comap` stay private — they are the proof of the tail engine, not its interface
* `Graphon.RelFixingCondIndep` — R4 converse piece 2b (#107): the headline `InfiniteRelExchangeableLaw.condIndep_fixingAlgebra` — for **every** exchangeable law, with no dissociation hypothesis, `CondIndep (fixingAlgebra (A ∩ B)) (fixingAlgebra A) (fixingAlgebra B) (fixingAlgebra_le _) M.law` (Austin arXiv:0801.1698 Lemma 3.11 / Proposition 3.12; Kallenberg Lemma 7.6 as the closest precursor — Lemmas 7.18–7.19 there belong to the later realization recursion). The private machinery: the `L²`-energy squeeze, measure-preserving-map transport of conditional expectation, and the tail-property engine (a.e.-fixing + comap-pullback ⟹ equal conditional expectations); the upgrade of `fixingAlgebra A`-invariance from finitely supported to *arbitrary* sortwise permutations fixing `A`, modulo the law; the poll geometry (deep copies of `B \ A` laid out along a two-sided `ℤ`-orbit — a unilateral block shift is not a bijection — moved by a single residue-wise permutation fixing `A`); the tail **joins** `⨆_{m ≥ n} fixingAlgebra ((A ∩ B) ∪ Q m)`, whose intersection is `fixingAlgebra (A ∩ B)` as a *raw* σ-algebra equality; and the reduction `E[f | fixingAlgebra B] =ᵐ E[f | fixingAlgebra (A ∩ B)]` that the theorem factorizes through. Everything but the headline is `private`
* `Graphon.SeparableFactor` — R4 converse piece 3 (#107), the generic signature-free toolkit for the coherent factor realization; nothing here mentions relational structures, and the whole module is a Mathlib-upstream candidate (#24). `Measure.MeasureDense.exists_generateFrom_ae_eq_of_ne_top` upgrades a measure-dense family for a trimmed measure from *approximation* to honest **a.e. representatives** (`∀ E, MeasurableSet[m] E → ∃ E', MeasurableSet[generateFrom G] E' ∧ E' =ᵐ[μ] E`) by summable symmetric-difference approximation plus Borel–Cantelli, with no countability hypothesis — countability matters only when the family is turned into a factor space — and `exists_generateFrom_ae_eq` is its finite-measure corollary. `measure_symmDiff_threshold_le` is the threshold estimate `ν (E ∆ {x | 1/2 < f x}) ≤ 2‖1_E - f‖₁`, the bridge from an `L¹`-dense family of *functions* to a measure-dense family of *sets*. `MeasurableSpace.comap_mapNatBool` is the missing companion to Mathlib's `measurable_mapNatBool`: a countably generated σ-algebra is *literally* the pullback of the Cantor-space σ-algebra along `mapNatBool`, needing no `SeparatesPoints` since injectivity is irrelevant to the pullback identity. Throughout, the mod-null statements are deliberately eventwise rather than equalities of σ-algebras "modulo null sets", which would force a `Measure.trim`/`Measure.completion` choice at every use site and create diamonds between them
* `Graphon.RelCoherentBasis` — R4 converse piece 3 (#107): the **interface** for a simultaneous, coherent family of factors for the fixing σ-algebras, defined but deliberately not constructed. `CoherentBasis` carries one global countable index type whose indices are anchored at finite tagged vertex sets, closed under finite Boolean operations (a countable set ring), acted on by finitely supported relabelings with exact anchor and event transport, and measure-dense over each `A`. The derived factor at `A` maps into `BasisIndex A → Bool` — a *varying* countable index rather than `ℕ → Bool`, which is what keeps the inclusion for `C ⊆ A` literal, the factor projection an ordinary coordinate restriction, and its cocycle law definitional; `mapNatBool` loses exactly this, since its generating sequence is typeclass-chosen. `exists_comap_factorMap_ae_eq` is the payoff: every `fixingAlgebra A`-event has an a.e. representative in the factor's pullback
* `Graphon.RelBasisSyntax` — R4 converse piece 3 (#107): the Boolean **syntax** layer for a coherent basis. `BasisExpr` is the free `⊥`/complement/intersection syntax over an atom type, with `anchorOf` and `eval` computed by recursion and `act` acting on the tree. Syntax rather than a family of events closed under the operations, for two reasons recorded in the module docstring: the anchor is not determined by the event, so an event-indexed family would have to *choose* one and then make that choice equivariant; and closing a family of events forces representative choices that make `act_one` and `act_mul` hold only up to that choice. Here `act_one`, `act_mul`, `anchorOf_act`, and `eval_act` all follow by structural induction from the atom-level laws, and the anchor-as-union convention on `inter` is what keeps the indices anchored inside `A` closed under the operations
* `Graphon.RelBasisSaturation` — R4 converse piece 3 (#107): the saturated atom family. An atom is a seed event anchored at a finite vertex set together with a finitely supported relabeling of it; the relabeling action is **left multiplication in that coordinate**, which turns the two action laws into literal group laws in the finitely supported subgroup (`act_one` is `one_mul`, `act_mul` is `mul_assoc`), the anchor law into `Finset.image_image`, and the event law into `relabel_preimage_relabel_preimage` — the orientation matching because `relabel` is contravariant. Saturation lives in the index rather than being imposed afterwards, so the family is closed under the action by construction, with no orbit representatives and nothing to make equivariant after the fact. `SeedData` keeps the seeds abstract, so none of the structural laws depend on how they are produced; the seeds themselves come from separability of the law, and the module closes with **`InfiniteRelExchangeableLaw.nonempty_coherentBasis`** — every exchangeable law has a coherent basis, under `[Fintype S.Srt]` and `[Countable S.Rel]`, with no `NoNullary`. Stated as `Nonempty` rather than registered as an instance, since a coherent basis is chosen data and an instance would make later independent choices behave like typeclass diamonds
* `Graphon.RelFactorLaws` — R4 converse piece 3 (#107): the boundary/exact splitting of the coherent factors and their laws. `BoundaryIndex A` collects indices anchored *properly* inside `A` and `ExactIndex A` the exact-anchor layer, giving the measurable equivalence `FactorSpace A ≃ᵐ BoundarySpace A × ExactSpace A`. This partitions *coordinates by anchor*, not information: anchors are not minimal, so an expression anchored at `A` may still name an event measurable over a proper subset. This is the shape the AHK recursion needs — one kernel per finite `A`, conditioned on the whole proper-subset boundary and recursing by `|A|`: kernels for every pair `C ⊆ A` would be redundant and force compatibility between different a.e. versions of conditional distributions, while a linear chain would impose an arbitrary ordering and let the value at `A` depend on sets incomparable to it, breaking subset-locality. `factorLaw` / `boundaryLaw` / `exactLaw` are the pushforwards, with projection consistency along the sub-index inclusions and relabeling invariance from exchangeability — the first place in this layer where the law is used. `measurable_exactMap_fixingAlgebra` sharpens ambient measurability of the exact layer to measurability for `fixingAlgebra A`, which any argument bundling exact-layer events over a support needs
* `Graphon.RelStepKernel` — R4 converse piece 3 (#107): **one kernel per finite `A`**, `stepKernel A : Kernel (BoundarySpace A) (ExactSpace A)`, the conditional distribution of the exact-anchor layer given the whole proper-subset boundary — not one kernel per pair `C ⊆ A`, and not a chain. Built as `condDistrib`, whose standard-Borel hypothesis is exactly what the factor-space packaging supplies. Central identities: the disintegration `boundaryLaw A ⊗ₘ stepKernel A = M.law.map (boundaryMap A, exactMap A)`, marginal recovery `stepKernel A ∘ₘ boundaryLaw A = exactLaw A`, and the same read through `factorSpaceProdEquiv`. Valid for an arbitrary exchangeable law; the `A = ∅` base case is deliberately absent, since its determinism uses dissociation and belongs to the later realization layer
* `Graphon.RelRankAlgebra` — R4 converse piece 3 (#107): the **lower-rank conditioning algebra** `lowerRankAlgebra n = ⨆ A, ⨆ (_ : A.card < n), fixingAlgebra A` and its order theory — monotone in the rank bound, below the ambient algebra, containing each low-rank fixing algebra, `⊥` at rank `0`, and `invariantAlgebra` at rank `1` (the recursion's base, and the reason no `NoNullary` hypothesis is needed). Plus `comap_relabel_lowerRankAlgebra`, invariance under an **arbitrary** sortwise permutation family — relabelings displacing infinitely many vertices arise naturally downstream, so the finite-support hypothesis would be too weak — and `card_inter_lt_of_ne`, that distinct supports of equal rank meet in strictly lower rank. Law-free throughout
* `Graphon.RelLowerFactor` — R4 converse piece 3 (#107): the **structural lower-rank factor**, the object the rank recursion conditions on. `lowerFactorMap n` reads the coherent-basis coordinates whose anchor has cardinality `< n` into the standard Borel `LowerFactorSpace n`. It is stated about the *factor*, never about latents: a latent normally carries randomness beyond the factor it represents — already `1_{U < p}` generates strictly less than `U` — so a σ-algebra generated by latents is typically strictly larger. Generation is `comap (lowerFactorMap n) inferInstance ≤ lowerRankAlgebra n` together with an **eventwise** converse; no raw equality is asserted or supplied, the available converse being modulo `M.law`. The converse is proved support by support through `lowerToFactorProjection`, which exhibits `factorMap A` as a coordinate restriction whenever `A.card < n`, and the containments are joined inside `eventuallyMeasurableSpace` — already a σ-algebra, so the completion does the closing and no family of a.e. witnesses is ever chosen simultaneously through the `iSup`. `lowerIndexEquiv` gives `FinSuppPerm` equivariance as automorphisms of one fixed type (rank is preserved because anchors transport by an injective image map), so the action laws are honest equalities of equivalences with no dependent transport, and they commute with rank nesting definitionally. Rank `0` is `⊥` on the nose; rank `1` is the recursion's base, on the original law, with no augmented space and no coupling
* `Graphon.RelRankSuccessor` — R4 converse piece 3 (#107), unit 1 of the rank transition `n → n+1`: the law-free structural split of the factor space into everything below rank `n` and the layer at rank exactly `n`. **The layer is a Bool-cube, not a dependent product**, and that is a load-bearing choice: `Π A : RankSupport S n, ExactSpace A` would force every downstream conditional law to be a kernel into a dependent product, and Mathlib has no countable dependent product of kernels — there is no `Kernel.pi`, the only `Π`-valued kernels being the Ionescu–Tulcea trajectory kernels, which are ℕ-indexed chains whose source is the history rather than a fixed common parameter. Since `ExactSpace A = ExactIndex A → Bool` the dependent product is already a Bool-cube on `{i // (anchor i).card = n}`, so `RankLayerIndex`/`RankLayerSpace`/`rankLayerMap` are defined directly that way, with `sigmaExactIndexEquiv` recording the bridge to the per-support view and `rankLayerMap_sigmaExactIndexEquiv` identifying each block with `exactMap A`. Downstream this means a layer conditional law is an ordinary `condDistrib` into a standard Borel space and mutual conditional independence supplies the finite products that finite-cylinder extensionality consumes — no product kernel anywhere. `lowerIndexSuccEquiv`/`lowerFactorSpaceSuccEquiv` give the split `LowerFactorSpace (n+1) ≃ᵐ LowerFactorSpace n × RankLayerSpace n`; `lowerToBoundaryProjection` reads the boundary at each rank-`n` support, definitionally compatible with `boundaryMap`. The relabeling actions `rankSupportEquiv`/`rankLayerIndexEquiv`/`rankLayerSpaceEquiv` are automorphisms of fixed types, so the action laws need no dependent transport; the square `lowerIndexSuccEquiv_rankLayerIndexEquiv` against the successor split is **not** definitional, since the split branches on `card < n` and the two sides' branch conditions agree only after transporting anchor cardinality through the image map. The **space-level** successor square `lowerFactorSpaceSuccEquiv_lowerFactorSpaceEquiv` *is* definitional, escaping the case split because it is built from `lowerIndexSuccEquiv.symm`, a `Sum.elim` that computes on the constructors. Per-support API for units 2 and 3: `rankLayerToExactProjection` (with `rankLayerToExactProjection_rankLayerMap` definitional), and the naturality squares for it, for `lowerToBoundaryProjection`, and for the support/exact bridge — all definitional, so per-support kernel identification and coherent randomization inherit them without transport bookkeeping
* `Graphon.RelRankLatents` — R4 converse piece 3 (#107), the latent-side prerequisite for the coupled rank induction: `RankLatentIndex n` is the finite tagged supports of cardinality `< n` (so it contains `∅` exactly when `0 < n`), `RankLatentSpace n` is their real-valued cube, and `rankLatentSource n` supplies one independent `uniform01` coordinate per support. Rank nesting and its projection cocycle are definitional. `rankLatentIndexEquiv`/`rankLatentRelabel` give the genuine finitely-supported sortwise action and preserve the source exactly. At rank one, `rankLatentOneEquiv` is evaluation at the unique empty-support coordinate and pushes the source to `uniform01`. The successor measurable equivalence splits the source into the old rank-`n` latents and a fresh `RankSupport S n → ℝ` layer, with both the source-product identity and the relabeling square; unlike `LowerFactorSpace`, this is an `ℝ`-cube indexed by tagged supports, related to the Boolean coherent factor only later through a rank coding
* `Graphon.RelRankOneCondIndep` — R4 converse piece 3 (#107): the **rank-one mutual conditional independence**, `iCondIndepFun (fun v => exactMap {v}) invariantAlgebra M.law` — the singleton exact-anchor layers are mutually, not merely pairwise, conditionally independent given the invariant σ-algebra, for an arbitrary exchangeable law with no dissociation and no `NoNullary`. Proved entirely from the two-set `condIndep_fixingAlgebra` by peeling one vertex at a time: the accumulated events bundle into a single `fixingAlgebra s`-event by monotonicity, `{v} ∩ s = ∅`, so the two-set theorem conditions on `fixingAlgebra ∅ = invariantAlgebra` — the same algebra at every stage — and the products compose against the induction hypothesis. The peel is available *only* at rank one: for supports of rank `n > 1` the peeled support need not be disjoint from the accumulated union, and where it is not, that stage conditions on a larger algebra — and conditional independence is not preserved under enlarging the conditioning. A positive-rank intersection is not inevitable for every family, but it is possible, which is enough to break the induction. So no de Finetti representation, no mixing measure, and no identification of a mixing measure with an invariant conditional distribution is needed here
* `Graphon.DigraphMaps` — the minimal `Digraph.comap` pullback API for Mathlib's `Digraph` (mirroring `SimpleGraph.comap`; a Mathlib-upstream candidate tracked on #24), used by the D2 directed-law bridge
* `Graphon.InfiniteDigraphLaw` — Directed umbrella (#84) D2 (#86): the `PMF`-based finite directed law `ExchangeableDigraphLaw` (consistent under `Digraph.comap`), the finite bridge `digraphLawEquiv : ExchangeableDigraphLaw ≃ RelExchangeableLaw digraphSig` (via `finiteDigraphEquiv` + `PMF.toMeasure`/`Measure.toPMF`), and the headline `exchangeableDigraphLawEquiv : ExchangeableDigraphLaw ≃ InfiniteExchangeableDigraphLaw` composing with R2c — measurable structure stays on the relational carrier
* `Graphon.ExchangeableLawBlueprint` — annotation-only blueprint wrappers for the R2c relational (`relExchangeableLawEquiv`) and D2 directed (`exchangeableDigraphLawEquiv`) equivalences, keeping `Architect` out of the reusable foundational modules
* `Graphon.SamplerSources` — generic i.i.d. random sources (`uniform01`, `iidVertexSource`, `iidUniformSource`) shared by the graph and directed samplers
* `Graphon.Digraphon` — Directed umbrella (#84) D3a (#87): the five-component CAF `Digraphon` (four reciprocal-edge pair kernels + Bool loop, a.e. probability-vector + transpose law) with `ext`; measurable representatives; the transpose-symmetrized `pairSym`; and the **everywhere-valid 3-simplex representative** `simplexRep` (measurable, nonneg/sum-one/transpose-compatible everywhere, a.e.-equal to `pairProb`) — the prerequisite for the D3b sampler; no random sources yet
* `Graphon.DigraphSampler` — Directed umbrella (#84) D3b (#87): the per-pair four-state distribution `Digraphon.pairPMF`, the one-uniform categorical map `catOutcome` with its **exact four-state law** `uniform01_map_catOutcome`; the explicit finite/infinite digraph samplers (`sampleAdj` in the natural-number order, `sampleInfinite`, `sampleFinite`); the **exact finite-event product formula** over an arbitrary injective labeling; the sampled law (`sampleRelLaw` / `sampleDigraphLaw`) with the infinite-law identification through `exchangeableDigraphLawEquiv`; exchangeability and dissociation
* `Graphon.DigraphonConstructors` — Directed umbrella (#84) D3c (#87): the special-family digraphon constructors — the generic pointwise builder `Digraphon.ofFun`, the ordinary-graphon embedding `ofGraphon` (reciprocal edges fully correlated), the tournament digraphon `ofTournament` (exactly one direction per pair), and the asymmetric-kernel digraphon `ofKernel` (independent directions, all four products present) — each with its a.e. pair-kernel identification
* `Graphon.DigraphSamplerFamilies` — Directed umbrella (#84) D3c headlines (#87): the sampler laws of the special families — the embedded ordinary graphon samples exactly the undirected `W`-random graph (`map_sampleFinite_ofGraphon`, pushforward of `samplePMF` under the symmetric loopless embedding), the tournament digraphon samples an almost-sure tournament (`ofTournament_sample_isTournament`), and the asymmetric-kernel sample draws its two directions independently (`sampleEventIntegrand_ofKernel_ae`)
* `Graphon.RelationalTopology` — Generic AHK program R1b (#104): the Boolean-product topology / σ-algebra on `RelStructure` — compact/Polish/standard-Borel instances, measurability of the finite restrictions, the cylinder π-system `cylinders` generating the product σ-algebra (`generateFrom_cylinders_eq`; = Borel under the countability giving Polish), and finite-restriction measure extensionality (`ext_of_map_restrictFin`); no projective extension (that is R2)
* `Graphon.InverseCounting` — Inverse counting lemma, convergence equivalence
* `Graphon.Convergence` — Top-level convergence characterization

## Experimental

* `Graphon.Operations` — Pointwise product (direct sum and operator product are future work)
* `Graphon.Operator` — Kernel operator pointwise definition (full L² API is future work)
* `Graphon.Sampling` — W-random graph distribution (`sampleMass`) and expected edge density (concentration is proved in the `Sampling*` modules above, culminating in `Graphon.SamplingLemma`)
-/