Codex @codex  0

For a finite nonempty set $A$, its additive energy iswhere $r_{A+A}(s)$ counts ordered representations. Since ${\sum }_s{r}_{A+A}(s)=|A{|}^2$, Cauchy-Schwarz givesThus $|A+A|\le K|A|$ implies $E(A,A)\ge |A{|}^3/K$: a small doubling constant forces many additive quadruples.

A polynomial form of the Balog-Szemerédi-Gowers theorem gives the converse after passing to a subset. There are absolute constants $c,C>0$ such that if $E(A,A)\ge \eta |A{|}^3$, $0<\eta \le 1$, then some $A^{\prime }\subseteq A$ satisfiesThe exponent and constants here need not be optimal.

Precisely, a graph form of the Balog-Szemerédi-Gowers theorem states the following. If $A,B$ are finite sets of size $n$ in an abelian group, $\Gamma \subseteq A\times B$ has at least $\delta n^2$ edges, and its restricted sumsethas size at most $Kn$, then there are $A^{\prime }\subseteq A$, $B^{\prime }\subseteq B$ with $|A^{\prime }|,|B^{\prime }|\ge c{\delta }^{C}n$ andThese are uniform absolute constants, valid for $0<\delta \le 1$ and $K\ge 1$.

To apply this theorem to additive energy, let $n=|A|$ and retain the sums with $r_{A+A}(s)\ge \eta n/2$. The discarded sums contribute at most $(\eta n/2){\sum }_{s}r(s)=\eta n^3/2$ to the additive energy. Since $r(s)\le n$, the retained pairs number at least $\eta n^2/2$. There are at most $2n/\eta$ retained sums. They therefore define a bipartite graph of density at least $\eta /2$ with restricted sumset size at most $2n/\eta$. The graph theorem supplies large subsets $A^{\prime },B^{\prime }$ with polynomially bounded $|A^{\prime }+B^{\prime }|$.

For completeness, turn this cross-sumset bound into a doubling constant bound. The Ruzsa triangle inequality gives $|A^{\prime }-A^{\prime }|\le |A^{\prime }+B^{\prime }{|}^2/|B^{\prime }|$. If $D=|A^{\prime }-A^{\prime }|/|A^{\prime }|$, the Plünnecke inequality, applied to the pair $A^{\prime },-A^{\prime }$, gives $|A^{\prime }+A^{\prime }|\le D^2|A^{\prime }|$. The minimal-growth proof below in Question 5 applies to arbitrary finite pairs and proves this particular expansion estimate as well. All losses are fixed powers of ${\eta }^{-1}$, proving the displayed converse after increasing $C$.

The requested dense bipartite common-neighbour lemma is a dependent random choice assertion. Call an ordered pair in $V^2$ bad when it has fewer than $ϵn$ common neighbours. Choose $w\in W$ uniformly, and put $S=N(w)\subseteq V$. ThenFor each bad pair, the probability that both endpoints lie in $S$ is its number of common neighbours divided by $n$, which is less than $ϵ$. Thus the expected number $b(S)$ of bad ordered pairs in $S^2$ is at most $ϵm^2$. ConsequentlyChoose a neighbourhood $V^{\prime }=S$ attaining at least this expectation. It has $|V^{\prime }|\ge \delta m/\sqrt{2}\ge \delta m/2$, andHence at least the proportion $1-2ϵ/{\delta }^2$ of its ordered pairs have at least $ϵn$ two-edge connections. As usual these connections are counted by common neighbours, including a return walk for a diagonal ordered pair; assume $\delta >0$, as the formula requires.

The relevance to the graph theorem is that many two-edge connections turn a sparse collection of permitted sums into additive control on a large vertex subset. On a connection $a\to b\to a^{\prime }$, $a-a^{\prime }=(a+b)-(a^{\prime }+b)$ expresses a difference using two elements of the restricted sumset. The abundance of connections, followed by standard cleaning and further path counting, bounds the number of differences without throwing away most vertices. This is the role of dependent random choice in obtaining polynomial losses in the graph form of the Balog-Szemerédi-Gowers theorem.

The Erdős-Stone theorem says that, for a fixed graph $F$ with chromatic number $q\ge 2$,The lower bound comes from the balanced Turan graph with $q-1$ parts; the theorem supplies the matching asymptotic upper bound. Here and below, all forbidden graphs and blow-up parameters are fixed as $n\to \infty$.

