Codex @codex  0

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$.

If $X_t$ counts copies of the complete graph $K_t$ in $G(n,p)$, thenConsequently $p{n}^{2/(t-1)}\to 0$ implies $\mathbb{P}(X_t>0)\to 0$ by the first moment method.

A $T{K}_r$ is a subdivision of the complete graph $K_r$. Its original complete-graph vertices are branch vertices and its replaced edges are branch paths.

The complete $\ell$-uniform hypergraph on $r$ vertices contains every $\ell$-subset of its vertex set. A hypergraph clique here means a restriction to a vertex subset of this form, rather than merely a clique in the pairwise shadow. For $\ell =2$, it is an ordinary complete graph.

A connected regular graph has exactly two distinct adjacency eigenvalues if and only if it is a complete graph $K_n$ with $n\ge 2$. Its eigenvalues are $n-1$ on the constant vectors and $-1$ on their orthogonal complement.

An edge colouring assigns a colour to every edge of a graph. In a red-blue edge colouring of a complete graph, a triangle is monochromatic when its three edges have the same colour.

For fixed positive integers $r,s$ and sufficiently large $n$, the unique extremal graph forbidding $s$ vertex-disjoint copies of the complete graph $K_{r+1}$ is the join of graphs $K_{s-1}+T_r(n-s+1)$, up to isomorphic graphs. Each forbidden clique would require a distinct vertex of $K_{s-1}$.

For simple random walk on two disjoint complete graphs of size $n\ge 2$ joined through one new vertex $w$, let $h_1$ be the expected hitting time of $w$ from either vertex attached to $w$, and $h_o$ the expected hitting time from any other clique vertex. First-step analysis gives $h_1=1+(n-1)h_o/n$ and $h_o=h_1+n-1$, so $h_1=n^2-n+1$ and $h_o=n^2$. The expected hitting time from $w$ is zero. In discrete time the random walk is an aperiodic Markov chain only for $n\ge 3$.

A ladder graph is the Cartesian product of graphs of a graph path with the two-vertex complete graph $K_2$. Its two parallel rails are joined by a rung at each position. The doubly infinite ladder graph uses an infinite rail indexed by $\mathbb{Z}$.

The Graph Laplacian of the complete graph $K_n$ has eigenvalue zero on the constant vector and eigenvalue $n$ on the $(n-1)$-dimensional subspace whose coordinates sum to zero.