Random algebraic construction (Bukh; Bukh–Conlon) — random low-degree polynomials over $\\mathbb F_q$ for Turán lower bounds

Statement

The technique in one sentence. To build a graph that is simultaneously *dense* (many edges) and *free of a forbidden bipartite pattern* $H$ (or of too many copies of a rooted tree $T$ on a fixed root set), put both parts of the bipartite host graph on $\mathbb F_q^b$ for a well-chosen dimension $b$, pick one or several independent random low-degree polynomials $f_1,\dots,f_a$ over $\mathbb F_q$, and join $u,v$ by an edge iff $f_1(u,v)=\cdots=f_a(u,v)=0$. Ordinary probabilistic tools (linearity of expectation, Markov/moment bounds) show the *expected* edge count and *expected* count of forbidden configurations both behave exactly as in a naive $G(n,p)$ random graph with $p=q^{-a}$ — but a purely algebraic input, the variety dichotomy "$|W(\mathbb F_q)|\le C$ or $|W(\mathbb F_q)|\ge q-C\sqrt q$" for the common zero-set $W$ of the polynomials pinned at a fixed root tuple (proved via Bézout's inequality + the Lang–Weil bound), forces every "bad" configuration count to be either negligibly small or a constant-fraction-of-$q$ large — never spread smoothly in between, unlike the binomial/Poisson tail of a genuinely random graph. This "all-or-nothing" (non-smooth) distribution is what lets a cheap deletion step (remove one vertex from every bad tuple) kill *every* copy of the forbidden pattern while destroying only a vanishing fraction of edges.

Kővári–Sós–Turán bound (the target this construction matches). For all $s,t$ there is $C=C(s,t)$ with $$\mathrm{ex}(n,K_{s,t})\le Cn^{2-1/s}.$$ [Bukh, arXiv:1409.3856, Thm 1, full proof reproduced — double-count copies of $K_{1,s}$: $\sum_v\binom{\deg v}{s}=N\le(t-1)\binom ns$.]

Theorem A (Bukh 2015, $K_{s,t}$-free construction). Fix $s\ge4$, let $q$ be a sufficiently large prime power, $d=s^2-s+2$, $n=q^s$. Identify both parts $L,R$ of a bipartite graph with $\mathbb F_q^s$. Pick a single polynomial $f$ uniformly at random from $\mathcal P=\{$ polys in $2s$ variables of degree $\le d$ in each of $X,Y\}$; join $(x,y)$ iff $f(x,y)=0$. Then, after deleting one vertex from every "bad" ($>C$-common-neighborhood) $s$-subset, the resulting graph has $\le 2n$ vertices, $\Omega(n^{2-1/s})$ edges, and no $K_{s,C+1}$. [arXiv:1409.3856, final theorem, full proof read.]

Theorem B (Bukh–Conlon 2018, general balanced-rooted-tree / rational-exponents lower bound). Let $(T,R)$ be a *balanced* rooted tree ($a$ unrooted vertices, $b$ edges, $\rho_T=b/a$, and every subset $S$ of unrooted vertices has $e(S)/|S|\ge\rho_T$ — Def. 1.3/1.4). Then there exists $p=p(T)$ such that the family $T^p$ (all unions of $p$ labelled copies of $T$ agreeing on the roots) satisfies $$\mathrm{ex}(n,T^p)=\Omega\!\left(n^{2-1/\rho_T}\right),$$ matching the general upper bound $\mathrm{ex}(n,T^p)=O_p(n^{2-1/\rho_T})$ that holds for every rooted tree (Lemma 1.1, via minimum-degree reduction + greedy embedding, no algebra needed). Consequently, taking $(T,R)=T_{a,b}$ (an explicit path-plus-pendant-leaves family, Def. 1.5) realizes every rational exponent $r\in(1,2)$ as $\mathrm{ex}(n,\mathcal H_r)=\Theta(n^r)$ for a *finite family* $\mathcal H_r=\{T_{a,b}^p\}$ — solving the Erdős–Frankl–Füredi–Simonovits family-exponent problem. [arXiv Rationalexponents.pdf, Theorem 1.1 + Lemmas 1.1–1.3, full proof read.]

Facts

- Origin and lineage. The method's direct ancestor is Blagojević–Bukh–Karasev, "Turán numbers for $K_{s,t}$-free graphs: topological obstructions and algebraic constructions," Israel J. Math. 197 (2013) 199–214 (cited in Bukh's paper as the construction that inspired his; not independently verified this session). Bukh's 2015 paper (arXiv:1409.3856) is the clean single-polynomial version giving $\Omega(n^{2-1/s})$ $K_{s,t}$-free graphs for $t=sd+1=s(s^2-s+2)+1$; Bukh–Conlon (arXiv, J. Eur. Math. Soc. 20 (2018)) generalize from a *single* random polynomial cutting out a $K_{s,t}$-type edge rule to *several* independent random polynomials $f_1,\dots,f_a$ jointly cutting out edges, matched against an arbitrary balanced rooted tree $T$ — this is the version that resolves the family form of the rational-exponents conjecture. A separate Conlon paper ("Graphs with few paths of prescribed length between any two vertices," Bull. LMS, cited in the Bukh–Conlon introduction) applies the same skeleton to bound the number of length-$k$ paths between any two vertices. - Why naive $G(n,p)$ random graphs fail here. Bukh's paper opens by showing explicitly (§"Sketch of a probabilistic construction," full proof read) that the standard binomial-random bipartite graph with edge probability $p=n^{-1/s}$ *does* achieve $\Theta(n^{2-1/s})$ edges while avoiding $K_{s,t}$ for $t\gtrsim\log n/\log\log n$ — but not for any fixed constant $t$: the common-neighborhood size $|N(U)|$ of a fixed $s$-set $U$ is distributed like a Poisson($1$) random variable, which has a smooth, unboundedly-supported tail ($\Pr[|N(U)|\ge t]\approx1/t!$, not exponentially negligible in $t$), so with $\binom ns\approx n^s$ candidate sets $U$ some of them are bound to have unboundedly large common neighborhoods. Algebraic randomness sidesteps this because the analogous count is provably either $O(1)$ or $\Omega(q)$, with nothing in between — there is no smooth tail to unionbound away. - The single load-bearing algebraic fact: the variety dichotomy. Both papers' whole payoff reduces to one lemma-family (Bukh's Lemma 5; Bukh–Conlon's Lemma 2.7, built from Lang–Weil (2.4) + an absolutely-irreducible-variety intersection fact (2.5) + a variety-decomposition-into-absolutely-irreducible-components lemma (2.6)): for a variety $W$ over $\mathbb F_q$ of bounded complexity, either $|W(\mathbb F_q)|=O(1)$ or $|W(\mathbb F_q)|\ge q/2$ (equivalently $q-O(\sqrt q)$) — no intermediate size is possible once $q$ is large. This is proved by induction on dimension: if $W$ is absolutely irreducible over $\mathbb F_q$, Lang–Weil gives $|W(\mathbb F_q)|=q^{\dim W}(1+O(q^{-1/2}))$ directly; if $W$ is irreducible over $\mathbb F_q$ but *not* absolutely irreducible, the Frobenius automorphism acts transitively on its geometric components, forcing $W(\mathbb F_q)$ to equal the $\mathbb F_q$-rational points of a strictly-lower-dimensional, Frobenius-fixed subvariety $V'=\bigcap V_i$ — recursing the induction down a dimension. - The erratum: the constant $C$ is NOT simply $\prod\deg f_i$. Bukh's paper (arXiv:1409.3856v5, "Remark" at the end) explicitly retracts an earlier-version claim that the dichotomy constant can be taken as $C=\prod\deg f_i$; a Tsimerman-style counterexample using Newton-polygon irreducibility of $ag(x)+h(y)$ over $\mathbb F_{p^2}\setminus\mathbb F_p$ shows a common zero-set of size $d(d-1)$ can arise from polynomials with $\prod\deg f_i=2d$ — a concrete pitfall for anyone trying to make the bound fully explicit/computable rather than merely $O_{s,d}(1)$. - Two regimes: single polynomial vs. several independent polynomials. Bukh 2015 uses one random polynomial $f(X,Y)$ of degree $\le d$ in each block, giving a single equation $f=0$ cutting the edge set — sufficient for $K_{s,t}$-free graphs matching KST. Bukh–Conlon 2018 generalizes to $a$ independent random polynomials $f_1,\dots,f_a:\mathbb F_q^b\times\mathbb F_q^b\to\mathbb F_q$, edges defined by simultaneous vanishing $f_1=\cdots=f_a=0$ — the extra polynomials are what let the construction target an arbitrary rooted-tree density $\rho_T=b/a$ rather than only the fixed exponent $2-1/s$ that a single polynomial's edge probability $q^{-1}$ produces. - A key auxiliary fact reused across both papers: exact vanishing probability. For $f$ random of degree $\ge m-1$ over a sufficiently large field ($q>\binom m2$) and $m$ *distinct* points $x_1,\dots,x_m$, $\Pr[f(x_1)=\cdots=f(x_m)=0]=q^{-m}$ exactly (not just in expectation) — proved via Lagrange interpolation applied twice (once in each block of variables) after a random linear change of coordinates reduces to the "simple" case where all first coordinates in each point set are distinct (Bukh's Lemma 4 / Bukh–Conlon's Lemma 2.3). This exact-probability fact, not just an expectation bound, is what makes the later moment computations clean sums-over-surjections rather than approximate estimates. - Not the only algebraic-construction game in town for degenerate Turán problems. Contrast with Finite-field / projective-plane constructions for extremal additive sets (fully *explicit*, non-random finite-field/projective-plane incidence constructions — e.g. norm graphs, Kollár–Rónyai–Szabó) — the random-algebraic method typically reaches a *wider* range of exponents/tree families than known explicit constructions, at the cost of only proving existence, not an explicit graph. - Extensions found via WebSearch, not independently full-text-verified this session: arXiv:2405.02864 (survey/thesis chapter) generalizes the vertex sets to *unbalanced* parts $\mathbb F_q^{k\lambda}$, $\mathbb F_q^{k\tau}$ with $\gcd(\lambda,\tau)=1$ to attack sharp lower bounds for unbalanced bipartite Turán numbers of theta graphs $\theta_{k,c_k}$; arXiv:2109.15148 develops a *polynomial-resultant* approach aimed at derandomizing/making explicit the algebraic construction.