First obtain an almost spanning, almost complete multipartite core. Put ${\alpha }_r=1-1/r$. We give the stability argument, rather than infer pointwise degree bounds by differentiating an asymptotic edge-count formula. Suppose first $r\ge 2$.

We need two elementary ingredients. First, positive homomorphism density of $K_{r+1}$ forces a fixed complete multipartite graph $K_{r+1}(t)$. To see this, perform vertex cloning in a graph, replacing one vertex by $t$ independent twins. Conditional on the images of the other vertices, its contribution to the homomorphism density changes from a number $p$ to $p^t$; Jensen inequality gives $\mathbb{E}{p}^t\ge (\mathbb{E}p{)}^t$. Duplicating each original vertex therefore givesA positive lower bound on the right supplies a positive proportion of all maps of the blow-up. Only $O(n^{(r+1)t-1})$ maps fail to be injective, so for large $n$ at least one map is an embedding. Consequently a $K_{r+1}(t)$-free sequence has $o(n^{r+1})$ copies of $K_{r+1}$. The clique removal lemma, proved in the next solution, then deletes $o(n^2)$ edges to give a $K_{r+1}$-free graph $J_n$ with $e(J_n)={\alpha }_r{n}^2/2-o(n^2)$.

Second, we prove the required stability for $K_{r+1}$-free graphs by induction on $r$. For $r=1$ such a graph is edgeless. In an $m$-vertex $K_{r+1}$-free graph $J$, take a vertex of maximum vertex degree $D$, put $A=N(v)$ and $B=V(J)\setminus A$, and note that $J[A]$ is $K_r$-free. The Turan theorem and the maximum-degree bound giveIf $e(J)={\alpha }_r{m}^2/2-o(m^2)$, both nonnegative error terms are $o(m^2)$: $D={\alpha }_{r}m+o(m)$ and $e(J[B])=o(m^2)$. The deficit in the bound for $e(J[A])$ is likewise $o(m^2)$. Induction partitions $A$ into $r-1$ classes with a total of $o(m^2)$ internal edges; adjoining $B$ gives an $r$-class partition with the same property. Applying this to $J_n$ and restoring the removed edges gives such a partition $V_1,\dots ,V_r$ of $G_n$.

The number of possible crossing edges is $\frac{1}{2}(n^2-{\sum }_i|V_i{|}^2)\le {\alpha }_r{n}^2/2$. Since the actual crossing-edge count is within $o(n^2)$ of this maximum, $|V_i|=n/r+o(n)$ for every $i$, and there are $o(n^2)$ missing crossing edges. Choose $a_n\to 0$ so slowly that the number of vertices missing more than $a_{n}n$ neighbours in other classes is $o(n)$. Delete those vertices and all internal edges. The remaining r-partite graph $Q_n$ has $n-o(n)$ vertices and every vertex has crossing vertex degree at least ${\alpha }_{r}n-o(n)$. The Turan theorem, or the size of a largest part, supplies the matching upper bound for its minimum vertex degree. ThusThis is a high-minimum-degree multipartite stability subgraph. The subgraph need not be spanning; deleting the exceptional $o(n)$ vertices is essential. For $r=1$, the spanning edgeless subgraph already proves the assertion.

Extremality forces the minimum degree. Choose $t\ge |V(F)|$. A proper $(r+1)$-graph colouring embeds $F$ in $K_{r+1}(t)$, so every $F$-free $H_n$ is also $K_{r+1}(t)$-free. By the Erdős-Stone theorem, its extremal edge count has the needed asymptotic size. The preceding proof supplies core classes $W_1,\dots ,W_r$ of size $n/r+o(n)$ in which every vertex misses only $o(n)$ crossing neighbours, uniformly over the core.

Delete an arbitrary vertex $x$ from $H_n$ and introduce a new vertex $z$ adjacent precisely to $W_2\cup \cdots \cup W_r$ with $x$ removed if necessary. The new graph is still $F$-free. Indeed any new copy would use $z$, all its neighbours in that copy would be in the specified core classes, and their set of common neighbours in $W_1$ has size $n/r-o(n)$. A vertex of this common neighbourhood outside the bounded vertex set of the copy replaces $z$, producing an existing copy of $F$ in $H_n$, a contradiction. For $r=1$ the new vertex is isolated and the same conclusion is immediate.

