claimroutine

Many complete grids by Jensen

Claim·§8.2 A complete grid with generic positions·inside lemGeneric complete grid with independent coordinates

Statement (paper)

Let the two pruned set sizes be

m,n'

and their edge density be

\delta

. Then the number of ordered complete

N

-by-

j

grids, allowing repetitions, is at least

m^N(n')^j\delta^{Nj}=t_n^{N+j-o(1)}

In plain English

If the two pruned vertex sets have sizes

m

and

n'

with edge density

\delta

, then the number of ordered complete

N

-by-

j

grids (repetitions allowed) is at least

m^N(n')^j\delta^{Nj}

, which equals

t_n^{N+j-o(1)}

Why it's here

This is a counting lower bound showing complete grids are plentiful in the pruned graphs, via Jensen's inequality applied to the edge density (the claim's working name). The abundance lets the later diagonal choice pick grids index by index that avoid every countable family of polynomial tests, which gives the algebraic independence in the parent lemma.

Classified routine:

This is the standard Jensen/convexity lower bound on homomorphism counts of complete bipartite graphs K_{N,j} in a bipartite graph of given edge density (the Sidorenko/Kővári–Sós–Turán-type counting argument), applied to the pruned sets.

Uses

Nothing else in the paper

Used by

claimDiagonal grid choice avoids all tests

Sources

PaperOpen

Section: §8.2 A complete grid with generic positions
Page: —
Label: —
Line: sections/07-algebra.tex:232

Leannot aligned

Phase 2 aligns this node to a Lean declaration.