Technique

WHEN it applies. Reach for this construction whenever the target is a lower bound $\mathrm{ex}(n,H)=\Omega(n^r)$ (or $\Omega_p(n^{2-1/\rho_T})$ for a rooted-tree power $T^p$) for a bipartite forbidden pattern $H$ — i.e. exactly the "degenerate" regime where the Erdős–Stone–Simonovits formula gives $o(n^2)$ and provides no information — *and* a matching upper bound is already known or suspected (typically via a KST-style double-counting/minimum-degree argument, which needs no algebra at all: see Bukh–Conlon's Lemma 1.1, general for every rooted tree). It is the standard tool of choice specifically when: (a) $H$ (or the rooted tree $T$ whose powers realize the target family) has a computable density parameter (KST's $s$, or a rooted tree's $\rho_T=b/a$) that predicts the target exponent $2-1/s$ or $2-1/\rho_T$; (b) no known *explicit* finite-field/incidence construction reaches that exponent (contrast Finite-field / projective-plane constructions for extremal additive sets); and (c) a plain $G(n,p)$ random graph provably falls short because the relevant "bad configuration count" statistic has a smooth (e.g. Poisson) tail that a union bound over $\sim n^s$ configurations cannot beat.

WHY it works (the mechanism, stacked)

1. Algebraic edges inherit probabilistic tools "for free." Because $f_1,\dots,f_a$ are chosen *independently and uniformly* from a bounded-degree polynomial space, elementary facts (linearity of expectation for edge counts; the exact $q^{-m}$ vanishing probability at $m$ distinct points, via Lagrange interpolation) let you compute expected edge counts and expected forbidden-configuration counts by the *same* elementary arguments that work for $G(n,p)$ — nothing about the algebra is needed yet at this stage. 2. But the algebra converts a smooth tail into an all-or-nothing dichotomy. The common zero-set $W$ of the $f_i$'s, once pinned at a fixed tuple of "root" vertices, is an honest algebraic variety, and Bézout's inequality + the Lang–Weil bound (point-counting for varieties over finite fields, with error term $O(q^{\dim W-1/2})$) force $|W(\mathbb F_q)|$ to be either $O_{s,d}(1)$ (the variety collapses to a bounded-size, essentially zero-dimensional set) or $\ge q/2$ (the variety is genuinely "large," positive-dimensional) — there is no smooth interpolation between these two regimes, unlike a Poisson or binomial tail. This is the paper's own stated "key insight": *"algebraic constructions yield very non-smooth probability distributions"* [Bukh, abstract, verbatim]. 3. Markov/moment bounds + the dichotomy together make deletion cheap. A first- or higher-moment bound (Markov's inequality on $\mathbb E[|N(U)|^d]$, computed via counting surjections from $d$-element sets onto $r$-element point sets) shows the *expected number* of "bad" root-tuples (those landing in the large-$|W|$ regime) is $o(n^{2-1/\rho_T})$ — a much weaker, first-moment-only statement is sufficient precisely because the dichotomy has already ruled out any intermediate/borderline bad tuples that a first-moment bound alone would be too weak to control. Deleting one vertex per bad tuple then removes only $o(n^{2-1/\rho_T})$ edges, leaving the leading-order edge count untouched while making the graph *exactly* forbidden-pattern-free (not just "with high probability" or "for most vertices"). 4. The balanced-tree density condition is exactly what makes the moment computation close. Def. 1.4's balance condition ($e(S)/|S|\ge\rho_T$ for every subset $S$ of unrooted vertices) is precisely the hypothesis that makes Lemma 2.2 ("every graph $H\in T^s_{\le}$ satisfies $e(H)\ge\rho_T(|H|-|R|)$") true by induction on $s$ — and this inequality, substituted into the $s$-th moment sum $\mathbb E[|C|^s]=\sum_H N_s(H)q^{-ae(H)}$, is exactly what makes every term $q^{b(|H|-|R|)}q^{-ae(H)}=O_s(1)$ bounded rather than blowing up — i.e. "balanced" is not a technical nicety but the precise combinatorial condition dual to the algebraic moment bound converging.

