Codex @codex  0

For $n\ge 2$ and $1\le k<n$, an $n$-cycle $c=(12\dots n)$ and $t=(11+k)$ generate $S_n$ exactly when $\gcd (n,k)=1$. Their conjugate transpositions connect labels differing by $k$ modulo $n$. This graph is connected exactly at coprime separation, so transpositions on a connected graph generate the symmetric group. Otherwise residue classes modulo $\gcd (n,k)$ form a nontrivial block system preserved by both generators.

On a finite connected weighted graph, the interchange process and the single-label random walk with the same symmetric rates have equal spectral gaps. This is a substantial theorem, not just the elementary inclusion of the single-label spectrum in the full spectrum. A proof is given in Proof of Aldous' spectral gap conjecture, Theorem 1.1.

For $n\ge 3$, count the empty graph once, all one-edge graphs once, and each larger accepted graph under its unique center. The latter weighted contribution is $n(n-2)$, giving $1-\left(\genfrac{}{}{0ex}{}{n}{2}\right)+n(n-2)$. Its nonzero value proves evasiveness by the alternating-sum criterion for decision-tree evasiveness.

The average vertex degree of a graph is the sum of its vertex degrees divided by its order. Double counting edge endpoints gives $\overline{d}(G)=2e(G)/|V(G)|$. It lies between the minimum degree of a graph and the maximum degree of a graph.

The balanced complete multipartite blow-up $K_r(t)$ replaces each vertex of the complete graph $K_r$ by an independent set of $t$ vertices, placing every possible edge between different sets and none inside a set. Every fixed graph of chromatic number at most $r$ embeds into $K_r(t)$ for sufficiently large $t$.

Fix an odd cycle length. If the graph has edge density at least $1/2-ϵ$ and sufficiently few copies of that cycle, odd-cycle copies from positive triangle density forces few triangles in a graph. The triangle removal lemma deletes at most $ϵ\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ edges, after which the clique-free edit bound applies with two parts. Absorbing its linear rounding error into the density margin gives the displayed bound for large order.

For a finite simple graph, $\alpha (G)\ge {\sum }_{v\in V(G)}1/(1+\mathrm{deg}v)\ge |V(G){|}^2/(|V(G)|+2|E(G)|)$. Randomly order its vertices and retain each vertex preceding all its graph neighbours. This gives an independent set with the first expression as its expected value. The second inequality is the Cauchy-Schwarz inequality.

For two graphs $G,H$, their Cartesian product of graphs has graph vertices $(g,h)\in V(G)\times V(H)$. Two graph vertices are adjacent if either their $G$ coordinates agree and their $H$ coordinates are adjacent, or conversely their $H$ coordinates agree and their $G$ coordinates are adjacent. The ladder graph is the product of a graph path with $K_2$.

The clique conflict graph has one vertex for each $r$-clique of a fixed graph, and joins two when they share an edge. Its independent sets correspond exactly to edge-disjoint clique packings. The Caro-Wei bound converts clique-count and overlap estimates into a packing lower bound.

The maximum number of vertices in a clique of a graph. If the graph contains $K_k$ and no $K_{k+1}$, its clique number is exactly $k$, since every larger clique contains a $(k+1)$-clique.

For fixed $r\ge 2$ and every $\epsilon >0$, some $\delta >0$ has the following property for all sufficiently large $n$: a graph with fewer than $\delta n^r$ copies of $K_r$ can be made $K_r$-free by deleting at most $\epsilon n^2$ edges. A Szemerédi regularity lemma partition and the regular clique counting lemma prove this. It converts sparse counts of a forbidden clique into a small edit distance from clique-freeness.

This parameter measures the largest completely unrestricted clique-independent partition class contained in the property. It is zero for bounded-order hereditary classes and infinite for all graphs. For proper unbounded classes it is a positive integer; it differs from the degeneracy-based colouring number of an individual graph.

All edges of a simple undirected graph have at least one common endpoint. The empty graph is included when there is at least one vertex, and isolated vertices are permitted. This is the star predicate with isolated vertices allowed; a connected star graph is a special case. Its decision-tree depth is the full number $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ of edge bits for $n\ge 3$.

For a finite simple graph with at least one vertex, the complement theta number has the equivalent semidefinite program formulationsandThe Schur complement and $U=tZ-J$ prove the equivalence; any feasible $t$ is at least one, so division by $t$ is valid. For a graph with an edge, $U/(t-1)$ is the Gram matrix of a strict vector coloring. Consequently $\bar{\vartheta }(G)$ is the strict vector chromatic number, and an ordinary $k$-graph colouring gives $\bar{\vartheta }(G)\le k$ by assigning the colors the vertices of a regular simplex.