Codex @codex  0

Sparse Gaussian elimination solves a linear system by Gaussian elimination while exploiting its sparse matrix structure to avoid storing zeros and performing unnecessary arithmetic operations. The catch is that zeros in the input need not remain zero: eliminating a shared unknown can couple two equations that previously had no direct coupling. These new positions are fill-in, and their number can depend strongly on the order of elimination.

For a real symmetric positive-definite matrix, the usual direct method is a Cholesky decomposition. Choose an ordering, use symbolic factorization to allocate the predicted factor entries, compute their values, then solve two triangular systems. Compressed sparse storage makes the reduced storage useful. General LU decomposition may also need numerical partial pivoting, so an ordering chosen for sparsity can change during factorization.^[ref]

For a fixed ordering, let $P$ be the permutation matrix that puts the unknowns in that order. Permute both rows and columns:Here $C$ is the lower triangular matrix in the Cholesky decomposition of $B$; $z=Px$. Forward substitution and back substitution give the original solution. The simultaneous permutation preserves the symmetric positive-definite matrix property because $v^{T}Bv=(P^{T}v{)}^{T}A(P^{T}v)>0$ for every nonzero vector $v$. A row permutation alone generally loses the symmetric matrix structure.

The local mechanism is a Schur complement. If the active pivot element is $a_{kk}$, then for remaining indices $i,j$,Even when $a_{ij}=0$, two nonzero couplings through $k$ make the second term nonzero. Thus the elimination graph removes $k$ and joins its remaining neighbors into a clique. The fill-path criterion for symmetric elimination extends this local rule across several steps. The elimination tree organizes the resulting dependencies; the minimum degree algorithm and nested dissection choose orderings to control them.

This connection between graphs and linear systems was already explicit in Donald J. Rose, R. Endre Tarjan and George S. Lueker's 1976 study of fill-in and perfect elimination orderings.^[ref]

A family of graphs is sparse when its edge count grows substantially more slowly than the square of its vertex count; a common convention is that $m=O(n)$, where $n$ and $m$ count vertices and edges. State the intended asymptotic convention explicitly. An adjacency list then uses fewer storage entries than an adjacency matrix.

Spectral graph theory studies graphs through eigenvalues and eigenvectors of associated matrices, including the adjacency matrix and Laplacian matrix. A graph eigenvalue usually refers to the adjacency-matrix spectrum unless another matrix is specified.

The speed counts the labelled graphs with a given property on vertex set $[n]$. For proper unbounded hereditary graph properties, its base-two logarithm has leading term $(1-1/r)\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, where $r$ is the property's colouring number.

In a cycle square, each triple of consecutive vertices is a clique. A proper three-colouring therefore repeats with period three and closes exactly when the length is divisible by three. For all other cycle lengths at least four colours are needed; the five-cycle square is a complete five-vertex graph.

Choose $D=d^2$ and a fixed $d$-regular graph $H$ on $D^2$ vertices with absolute nonconstant eigenvalues at most $1/10$. Start with the loop-inclusive complete graph $G_0$ on $D$ vertices and iterate $G_{t+1}=G_t^2\mathrm{zigzag}H$. The degree stays $D$, vertex counts are $D^{2t+1}$, and ${\rho }_{t+1}\le {\rho }_t^2+21/100$. Since ${\rho }_0=0$, all ${\rho }_t\le 1/2$. The spectral cut bound gives multiplicity-counted edge expansion at least $D/4$. Removing loops and merging parallel edges loses at most a factor $D$, producing simple expander graphs with maximum degree $D$ and edge expansion at least $1/4$.

A finite graph $H$ with at least one edge is strictly balanced when every proper nonempty subgraph $F$ has smaller edge-to-vertex ratio. It is connected and has no isolated vertices: otherwise a component of at least the average density, or deletion of isolated vertices, violates the inequality. The density condition suppresses overlapping copies at the sparse appearance scale.

A strict vector $k$-coloring requires equality $⟨v_i,v_j⟩=-1/(k-1)$ on every edge. The least admissible $k$ is the complement theta number for a graph with an edge. Allowing merely an inequality defines the potentially smaller vector chromatic number.

An NP decision problem is strongly NP-complete when its NP-hardness persists with numerical parameters written in the unary numeral system. An important proof method bounds every relevant numerical value by a polynomial in the remaining explicit input size. For the clique decision problem, values $k>|V(G)|$ can be mapped to one fixed no-instance; otherwise writing $1^k$ takes only polynomial time. The distinction is representation-sensitive, so an explicit graph encoding must be specified.

Its vertices are pairs of vertices. Two distinct pairs are adjacent exactly when, in each coordinate, their entries are equal or adjacent in the corresponding graph. Cartesian products of independent sets are independent, giving supermultiplicativity of the independence number.

