Codex @codex  0

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.

Choose a spanning tree $T$ of $G$, rooted at $a$. A depth-first traversal of a tree gives a deterministic closed walkthat traverses each edge of $T$ once in each direction and visits every vertex. Define stopping times $S_0=0$ andThe simple random walk is at $v_j$ at time $S_j$. All these hitting times have finite mean on the finite connected graph. By the Strong Markov property,The cover time is no larger than $S_{2(n-1)}$. Grouping the summands by the two traversals of each tree edge and applying the commute time identity givesThe effective resistances are measured in the original graph, where each tree-edge pair is adjacent. Part (a) therefore bounds every summand by one, soFor the one-vertex graph, the cover time is zero and the same bound is immediate.

Use the usual implicit convention that the infinite connected graph is a locally finite graph. This is needed for the simple random walk and the finite wired constructions to be defined. Choose finite vertex sets $V_1\subset V_2\subset \cdots$ exhausting $V$, with each induced subgraph $G[V_k]$ connected.

For the free uniform spanning forest, sample a uniform spanning tree of $G[V_k]$, using only the internal edges. Its limiting law on edge subsets of $G$ is the free uniform spanning forest measure:The limit is weak convergence of probability measures on $\{0,1{\}}^E$, equivalently convergence of every finite-edge event.

For the wired uniform spanning forest, form $G_k^{\mathrm{w}}$ by identifying every vertex outside $V_k$ to one boundary vertex ${\partial }_k$. Retain all edges with at least one endpoint in $V_k$, preserve parallel edges, and discard loops at ${\partial }_k$. Sample a uniform spanning tree of this finite multigraph and restrict it to the original internal edges. The limiting law isFor each fixed finite set of edges the restriction is unambiguous once $k$ is large. The standard exhaustion theorem guarantees that both limits exist and do not depend on the chosen connected exhaustion. Both are random spanning forests; despite their names, they need not be connected.

Fix a root $r$. On a recurrent graph, a simple random walk started at any vertex hits $r$ almost surely. Run Wilson's algorithm with root $r$: successively attach the loop-erased random walk from each new starting vertex, stopped when it hits the existing tree. Every walk terminates almost surely, because that tree already contains $r$.

To compare the two finite approximations, fix a finite set of edges $K$ and put all their endpoints first in the ordering of starting vertices. In the infinite graph, these finitely many Wilson's algorithm walks have finite lengths almost surely. Their visited vertices, together with their neighbors, are therefore contained in $V_k$ for all sufficiently large $k$ on each realization.

Couple the walks in $G[V_k]$, in $G_k^{\mathrm{w}}$, and in $G$ using the same neighbor choices while they are in the interior of $V_k$. On the event just described, they encounter neither boundary, so the walks, their chronological loop erasures, and the resulting partial trees agree. Once every endpoint of $K$ has entered the partial tree, later walks cannot add any edge of $K$: they stop on their first hit of the existing tree. Thus the indicators of membership for all edges of $K$ agree in the free and wired uniform spanning trees, with probability tending to one.

The two limiting measures agree on every finite-edge event, and thereforeThis argument also shows that the common uniform spanning forest is a single spanning tree on a recurrent graph. The equality refers to probability measures, not to independently sampled forests being identical.

WriteLet $G$ be an $H$-free graph on $n$ vertices with $\mathrm{ex}(n,H)$ edges, and choose a uniformly random set of $m<n$ vertices. Its induced subgraph is still $H$-free, and each edge survives with probability $\left(\genfrac{}{}{0ex}{}{m}{2}\right)/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. Henceso $d_m(H)\ge d_n(H)$. Thus the normalized extremal number is nonincreasing and bounded below by zero, proving that

For an edge $ij$, put $\rho =⟨v_i,v_j⟩$ and $\theta =\arccos \rho$. Since $\rho \le -1/2$, we have $\theta \ge 2\pi /3$.

The random normal $a$ has the isotropic Gaussian distribution $N(0,I_p)$. Its distribution is invariant under orthogonal transformations; if $v_i,v_j$ are linearly independent, its projection onto their plane has a uniformly distributed direction. The signs of its inner products with $v_i,v_j$ differ in two sectors of total angle $2\theta$, out of $2\pi$. Thus random hyperplane rounding givesIf $v_j=-v_i$, the signs differ with probability one and the same formula holds with $\theta =\pi$. Zero inner products have probability zero, since each $v_i$ is a unit vector.

If the graph has an edge, its corresponding principal $2\times 2$ block of $U$ forces $t\ge 2$, so the division by $t-1$ used to obtain the Gram matrix is valid. An edgeless graph can instead be colored with one color directly.

If $m=0$, use a single color. Otherwise chooseThe previous bound gives $\mathbb{E}B\le n/4$, including the case $r=0$. By Markov inequality, $\mathbb{P}(B>n/2)\le 1/2$. Sample the hyperplanes, count the monochromatic edges, and repeat if $B>n/2$. The success probability is at least $1/2$, so at most two draws are needed on average.

