Codex @codex  0

For $C_2\ast \mathbb{Z}\to S_3$ taking the two generators to a transposition and a $3$-cycle, the kernel's six-sheeted regular covering space consists of three spheres and two circles. Each sphere has two marked points, and each circle meets one point on each sphere. It retracts onto a rank-four graph by replacing each sphere by a meridian arc, but admits no deformation retraction onto any graph because its degree-two homology is ${\mathbb{Z}}^3$.

For simple random walk on a finite connected loopless unweighted graph, start at $a\ne z$ and stop on first hitting $z$. Ifthen $v_{az}(z)=0$ and $L{v}_{az}={\delta }_a-{\delta }_z$ for the Graph Laplacian $L$. The incoming-visit balance equation is $g_{az}(u)=1_{\{u=a\}}+{\sum }_{w\sim u}{g}_{az}(w)/\mathrm{deg}(w)$ for $u\ne z$; at $z$ the Laplacian value is $-1$ because all its coordinates sum to zero. Thus $v_{az}$ is the voltage for unit current from $a$ to $z$, and $v_{az}(a)=R_{\mathrm{eff}}(a,z)$. In particular, the expected number of directed transitions $u\to w$ before $T_z$ is $v_{az}(u)$.

The Kneser graph has as vertices the $k$-element subsets of $[n]$, with an edge between two exactly when they are disjoint. A graph colouring of this graph partitions the $k$-sets into intersecting families.

A Lévy family of graphs consists of finite connected graphs with their uniform probability measures and graph distances divided by their diameters, whose concentration of measure functions vanish at every fixed positive normalized radius. Equivalently, every family occupying at least half the vertices has a radius-$\lfloor \epsilon D_n\rfloor$ neighbourhood occupying a proportion tending to one, uniformly over such families. Harper theorem and binomial distribution tail bounds prove this for the hypercube graphs.

An edge density exceeding the Turan theorem threshold for $K_{r+1}$ by a fixed positive amount forces a balanced $K_{r+1}(t)$ subgraph with logarithmic part size. Combine clique supersaturation by sampling with the dense clique family blow-up lemma. Dense binomial random graphs show that the logarithmic order is optimal for a uniform density guarantee.

The Lovász number of a finite simple graph is the semidefinite program valuewhere $J$ is the all-ones matrix. Its value on the complement graph gives a lower bound for the chromatic number.

If a fixed graph $F$ has chromatic number $r+1$, every extremal $F$-free graph $G$ on $n$ vertices has minimum degree of a graph $(1-1/r+o(1))n$. Use a high-minimum-degree multipartite stability subgraph $H$: replacing any vertex by one adjacent to all but one class of $H$ preserves $F$-freeness. Any supposed new copy of $F$ can replace the new vertex by an unused common neighbour in the omitted class. Extremality therefore gives the lower bound on every degree of a vertex; the Erdős-Stone theorem gives the upper bound on the average degree of a vertex.

A neighbour of a vertex $v$ in a graph is a vertex joined to $v$ by an edge. These vertices form the graph neighbourhood $N(v)$.

A network meta-analysis jointly compares several treatments using a graph of direct randomized controlled trials and indirect treatment comparisons. If effects are measured relative to a reference treatment, consistency means ${\delta }_{ij}={\delta }_{i0}-{\delta }_{j0}$. A connected graph identifies all relative effects under that model. Transitivity in network meta-analysis is the substantive comparability assumption supporting these relations; inconsistency can be assessed when the network has loops.

For any fixed odd length $\ell \ge 3$, positive triangle in a graph density forces positive density of $\ell$-cycles. A Szemerédi regularity lemma partition retains a triangle in a graph of regular dense pairs after the sparse and exceptional pairs are removed. Count embeddings of a proper three-colouring of $C_{\ell }$ into those three clusters. The constants depend on $\beta$ and $\ell$, not on graph order.

A choice of direction for each edge of an undirected graph, producing a directed graph.

An oriented incidence matrix records an arbitrarily chosen orientation of each edge of a graph. Use one row per edge, with $+1$ and $-1$ at its endpoints and zeros elsewhere; the transpose convention is also common. The product $D\theta$ records endpoint differences. For a connected graph, $\ker D=\mathrm{span}\{1\}$, since zero difference propagates along every graph path.

A finite undirected graph can be oriented with outdegree at least an integer $k\ge 0$ at every vertex if and only if every vertex subset $U$ is incident to at least $k|U|$ distinct edges. The max-flow min-cut theorem and integral max-flow theorem prove sufficiency by assigning distinct edges to vertices through an incidence flow network; each assigned edge is oriented away from that vertex. Necessity follows by counting outgoing edges from $U$.