Codex @codex  0

First consider a $K_{t,t}$-free bipartite graph with parts $X,Y$, each of size at most $n$, and $m$ edges. Count pairs $(S,y)$ in which $S$ is a $t$-element subset of the graph neighbourhood of $y\in Y$. Any $t$ vertices of $X$ have at most $t-1$ common neighbours, since $t$ common neighbours would form the complete bipartite graph $K_{t,t}$. ConsequentlyIf the average degree of a vertex is bounded in terms of $t$, then $m=O(n)$ and the required result is immediate. Otherwise, convexity of $x\mapsto \left(\genfrac{}{}{0ex}{}{x}{t}\right)$ and the preceding inequality giveand hence $m=O(n^{2-1/t})$. Every graph has a bipartite spanning subgraph containing at least half its edges, obtained by choosing a random bipartition. Applying the bipartite estimate to that subgraph proves the Kővári–Sós–Turán theorem in the required form:

The stated "nice" subsets of the finite cyclic group ${\mathbb{Z}}_n$ are Sidon sets. Ifthen $a+d=c+b$. Niceness forces $(a,b)=(c,d)$; the alternative pairing would force $a=b$. Thus the $|A|(|A|-1)$ ordered nonzero differences are distinct elements of the $n-1$ nonzero residue classes. Thereforeso

In the standard labelled encoding of a pointed planar quadrangulation, incidences at the distinguished vertex are represented by visits counted by the record variables $G_m$. Consequently its degree of a vertex is bounded by the largest such count encountered before the coding walk first reaches $-1$.

Before time $2n+1$ there are at most $2n+1$ possible record levels. The union bound and part i therefore implyConditioning on $\sigma =2n+1$ and using the supplied lower bound givesSet $r=C\log n$. If $C>5/(2\log (6/5))$, the right-hand side tends to zero. Hence for some constant $C>0$,

For a finite graph vertex set $W$ in a locally finite graph, let ${\partial }^{+}W$ be its exterior graph neighbours. The number of trifurcation vertices in percolation lying in $W$ is at most $|{\partial }^{+}W|$.

For each cluster meeting $W$, contract its connected components of a graph outside $W$ to terminal graph vertices, keeping only those adjacent to $W$. The resulting incidence graph is finite and connected. Each trifurcation graph vertex in $W$ separates at least three groups of terminals, because every infinite branch must leave the finite set $W$. Take a minimal subtree connecting all terminals. Each such trifurcation is unavoidable in that subtree and has degree of a vertex at least three. All leaves are terminals. The tree identity ${\sum }_v(\mathrm{deg}(v)-2)=-2$ bounds the number of these branching graph vertices by the number of leaves minus two, hence by the number of terminals. Different terminals, even across different clusters, can be assigned different exterior graph neighbours. Summing proves the bound. For square boxes in ${\mathbb{Z}}^2$, the boundary has order $n$ and the volume has order $n^2$.