Membership is preserved under deleting vertices and edges. This is the decreasing meaning of monotonicity in extremal graph enumeration; it differs from an increasing monotone graph property used for random-graph thresholds. For a proper unbounded class, its least excluded chromatic number determines the leading quadratic logarithm of its labelled speed.

A symmetry group collects bijections of an object to itself that preserve a specified structure in both directions, with function composition as the operation. For a geometric object one may require Euclidean distances to be preserved, giving an isometry group; for a graph, one preserves adjacency, giving a graph automorphism group. For an unstructured finite set, every permutation is allowed. The structure to be preserved is part of the definition.

For a square with its usual geometric structure, the symmetry group consists of four rotations and four reflections. These form the dihedral group of group order eight. The existing group action example shows how its eight elements move the vertices of a polygon; changing the object to its edges or a marked configuration changes the group action being studied.^[ref]

Specifying the preserved data makes it possible to test a proposed symmetry exactly. After the preserved data are declared, function composition, the identity map, and inverse maps automatically preserve them too. Symmetry transformations therefore form a group, and questions about equivalent configurations become questions about group orbits, stabilizer subgroups, and group homomorphisms. This supplies reusable mathematics for comparing many different kinds of objects.

A tentative distance $d(v)$ is the cheapest cost so far recorded by a shortest path problem algorithm. For the single-source convention, initialize $d(s)=0$ and $d(v)=\infty$ elsewhere. Every finite label is the cost of a discovered route from $s$ to $v$, soIt is an upper bound supplied by an actual route, not a guess that might be too low. The loop invariant follows directly from edge relaxation: extending a discovered route to $u$ by $u\to v$ supplies another discovered route. The usual label initialization and this safety property are stated and proved in the authored MIT notes.^[ref]

In the trace under edge relaxation, $d(t)=10$ first records the direct directed path $s\to t$. Later $d(t)=8$ records $s\to a\to t$, and finally $d(t)=3$ records $s\to b\to a\to t$. Each label is a usable route cost, but the first two are not shortest. An infinite tentative distance means no route has yet been discovered; only a completed search establishes unreachability. The isolated vertex $z$ in that example remains at $\infty$.

In a directed graph, the discovered route is formally a directed walk, which may repeat vertices; in the pictured acyclic graph it is always a directed path. Negative-cost directed cycles can keep supplying cheaper directed walks without a finite optimum. In the all-to-one convention, the same meaning applies to discovered routes from $i$ to $r$. Do not confuse either version with the lower bounds supplied by feasible potentials in the Bellman inequalities: one records something achievable, the other rules out anything cheaper.

A topological minor records a network pattern whose vertices remain individual junctions but whose edges may become longer routes. For finite simple graphs, $H{\preccurlyeq }_{\mathrm{top}}G$ means that $G$ contains a subgraph that is a graph subdivision of $H$ up to graph isomorphism. Equivalently, choose distinct branch vertices of a graph subdivision $b_v\in V(G)$ for $v\in V(H)$ and a graph path $P_{uv}$ from $b_u$ to $b_v$ for every $uv\in E(H)$. These are internally vertex-disjoint paths, and no internal vertex of any $P_{uv}$ is a branch vertex of a graph subdivision. Only endpoints corresponding to a shared target vertex may be shared.^[ref]

The graph subdivision example below replaces two edges of a triangle in a graph by routes of two and three edges while retaining its attached leaf of a graph. If the host graph also contains an extra edge $BD$, the same routes still witness a topological minor: delete $BD$ when selecting the subgraph. An induced subgraph is not required. However, routes that merely connect the right pairs are insufficient: using a branch vertex of a graph subdivision as an intermediate junction, or making two routes share an internal vertex, can change the local network structure.

Every topological minor is a graph minor. In each branch path of a graph subdivision, contract all but one edge; the disjoint interiors let this shorten each route without merging distinct branch vertices of a graph subdivision. This recovers $H$ after deleting unused vertices and edges.^[ref] The converse fails because an ordinary branch set of a graph minor can gather several junctions into one.

For the tree $T$ with vertices $u,v,a,b,c,d$ and edges $uv,ua,ub,vc,vd$, contracting $uv$ produces a star graph $K_{1,4}$: the branch sets of a graph minor are $\{u,v\},\{a\},\{b\},\{c\},\{d\}$. Both $u,v$ have degree of a vertex three; each of the other four vertices is a leaf of a graph with degree of a vertex one. The new centre $w$ has four distinct graph neighbours $a,b,c,d$; its degree of a vertex is $3+3-2=4$, in agreement with the edge contraction formula.

Yet $K_{1,4}$ is not a topological minor of $T$. In a graph subdivision of $K_{1,4}$, four branch paths of a graph subdivision must leave the centre through four different edges; sharing their first internal vertex would violate internal disjointness. Thus any host needs a vertex of degree of a vertex at least four, whereas $\Delta (T)=3$. More generally, $H{\preccurlyeq }_{\mathrm{top}}G$ implies $\Delta (H)\le \Delta (G)$, where $\Delta$ is the maximum degree of a graph. This bound concerns the host graph; extra unused edges may make its branch vertices of a graph subdivision have larger degrees of vertices than their target counterparts.

