This decision problem asks whether a finite undirected graph has a graph colouring with three colours. It is NP-complete: a colouring certifies membership in NP, while 3-SAT reduces using Boolean-pair colouring gadgets and three-colour clause gadgets.

A graph is $r$-partite when its vertices can be partitioned into $r$ classes, each an independent set. Edges may be missing between different classes. If all possible edges between different classes occur, it is a complete multipartite graph.

A blow-up replaces each vertex of a graph by an independent set, and each original edge by all edges between the corresponding two sets. Replacing every vertex of $K_r$ by $t$ vertices gives the balanced complete multipartite blow-up $K_r(t)$.

The vertex set is the underlying set $V$ of a graph or hypergraph. In a hypergraph, its hyperedges are subsets of this set; in a simple graph, edges are two-element subsets.

The cubic lattice in dimension $d$ has graph vertex set ${\mathbb{Z}}^d$ and an edge between $x,y$ exactly when ${\sum }_i|x_i-y_i|=1$. For $d=2$ it is the square lattice. Every graph vertex has $2d$ graph neighbours, so it is a locally finite graph.

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

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

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 graph cut consists of the edges joining a vertex subset to its complement. In a two-group stochastic block model, crossing and within-group edges have different Bernoulli distributions. The Kullback-Leibler divergence between two such models is the sum of the changed-edge divergences, with their order determined by which partition regards the edge as crossing.

If $f$ is bounded along a downward gradient flow, the total time spent where $\Vert {\nabla }_{g}f\Vert \ge \epsilon$ is at most $(\sup f-\inf f)/{\epsilon }^2$. The gradient-flow dissipation identity proves this by integrating the indicator of that region. It bounds all visits together, without requiring the visited region to be connected.

For $V=m^2{\varphi }^2/2+\lambda ({\varphi }^2{)}^2/4$, $m^2<0$, the vacuum manifold is a sphere of radius $v=\sqrt{-m^2/\lambda }$. At a chosen vacuum the Hessian matrix is $2\lambda v^{2}n{n}^T$, where $n$ is its unit direction. The radial scalar has mass squared $2\lambda v^2$; the $n-1$ angular modes are physical Goldstone bosons when the symmetry is global.

For the two-component case, write $\mathbf{\varphi }=(v+\rho )(\cos \theta ,\sin \theta )$. The kinetic term becomes $\frac{1}{2}({\partial }_{\mu }\rho {)}^2+\frac{1}{2}(v+\rho {)}^2({\partial }_{\mu }\theta {)}^2$. At quadratic order the canonically normalized angular field is $\pi =v\theta$, with no mass term. Its Euler-Lagrange equation is the wave equation, so ${\omega }^2=|\mathbf{k}{|}^2$ in units where the propagation speed is one. The radial field instead obeys ${\omega }^2=|\mathbf{k}{|}^2+2\lambda v^2$. Thus a common rotation costs no energy, whereas a slowly varying rotation propagates as a collective wave. With the selecting source of continuous vacuum selection by an external source, use $\pi =w\theta$ and obtain ${\omega }^2=|\mathbf{k}{|}^2+h/w$. This elementary dispersion relation separates a Goldstone boson, a pseudo-Goldstone boson and a massive radial excitation within one example.

Stationarity of a canonical global F-term scalar potential gives ${\partial }_{i}V={\sum }_j{W}_{ij}\overline{W_j}=0$. If some $F_j=-\overline{W_j}$ is nonzero, this vector is in the kernel of the chiral-superfield fermion mass matrix. It supplies the massless goldstino direction. If every $F_j$ vanishes, this argument gives no broken-symmetry mode.

Gravitational initial data on a spatial manifold consist of a Riemannian metric $h$ and an extrinsic curvature $K$ satisfying the Hamiltonian constraint and momentum constraint. Matter theories require their own data and constraints as well. The data determine a maximal Cauchy development.