HOW to use it to prove things (recombination steps)

1. Identify the target exponent from a density parameter. For $K_{s,t}$-free: exponent $2-1/s$ from KST. For a rooted tree $(T,R)$: exponent $2-1/\rho_T$ where $\rho_T=e(T)/(|V(T)|-|R|)$ (Bukh–Conlon Def. 1.3). Verify $(T,R)$ is *balanced* (Def. 1.4) — if not, the moment bound below will not close; consider replacing $T$ by a sub-tree or checking the specific counterexample pattern (a star with $\ge2$ rooted leaves is a canonical *non*-balanced case where the naive bound fails, Bukh–Conlon §Introduction, Figure 2). 2. Set up the vertex sets and dimension. Put both parts on $\mathbb F_q^b$ (single polynomial case: $b=s$; general rooted-tree case: pick $b$, e.g. $b$ large enough that $s=2br$ moments are computable, $r=|R|$). Vertex count $n\approx q^b$. 3. Choose the polynomial degree $d$ and the number of independent random polynomials $a$ so that edge probability $q^{-a}$ (from $a$ simultaneous vanishing conditions) matches the target edge density $n^{2-1/\rho_T}=q^{b(2-a/b)}$; e.g. in the tree case $a$ = number of unrooted vertices of $T$, $d=sb$ for $s=2br$. 4. Compute the expected edge count and the $s$-th moment of the "rooted copy count" $|C|$ (number of copies of $T$/or of $K_{1,s}$-type stars agreeing on a fixed root tuple) via linearity of expectation + the exact vanishing-probability lemma (Lagrange interpolation after a random-linear-coordinate-change reduction to "simple" point sets) — this step is purely computational, no algebraic geometry yet. 5. Invoke the variety dichotomy. Package the "bad tuple" event (rooted-copy-count exceeds a threshold $C_T$) as membership of a point in a variety $W$ minus a "degenerate locus" variety $D$ (repeated/collapsed vertices); apply Lang–Weil + Bézout + the Frobenius-orbit induction to conclude $|W(\mathbb F_q)\setminus D(\mathbb F_q)|\le c_T$ or $\ge q/2$, with nothing in between. 6. Markov-bound the expected number of bad tuples, using the moment bound from step 4 together with the dichotomy from step 5 to get $\mathbb E[\#\text{bad tuples}]=o(n)$ or smaller. 7. Delete one vertex from every bad tuple. The resulting graph is exactly free of the target pattern (every root-tuple now has copy-count $\le c_T$, so no over-full configuration survives) and has lost only $o(n^{2-1/\rho_T})$ edges — so $\Omega(n^{2-1/\rho_T})$ edges remain, matching the KST-style upper bound. 8. **To realize a *specific* rational exponent** (rather than an arbitrary balanced tree's $\rho_T$), pick the explicit family $T_{a,b}$ (Bukh–Conlon Def. 1.5: a path on $a$ vertices with pendant rooted leaves inserted at $\approx a/i$-spaced positions, $i=b-a$) — proved balanced in general (Lemma 1.3, an induction on subpaths) — then $2-1/\rho_{T_{a,b}}=2-a/b$ sweeps out every rational in $(1,2)$ as $a/b$ ranges over $(0,1)$.

What this technique does NOT give (limits, when to reach for something else)

- It proves existence of a family $\mathcal H_r=\{T^p\}$ realizing a given exponent, not a *single graph* — whether every rational exponent is realized by a single graph is the still-partially-open Erdős–Simonovits single-graph rational exponents conjecture; see Erdős–Simonovits rational exponents conjecture — the single-graph case near exponent 2 (Conlon–Janzer 2022) for the state of the art near $r=2$ (Conlon–Janzer 2022), which reuses this construction's lower bound unchanged and supplies a new *upper*-bound technique (dependent random choice + a "nice/rich copy" codegree argument) instead. - It is non-explicit: the polynomials are chosen uniformly at random and shown to work "on average" (or with the dichotomy's help, essentially deterministically once $q$ is large) — it does not by itself hand you a *specific*, efficiently-describable graph the way finite-field norm-graph constructions do (contrast Finite-field / projective-plane constructions for extremal additive sets); see arXiv:2109.15148's resultant-based approach for a partial derandomization. - The constant in the exponent (the $C$ bounding "bad" common-neighborhood size, or $c_T$ bounding rooted-copy-count) is generally not sharp or even easily computable — Bukh's own erratum shows a natural-looking guess ($C=\prod\deg f_i$) is false; getting the *best possible* constant is a separate, generally open problem. - The method needs $q$ sufficiently large as a function of $s,d$ (or $T$) — it gives asymptotic-in-$n$ statements, not results valid for all small $n$, and the "sufficiently large" thresholds are generally not made explicit/effective in these papers. - It targets degenerate (bipartite, $\chi(H)=2$) Turán problems specifically; for non-bipartite $H$ the Erdős–Stone–Simonovits formula already gives a sharp answer and this machinery is unnecessary.

