Counting induced three-vertex patterns in uniform triples of cells

If three cells A 0, A 1, A 2 of a graph G are pairwise ε-uniform, then for every graph J on Fin 3 the number of maps g with g i ∈ A i that induce J (edges of J go to edges of G and nonedges to nonedges) is the count predicted by independence, |A 0| |A 1| |A 2| ∏_{i < j} d_{ij}, up to an error 3 ε |A 0| |A 1| |A 2|. Here d_{ij} is the edge density of (A i, A j) when i and j are adjacent in J and the nonedge density 1 - d(A i, A j) otherwise. Since nonedges are counted too, this predicts every induced pattern, not only edge-preserving copies.

The argument has two steps.

• A ε-uniform pair (s, t) has small rectangle discrepancy: the number of edges between s' ⊆ s and t' ⊆ t is within ε |s| |t| of d(s, t) |s'| |t'|. Large rectangles are controlled by uniformity itself, and small ones because both counts are then at most |s'| |t'| ≤ ε |s| |t|. Testing against functions with values in [0, 1] instead of indicator functions does not increase the discrepancy (SimpleGraph.IsUniform.abs_sum_sum_mul_sub_le).
• Replacing the three pair indicators by their densities one at a time, every step is a test of one pair against two functions with values in [0, 1], summed over the third vertex.

The cells may overlap and need not be distinct; when they are pairwise disjoint, every counted map is injective. Summed over the triples of distinct parts of a uniform partition, this gives the contribution of transversal maps in counting lemmas for regular partitions, such as the induced counting lemma for strong graph regularity.

Main results

• SimpleGraph.abs_card_induced_fin_three_sub_le: the induced counting lemma for pairwise uniform triples of cells.

References

• Y. Zhao, Graph Theory and Additive Combinatorics, Cambridge University Press (2023), Chapter 4 (the graph counting lemma).

theorem SimpleGraph.abs_card_induced_fin_three_sub_le {α : Type u_1} {𝕜 : Type u_2} [Field 𝕜] [LinearOrder 𝕜] [IsStrictOrderedRing 𝕜] {G : SimpleGraph α} [DecidableRel G.Adj] {ε : 𝕜} (J : SimpleGraph (Fin 3)) [DecidableRel J.Adj] {A : Fin 3 → Finset α} (hA : ∀ (i j : Fin 3), i < j → G.IsUniform ε (A i) (A j)) : |↑{g ∈ Fintype.piFinset A | ∀ (i j : Fin 3), J.Adj i j ↔ G.Adj (g i) (g j)}.card - (∏ i : Fin 3, ↑(A i).card) * ∏ p : { p : Fin 3 × Fin 3 // p.1 < p.2 }, G.patternDensity (J.Adj (↑p).1 (↑p).2) (A (↑p).1) (A (↑p).2)| ≤ 3 * ε * ∏ i : Fin 3, ↑(A i).card

Induced counting lemma for three cells. Let A 0, A 1, A 2 be pairwise ε-uniform cells of G, and J a graph on Fin 3. Then the number of maps g with g i ∈ A i such that g i and g j are adjacent in G exactly when i and j are adjacent in J differs from |A 0| |A 1| |A 2| times the product, over the pairs i < j, of the edge density of (A i, A j) (if i and j are adjacent in J) or of its nonedge density 1 - d(A i, A j) (otherwise), that is SimpleGraph.patternDensity, by at most 3 ε |A 0| |A 1| |A 2|.