For a successful draw, select one endpoint of each monochromatic edge and let $D$ be the union of the selected vertices. Then $|D|\le B\le n/2$. Every monochromatic edge meets $D$, so the original colors give a proper graph colouring on the induced subgraph with vertex set $W=V\setminus D$. Since $|W|\ge n/2$, the coloring of all vertices is a semicoloring. This is a random alteration method; no additional colors for $D$ are required.

The number of available colors satisfies $2^r\le 2\max \{1,(4m/n{)}^{{\log }_{3}2}\}$. A simple graph has $m\le n(n-1)/2$, hence semicoloring by independent hyperplanes gives

A graph $G=(V,E)$ is bipartite when its set of vertices can be partitioned asso that every edge has one endpoint in $A$ and the other in $B$. Equivalently, $G$ has a proper graph colouring with at most two colours.

Vizing theorem states that every finite simple graph of maximum degree $\Delta$ haswhere ${\chi }^{\prime }(G)$ is its edge chromatic number. The lower bound follows because all edges incident with a vertex of degree $\Delta$ need different colours.

For the upper bound, induct on the number of edges. Delete an edge $xy$ and colour the remaining graph with the palette $\{1,\dots ,\Delta +1\}$. We use the Vizing fan lemma: in a partial proper edge colouring with one uncoloured edge $xy$, if the palette has one more colour than the maximum degree, a sequence of fan rotations and two-colour Kempe-chain interchanges makes some colour missing at both ends of the uncoloured edge.

Here is the fan argument. Build a maximal sequence $y_0=y,y_1,\dots ,y_k$ of distinct neighbours of $x$ such that, for $i\ge 1$, the colour on $x{y}_i$ is missing at an earlier fan vertex. Rotating an initial fan segment means moving each colour on $x{y}_i$ to the preceding edge where it is missing; this preserves properness and moves the uncoloured edge to the end of that segment. Choose a colour $\alpha$ missing at $x$ and a colour $\beta$ missing at $y_k$. On the maximal $\alpha$-$\beta$ alternating path from $y_k$, interchange $\alpha$ and $\beta$. If the path does not reach $x$, $\alpha$ is then missing at both $x$ and $y_k$, so rotate the fan and colour its final uncoloured edge $\alpha$. If it reaches $x$, its last edge at $x$ has colour $\beta$. Maximality of the fan forces the other endpoint of that edge to be a fan vertex; rotate up to that vertex first. This breaks the alternating path before $x$, reducing to the preceding case. This proves the fan lemma and extends the colouring to $xy$, completing the induction.

For $K_{n,n}$, label both vertex classes by $\mathbb{Z}/n\mathbb{Z}$ and colour edge $(i,j)$ by $i+j$. Each colour is a perfect matching, so this is an $n$-edge-colouring. Since $\Delta (K_{n,n})=n$, ${\chi }^{\prime }(K_{n,n})=n$. If $r=\max \{m,n\}$, embed $K_{m,n}$ into $K_{r,r}$ and restrict its $r$-edge-colouring. The degree lower bound then gives

Finally, subdividing one edge of $K_{n,n}$ produces $n^2+1$ edges on $2n+1$ vertices while keeping maximum degree $n$. In any proper edge colouring, each colour class is a matching of size at most $n$. An $n$-edge-colouring could therefore colour at most $n^2$ edges, a contradiction. Thus ${\chi }^{\prime }(G)>n$, while Vizing theorem gives ${\chi }^{\prime }(G)\le n+1$, so

The extremal number $\mathrm{ex}(n,H)$ is the maximum number of edges in an $n$-vertex graph containing no subgraph isomorphic to $H$.

Let $G$ be triangle-free with $e$ edges. For every edge $uv$, the neighbourhoods of $u$ and $v$ are disjoint apart from their endpoints, so
$d(u)+d(v)\le n$. Summing over edges and applying Cauchy-Schwarz inequality giveswhileThus $e\le n^2/4$, proving the required Mantel theorem bound.

Form the graph whose vertices are the points $x_i$, joining two when their Euclidean distance is one. Two distinct points have at most two common unit-distance neighbours, because two unit circles intersect in at most two points. The graph is therefore $K_{3,2}$-free. Part (c) bounds its unordered edges by $2n^{3/2}$, so the number of ordered unit-distance pairs is at most

For a finite graph $\Gamma$, its Right-angled Artin group isIts Salvetti complex $S_{\Gamma }$ is the one-vertex cube complex with an oriented loop labelled $v$ for each vertex of $\Gamma$, a square torus for every edge, and more generally one cubulated $k$-torus for every $k$-clique, attached compatibly along coordinate subtori. Thus ${\pi }_1(S_{\Gamma })\cong A_{\Gamma }$. The vertex link of a Salvetti complex is flag, so $S_{\Gamma }$ is a nonpositively curved cube complex.

The graph whose vertices are two-element subsets of a five-element set, with two vertices adjacent when the subsets are disjoint. It has ten vertices, degree three, zero common neighbours for adjacent pairs and one for nonadjacent pairs. Its adjacency matrix of a graph satisfies $A^2+A-2I=J$ and has eigenvalues $3,1,-2$ of multiplicities $1,5,4$.