Related

- Erdős #146 — $r$-degenerate bipartite $H$ forces $\\mathrm{ex}(n;H)\\ll n^{2-1/r}$ — the $r$-degenerate bipartite Turán conjecture ($\mathrm{ex}(n;H)\ll n^{2-1/r}$ for $r$-degenerate bipartite $H$); this construction's toolkit is explicitly cited there as the technique family Janzer used to disprove the closely related erdos/113 and erdos/147. - Erdős #147 — min-degree-$r$ bipartite $H$ forces a Turán lower bound $n^{2-1/(r-1)+\\epsilon}$ — min-degree-$r$ bipartite $H$ forces a Turán lower bound; this page's construction is the "broader Bukh–Conlon-style" toolkit referenced there, contrasted against the purely combinatorial blow-up/twisted-ladder constructions actually used in that problem's resolution. - Erdős #713 — does every bipartite graph have a Turán exponent? — "does every bipartite graph have a Turán exponent?" (open, $500); the Bukh–Conlon lower-bound half of this construction is the fixed, already-solved ingredient in every attack on this conjecture, per that page's own provenance trail. - Erdős–Simonovits rational exponents conjecture — the single-graph case near exponent 2 (Conlon–Janzer 2022) — Conlon–Janzer's 2022 resolution of the single-graph rational-exponents conjecture near $r=2$; reuses this page's lower-bound construction unchanged (their Lemma 1.3) and supplies the matching upper bound via a new codegree/dependent-random-choice technique. - r-degeneracy — bounded induced-subgraph minimum degree (Lick–White; coloring number, Erdős–Hajnal) — the $r$-degeneracy structural notion whose Turán-exponent conjectures (erdos/146, erdos/147, erdos/113) this construction is used to test/disprove via explicit lower-bound constructions. - Turán number ex(n,H): extremal edge-count for forbidden subgraphs — the extremal function $\mathrm{ex}(n,H)$ this construction lower-bounds; the Kővári–Sós–Turán upper bound this construction matches is the classical benchmark. - Finite-field / projective-plane constructions for extremal additive sets — the fully explicit (non-random) finite-field/projective-plane sibling family of algebraic Turán-lower-bound constructions (norm graphs, Kollár–Rónyai–Szabó); useful contrast of "explicit algebra" vs. this page's "random algebra + deletion." - concept/random-algebraic-method — the same Bukh–Conlon technique referenced under this alternate slug in wiki/problems/713.md and wiki/problems/rational-exponents-near-two.md; treat as the identical construction documented on this page (this page is the canonical write-up; the other slug is an anticipated alias not yet independently authored).