LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-13

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The Kővári–Sós–Turán common-neighbour count and the discrete convexity lower bound for degree sums

Statement

Let $s, t \geq 1$ be integers, let $G$ be bipartite with parts $A, B$ , where $∣ A ∣ = m$ , $∣ B ∣ = n$ , and let $d (b) = ∣ N (b) \cap A ∣$ . If $G$ contains no oriented $K_{s, t}$ with $s$ vertices in $A$ , then

$\sum_{b \in B} (\binom{d (b)}{s}) \leq (t - 1) (\binom{m}{s}) .$

For $n \geq 1$ and any nonnegative integers $d_{1}, \dots, d_{n}$ with sum $E$ , moving one unit from a value at least two larger than another cannot increase $\sum_{i} (\binom{d_{i}}{s})$ . Consequently the minimum occurs when the values differ by at most one. If $E / n \geq s - 1$ , this gives

$\sum_{i = 1}^{n} (\binom{d_{i}}{s}) \geq \frac{n}{s!} {(\frac{E}{n} - s + 1)}^{s} .$

Facts & Assumptions

Given: The hypotheses and notation of the statement above.

[F1]

In $z (m, n; s, t)$ , the $s$ -vertex part of the forbidden $K_{s, t}$ lies on the left and the $t$ -vertex part lies on the right (The Zarankiewicz number $z (m, n; s, t)$ for a forbidden $K_{s, t}$ in a bipartite graph).

[F2]

The open neighbourhood is $N_{G} (v) = {u : {u, v} \in E}$ and $\deg_{G} (v) = ∣ N_{G} (v) ∣$ (Adjacency, incidence, open and closed neighbourhoods, vertex degree, minimum degree and maximum degree).

[F3]

For a finite incidence relation, the sum of its row-fibre sizes equals the sum of its column-fibre sizes (Double counting: $\sum_{x \in X} ∣ R_{x} ∣ = ∣ R ∣ = \sum_{y \in Y} ∣ R^{y} ∣$ for a relation between finite sets).

[F4]

$(\binom{n}{k})$ is the number of $k$ -element subsets of an $n$ -element set (The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ ).

Proof

technique · double-count common neighbours, then smooth integer degrees

1.1

Count pairs $(S, b)$ with $S \subseteq A$ , $∣ S ∣ = s$ , and $S \subseteq N (b)$ . Counting first by $b$ gives the left side. For fixed $S$ , at most $t - 1$ vertices of $B$ contain $S$ in their neighbourhood, or those vertices with $S$ form the forbidden $K_{s, t}$ . Counting first by $S$ proves the upper bound.

givenF1F2F3

1.2

Partitioning the $s$ -subsets of a $d$ -element set according to whether they contain one distinguished element gives $(\binom{d}{s}) - (\binom{d - 1}{s}) = (\binom{d - 1}{s - 1})$ , a nondecreasing function of $d$ . Thus if $d_{i} \geq d_{j} + 2$ , replacing $(d_{i}, d_{j})$ by $(d_{i} - 1, d_{j} + 1)$ does not increase the binomial sum. Repetition terminates at values $q = ⌊ E / n ⌋$ and $q + 1$ .

givenF4

2.1

For integers $d \geq s - 1$ , $(\binom{d}{s}) \geq (d - s + 1)^{s} / s!$ . Writing $E / n = q + θ$ with $0 \leq θ < 1$ , the balanced sum is the corresponding linear interpolation between $(\binom{q}{s})$ and $(\binom{q + 1}{s})$ ; convexity of $y \mapsto y^{s}$ on nonnegative reals bounds it below by $n (E / n - s + 1)^{s} / s!$ .

step 1.2algebraF4

3.1

Steps 1.1-2.1 prove the common-neighbour upper count and the discrete smoothing lower count with the stated threshold.

step 1.1step 1.2step 2.1∎

Depends on

Used by

Dependency tree · two levels

19 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Yufei Zhao, Graph Theory and Additive Combinatorics (standard reference, not scraped)