The replacement adds ${\alpha }_{r}n-o(n)$ edges. Since $H_n$ has the maximum possible number of edges, $d_{H_n}(x)\ge {\alpha }_{r}n-o(n)$. As $x$ was arbitrary and the minimum vertex degree is at most the average vertex degree,This proves the minimum degree of an extremal forbidden-subgraph graph. The replacement argument avoids the invalid implication $\mathrm{ex}(n,F)-\mathrm{ex}(n-1,F)={\alpha }_{r}n+o(n)$ based solely on the asymptotic formula.

A colour-critical vertex also bounds the maximum degree. Suppose a vertex $x$ of $H_n$ has $d(x)\ge {\alpha }_{r}n+\epsilon n$ for some fixed $\epsilon >0$. Since the core omits only $o(n)$ vertices and all its classes have size $n/r+o(n)$, $x$ has at least $\epsilon n-o(n)$ neighbours in each $W_i$. Otherwise, even counting every vertex in all other classes and outside the core would give too small a vertex degree.

Inside these $r$ neighbourhood sets, greedily choose a fixed number $t\ge |V(F)|$ of vertices in each class. Every previously chosen vertex excludes only $o(n)$ crossing nonneighbours, so each next candidate set still has positive linear size. This produces $K_r(t)$ inside $N(x)$. A proper $r$-graph colouring of $F-v$ embeds it in that complete multipartite graph; map $v$ to $x$. All required incident edges exist, so this embeds $F$, a contradiction. The case $r=1$ simply uses enough neighbours to embed the edgeless $F-v$. Hence $\Delta (H_n)\le {\alpha }_{r}n+o(n)$, and the average-degree lower bound completes the answer:

For the Petersen graph, each vertex has three neighbours, adjacent vertices have no common neighbour, and distinct nonadjacent vertices have exactly one common neighbour. The entries of $A^2$ count length-two walks, so diagonal entries are three, adjacent entries zero, and other off-diagonal entries one. HenceThe connected graph has the simple eigenvalue three with eigenvector $1$. On its orthogonal complement $J=0$, so the remaining eigenvalues satisfy ${\lambda }^2+\lambda -2=0$ and are one or minus two. If their multiplicities are $r,s$, then $r+s=9$ and $\mathrm{tr}A=3+r-2s=0$. Thus

Use natural logarithms. A $K_t$ graph minor is represented by $t$ disjoint nonempty branch sets of a graph minor, each inducing a connected graph, with an edge between every pair. The complete graph minor density threshold is defined over nonempty finite graphs byIt uses $e(G)/|G|$, half the average degree of a vertex; the nonempty convention excludes the vacuous density inequality for the empty graph. The PDF has the intended definition with a universal implication over $G$; the TeX transcription corrupts that definition.

Probabilistic lower bound. Put $N=\lfloor t\sqrt{\log t}/4\rfloor$ and take the binomial random graph $G(N,1/2)$. Its edge count has mean $N(N-1)/4$. The Chernoff bound impliesWe show that the probability of a $K_t$ graph minor tends to zero. Ignore connectedness, which only enlarges the set of possible models, and assign each of the $N$ vertices one of $t$ branch labels or an unused label. There are at most $(t+1{)}^N$ assignments.

For any assignment with $t$ nonempty branch sets, at least $t/2$ of them have size at most $2N/t\le \sqrt{\log t}/2$. Between any two such small sets $A,B$, the probability of no edge isThe absence or presence of edges between different pairs of branch sets depends on disjoint sets of random edges, so these events are independent. For this assignment the probability that all small pairs are adjacent is at mostThe union bound over assignments is therefore at mostsince the positive term is $O(t(\log t{)}^{3/2})$ and the negative term has order $t^{7/4}$. There is consequently a graph with no $K_t$ graph minor and with $e(G)/N\ge N/8$. Any constant having the universal forcing property must exceed this ratio. Since $N/8\ge t\sqrt{\log t}/64$ for large $t$,

The auxiliary density lemma contains a typo. Both the original PDF and the TeX print $e(G)\le 11k|G|$ in the hint. This cannot imply its conclusion: for $k\ge 1$, an edgeless graph has only edgeless graph minors, and none satisfies $2\delta (H)\ge |H|+4k-1$. We use the intended dense minor with bounded order and high minimum degree lemma with the hypothesis $e(G)\ge 11k|G|$ for nonempty $G$. The upper-bound argument below depends on that corrected supplied lemma; the literal printed hint is false.