For a single-phase ideal gas mixture with molar amounts $N_i$, common temperature $T$, and pressure $P$, extensivity and ideal mixing giveHere $N={\sum }_i{N}_i$, $x_i$ is the mole fraction, $\mathcal{R}$ is the molar gas constant, and $P^{\circ }$ is the standard pressure. Integrating $\partial {\mu }_i/\partial P=\mathcal{R}T/P$ and including the ideal mixing entropy proves ${\mu }_i={\mu }_i^{\circ }+\mathcal{R}T\log (x_{i}P/P^{\circ })$. Reactions can change $N$, so fractions alone do not set the extensive Gibbs free energy. Its composition Hessian is $\mathcal{R}T({\delta }_{ij}/N_i-1/N)$; it is positive semidefinite by the weighted Cauchy-Schwarz inequality.

A row Gershgorin disc of a square matrix $A=(a_{ij})$ is the closed disk in the complex plane with centre $a_{ii}$ and radius $r_i={\sum }_{j\ne i}|a_{ij}|$. A zero radius gives a single point. The Gershgorin disc theorem places every eigenvalue in the union of these disks. For a Hermitian matrix, the real intervals cut out by the Gershgorin discs bound the eigenvalues, including energy levels when the matrix represents a Hamiltonian operator.

Applying the Gershgorin circle theorem to the transpose $A^T$ gives column Gershgorin discs with the same centres and radii $c_i={\sum }_{j\ne i}|a_{ji}|$. Since $A$ and $A^T$ have the same characteristic polynomial, every eigenvalue lies in the intersection of the row-disc union and the column-disc union. This is an intersection of two unions; one cannot generally replace each row radius by $\min (r_i,c_i)$. An isolated row Gershgorin disc contains exactly one eigenvalue by Gershgorin eigenvalue counting.^[ref]

Consider a layer governed by the linear shallow water equations of mean depth $H$ on an f-plane with nonzero constant Coriolis parameter $f$. Initially the surface is flat, the cross-strip velocity is zero, and the along-strip velocity is $u_0(y)=U{1}_{|y|<a}$. The two edges are opposite vortex sheets. Let $c=\sqrt{gH}$ and use the positive Rossby deformation radius $L_D=c/|f|$.

The conserved linearized shallow-water potential-vorticity anomaly is $q=v_x-u_y-f\eta /H$. Initially it isThe bounded final geostrophic balance has $u_f=-g{\eta }_f^{\prime }/f$ and henceThe decaying Green function of this one-dimensional operator is $-L_D{e}^{-|y|/L_D}/2$. Its convolution with the two sheets givesThe height is continuous and odd; differentiating gives the velocity jumps required by the two vortex sheets. Reversing $f$ reverses this height profile while leaving its positive decay length unchanged. The formula with $c/f$ as a decay length therefore requires the explicit restriction $f>0$.

Outgoing inertia-gravity waves carry the initial energy not retained in this balanced component. The geostrophic adjustment is a local late-time description in an open domain: a finite reflecting basin can retain oscillations.

With constant density divided out, a decaying or periodic geostrophic balance on an f-plane haswhere $q=\zeta -f\eta /H$ is the signed linearized shallow-water potential-vorticity anomaly. The stationary height equation and integration by parts prove the identity. Replacing $q$ by $|q|$ destroys it: an odd height paired with symmetric opposite-sign sheets would then misleadingly give zero.

Occupied area or volume divided by the corresponding total area or volume of a geometric packing. For a periodic packing, it is the total object area or volume within a repeat cell divided by the cell measure. It is distinct from the number fraction of objects of a given size.

Arrangement of circles in a plane without interior overlap. The covered area fraction is its packing fraction. Equal-radius square packing has fraction $\pi /4$.

Arrangement of spheres without interior overlap. The occupied volume fraction is its packing fraction; it depends on the spatial arrangement and on the radii.