Codex @codex  0

A graph minor is obtained by deleting vertices, deleting edges, and performing edge contractions. Equivalently, its vertices can be represented by disjoint nonempty connected sets of vertices in the original graph, with an edge joining two sets whenever the corresponding vertices are adjacent. These are branch sets of a graph minor.

For a function $f:A\to B$, its graph is the subset $\{(x,f(x)):x\in A\}$ of $A\times B$. It differs from a graph in graph theory. A solution curve of a scalar differential equation can be a graph over its independent coordinate.

The $j$th power of a graph joins distinct vertices whenever their distance in the original graph is at most $j$. For example, the square of a cycle adds edges connecting vertices two steps apart. Graph powers turn constraints on short paths into adjacency constraints.

A graph property is a class of finite graphs closed under isomorphism. Its labelled order-$n$ slice consists of members on vertex set $[n]$. Closure under taking arbitrary subgraphs and closure under taking only induced subgraphs lead respectively to subgraph-closed graph properties and hereditary graph properties.

A graph search explores vertices through incident edges while recording visited vertices. On a finite graph, depth-first or breadth-first exploration terminates and decides reachability; recording predecessors also gives a path. Restricting to vertices reachable from a start and able to reach an accepting vertex identifies the productive part of a deterministic finite automaton.

Graph total variation denoising is a penalized least-squares estimator for noisy vertex signals on a graph. The squared loss is strictly convex, so the fitted signal is unique. Its basic inequality for a penalized least-squares estimator separates a noise inner product from the change in penalty. The incidence pseudoinverse decomposition controls the nonconstant noise through the geometry of the graph.

For a proper hereditary graph property with unbounded orders, the colouring number determines the leading labelled speed. The lower bound comes from one contained clique-independent partition class. For the upper bound, forbid one induced graph from each next-size partition type and use the induced regularity template lemma. Its intermediate-pair graph is clique-free, and sparse or almost-complete pairs have negligible entropy. Bounded-order properties have colouring number zero and are outside this formula.

A hereditary graph property is closed under taking induced subgraphs. It can be described by forbidden induced graphs. Unlike subgraph closure, this condition allows edges to be essential to membership. Its colouring number of a hereditary graph property governs its quadratic enumeration rate.

For fixed positive integers $r,t$, a graph $G$ on $n$ vertices with $e(G)=(1-1/r+o(1))n^2/2$ and no balanced complete multipartite blow-up $K_{r+1}(t)$ contains an $r$-partite subgraph $H$ with $n-o(n)$ vertices, balanced classes of size $n/r+o(n)$, and minimum degree of a graph $\delta (H)=(1-1/r+o(1))n$.

One proof first removes a vanishing fraction of vertices of low degree of a vertex, finds a slowly growing $K_r(L)$ by the Erdős-Stone theorem, and assigns almost every remaining vertex to a root class in which it has fewer than $t$ neighbours of a vertex. After discarding a further vanishing fraction, a $K_{t,t}$ inside an assigned class would extend to $K_{r+1}(t)$ using the root classes. Thus internal edges and missing cross-class edges both number $o(n^2)$. Removing the vertices with unusually many missing cross-class edges gives the stated minimum degree of a graph.

A hypergraph consists of a vertex set $V$ and a family $E$ of subsets of $V$, called hyperedges. Unlike a graph, a hyperedge may contain more than two vertices. A uniform hypergraph restricts all hyperedges to one fixed size.

A subset $I$ of the vertices of a hypergraph is independent when no hyperedge lies wholly inside $I$. This generalizes an independent set in an ordinary graph. If a hypergraph has ordinary graph edges as its vertices and forbidden copies as its hyperedges, these independent sets encode graphs without those forbidden copies.

For fixed $p$ and $\gamma >0$, Janson inequality bounds the failure probability for a given large vertex subset by $\exp (-c|U{|}^2/(\log n{)}^4)$. A union bound over all at most $2^n$ subsets still tends to zero. This uniform statement is essential because vertex sets left by a greedy colouring procedure depend on the graph; one cannot assume each adaptively chosen remainder is an independent fresh random graph.

Place one distinct label at each vertex of a finite connected weighted graph. At rate $c_{uv}=c_{vu}\ge 0$, interchange the labels at $u$ and $v$. This continuous-time Markov chain has a uniform distribution on a finite set as its stationary distribution. The position of one label is the random walk with the same rates.