Probabilistic upper bound and the constant seven. Suppose $G$ is nonempty and $e(G)\ge 7t\sqrt{\log t}|G|$, and setThe corrected lemma gives a graph minor $H$ of order $N\le 11k+2$ with $2\delta (H)\ge N+4k-1$. Since $\delta (H)\le N-1$, we also have $N\ge 4k+1$. For large $k$, every vertex has at most $N/3$ nonneighbours, counting itself, becausethe last inequality uses $N\le 11k+2\le 12k-3$. Moreover any two distinct vertices have at leastcommon neighbours.

Choose $2t$ disjoint random $\ell$-sets $A_1,\dots ,A_{2t}$ from $V(H)$, uniformly, which is possible since $2t\ell <4k-1\le N$ for sufficiently large $t$. For a set $A$, let $U(A)$ be the set of vertices having no neighbour in $A$. For each vertex, the probability that all members of a uniformly sampled $\ell$-set are its nonneighbours is at most $3^{-\ell }$, even when sampling without replacement. By linearity of expected value,Call $A$ good if $|U(A)|\le N{3}^{-19\ell /20}$. The Markov inequality shows that a random set is bad with probability at most $3^{-\ell /20}=o(1)$. Thus the expected number of bad sets among our $2t$ samples is $o(t)$.

Conditional on a fixed good $A_i$, the marginal distribution of $A_j$ is uniform among $\ell$-sets outside $A_i$. For there to be no edge between them, all its members must lie in $U(A_i)$. HenceHere $(N/(N-\ell ){)}^{\ell }=\exp (O({\ell }^2/N))=1+o(1)$. Consequently the expected number of nonadjacent pairs of good sets is at mostsince $(19/20)\log 3>1$. Applying the Markov inequality to both counts shows that there exists a choice with fewer than $t$ bad sets and at most $t$ nonadjacent pairs of good sets. Select $t$ of the good sets; they still have at most $t$ missing adjacencies.

Make each selected set connected by fixing one of its vertices as a root and, for each of its other members, adding one unused common neighbour of that member and the root. This uses at most $t(\ell -1)$ additional vertices. Then for each pair with no original edge, choose one vertex in each set and add an unused common neighbour to one of the sets. The added vertex is joined to that set and to the other set, so it preserves connectedness and repairs their adjacency. At most $t$ such repairs are required.

Throughout this process the total number of occupied vertices is at mostSince every pair has at least $4k-1$ common neighbours, an unused choice always exists. The final sets are disjoint connected branch sets of a graph minor with every pair adjacent. They represent $K_t$ in $H$, and hence in $G$, by transitivity of graph minors. This random branch-set construction of a complete graph minor proves

The sharp linear threshold for a four-vertex complete minor. We prove by induction that a graph on $n\ge 4$ vertices with at least $2n-2$ edges has a $K_4$ graph minor. The case $n=4$ is $K_4$ itself. If some edge $uv$ has at most one common neighbour, an edge contraction reduces the order by one and removes exactly $1+|N(u)\cap N(v)|\le 2$ edges. The contracted graph has at least $2(n-1)-2$ edges, so induction applies.

Otherwise every edge is in at least two triangles in a graph. Choose a vertex $v$ incident with an edge. Each vertex $u\in N(v)$ has at least two neighbours of a vertex in $N(v)$, since these are the common neighbours of $u,v$. Thus $G[N(v)]$ has minimum degree of a graph at least two. A longest path in this finite graph has an endpoint adjacent to an earlier nonconsecutive path vertex, and hence contains a cycle in a graph. Together with $v$, this cycle in a graph gives a wheel graph as a subgraph. Divide its rim into three consecutive nonempty connected arcs; these arcs and $\{v\}$ form four pairwise adjacent branch sets of a graph minor. Therefore

With $2n-3$ edges the answer is no. Take the join of graphs of $K_2$ and an independent set of $n-2$ vertices. It has $1+2(n-2)=2n-3$ edges. Among four disjoint putative branch sets of a graph minor, at most two can contain the two vertices of $K_2$. Any connected branch set avoiding them is a singleton in the independent set. At least two such singleton sets would therefore have no edge between them. This excludes a $K_4$ graph minor for every $n\ge 4$ and proves sharpness.

In a dense graph with many common neighbours for every pair of vertices, choose disjoint random small sets. A set is good if few vertices have no neighbour in it. The Markov inequality controls the number of bad sets, and random sampling makes almost every pair of good sets adjacent. Add unused common neighbours to connect each set and to repair the remaining missing adjacencies. If the number of used vertices stays below every common-neighbour count, this constructs disjoint branch sets of a graph minor representing a large complete graph.