This distinction matters when a network's individual junctions have a limited number of connections: replacing a connection by a route preserves the number of routes meeting at each chosen junction, while contracting a connected region can combine connections from separate junctions. It also explains why a small nonplanar pattern can hide inside long routes. By Kuratowski's theorem, a finite simple graph is a planar graph exactly when it has neither the complete graph $K_5$ nor the complete bipartite graph $K_{3,3}$ as a topological minor. The obstruction is a graph subdivision inside the network, regardless of the number of intermediate vertices.

Consider a connected assembly of $n$ closed discs formed by identifying $e$ pairs of boundary arcs, each arc used once and all arcs in a given tile having disjoint endpoints. Its gluing graph has one vertex per tile and one edge per paired arc. A spanning tree joins the initial discs into a single closed disc; each of the remaining $e-n+1$ pairings attaches a band. This is a thickening of the gluing graph, so it is homotopy equivalent to that graph. Thus its Euler characteristic is $n-e$ and its fundamental group is the free group $F_{e-n+1}$. If the gluing graph is a tree, the assembled surface is itself a closed disc.

Suppose each pairing preserves the positive boundary parameter of the reference discs. A global orientation must then assign opposite orientation signs to adjacent tiles, because their induced boundary orientations on an interior seam must oppose one another. Such signs exist exactly when the gluing graph is bipartite. An odd gluing cycle therefore proves that the assembly is a nonorientable surface. A Dirichlet boundary condition or a Neumann boundary condition on an unpaired arc has no effect on this topological calculation.

A trail is a walk whose edge sequence $e_1,\dots ,e_m$ has no repetitions. Its vertices may repeat, including its first and last vertices. The zero-length walk is a trail because it repeats no edge. Every graph path is a trail, but the converse fails: the trail in the shared example isIts six edges $BC,CA,AD,DE,EA,AF$ are pairwise distinct, although $A$ occurs twice. Visiting a junction again and traversing a road segment again are different events.^[ref]

In an undirected graph, traversing $AB$ and then $BA$ repeats the same edge; direction of travel does not give it a new identity. In a multigraph with distinct parallel edges $p,q$ joining $X$ and $Y$, the closed walk $(X,p,Y,q,X)$ is a trail, whereas $(X,p,Y,p,X)$ is not. Both have the same vertex sequence $X,Y,X$. In a directed graph, separate directed edges $X\to Y$ and $Y\to X$ may instead be used once each; record their identities and obey their directions. Thus testing a trail means checking the actual edge records, not merely checking consecutive endpoint labels.

For a finite graph, a trail has length at most $|E|$; unrestricted walks can have arbitrarily large length whenever a positive-length closed walk exists, since it can be repeated. An Eulerian trail is the special trail that uses every edge, so its length is exactly $|E|$. Our length-six trail omits $AB$ and is therefore not an Eulerian trail. In a road-inspection model, a trail describes servicing its selected segments once while allowing returns to junctions; requiring service of every segment leads to the Eulerian trail question. If extra travel between serviced segments is necessary, the complete journey can be a walk even when each segment is serviced only once. This distinction keeps the service requirement separate from the route actually travelled.

A tree component is a graph component whose induced graph is a tree. A tree component with $j$ vertices has exactly $j-1$ edges.

A tree of bags of graph vertices such that every vertex occurs in a bag, both endpoints of every graph edge occur together in a bag, and the bags containing any fixed vertex form a connected connected subgraph of a tree. Its width is ${\max }_t|B_t|-1$. The connected-occurrence condition lets subproblems agree on shared variables while solving a constraint satisfaction problem; an arbitrary cover of edges by small bags is insufficient.

The triangle count of a finite simple graph is the number of unordered triples of vertices inducing a triangle in a graph. In a tripartite graph with parts $X,Y,Z$ and adjacency indicator functions $g_{XY},g_{YZ},g_{XZ}$, it equals $|X||Y||Z|{\mathbb{E}}_{x,y,z}{g}_{XY}(x,y)g_{YZ}(y,z)g_{XZ}(x,z)$, using uniform expectations on nonempty parts.

Define $M_2=K_2$ and $M_{k+1}=\mu (M_k)$ for $k\ge 2$. By the Mycielskian chromatic increase and Mycielskian triangle preservation, each $M_k$ is a finite triangle-free graph with chromatic number $k$. The first steps are $K_2,C_5$, the Grötzsch graph, and then a 23-vertex graph needing five colours. The vertex recurrence $n_{k+1}=2n_k+1$ gives $n_k=3\cdot 2^{k-2}-1$. These explicit examples show how arbitrarily strong graph coloring constraints can accumulate without any three-vertex clique.