A matching in a hypergraph is a family of pairwise vertex-disjoint hypergraph edges. A perfect matching in a hypergraph covers every vertex; an almost-perfect matching in a hypergraph leaves a small proportion uncovered. In a proper edge colouring, each colour class is a matching in a hypergraph.

A subhypergraph restricts the vertex set of a hypergraph and retains some of its edges contained in that vertex set. Retaining every such edge gives an induced subhypergraph.

Two sign-vector vertices of a centered hypercube differing in $h$ coordinates have dot product $n-2h$. Thus their body diagonals can be orthogonal only in even dimension. A collection of mutually orthogonal nonzero diagonals has at most $n$ members; achieving $n$ is equivalent to the existence of a Hadamard matrix of order $n$. For unoriented lines the angle is determined by $|n-2h|/n$, while oriented vertex vectors retain the sign of their dot product.

An ideal hyperbolic triangle has all three vertices on the boundary at infinity of the hyperbolic plane. All its angles are zero and its hyperbolic area in curvature $-1$ is $\pi$, by hyperbolic triangle area.

For curvature minus one, no hyperbolic triangle contains an open hyperbolic disc of radius greater than $\frac{1}{2}\log 3$. Move the disc centre to zero in the Poincare disc model and enclose the triangle in an ideal triangle with the same radial vertex directions. One gap between ideal directions is at least $2\pi /3$. Its opposite geodesic is at distance at most $2\mathrm{artanh}(2-\sqrt{3})=\frac{1}{2}\log 3$ from zero. The symmetric ideal hyperbolic triangle attains the bound as its inradius.

The unit ball in Euclidean space with the displayed Riemannian metric models hyperbolic space of curvature minus one. Its ideal boundary is the unit sphere, and its geodesics are diameters or circle arcs orthogonal to that sphere. The metric is invariant under the conformal ball automorphisms.

An isometry of hyperbolic space with positive attained translation length has an invariant complete geodesic joining its two ideal fixed points. This is its axis. It translates along the axis by its translation length; in three dimensions it may additionally rotate around it. In upper half-space, $(z,t)\mapsto (kz,|k|t)$ with $|k|\ne 1$ has the vertical axis through zero and length $|\log |k||$. Every connecting path has length at least the change in $\log t$, and a vertical segment attains the bound.

For a nonempty finite set $\{p_1,\dots ,p_m\}$ in finite-dimensional hyperbolic space, the continuous function $R(x)={\max }_{j}d(x,p_j)$ attains its minimum. Indeed, a bounded candidate radius confines all possible improving centers to a closed bounded ball about $p_1$. Such a ball is compact in the Poincare ball model, since its points remain away from the ideal boundary. Minimizing $R$ on it supplies a closed ball of smallest enclosing radius. More generally this argument works for any nonempty bounded set in a proper metric space when the supremum-distance function is finite.

In the positive Hermitian determinant-one model of three-dimensional hyperbolic space, the base point is $I$ and a matrix $g\in SL(2,\mathbb{C})$ sends it to $g{g}^{\ast }$. The distance obeys $2\cosh d(I,g{g}^{\ast })=\mathrm{tr}(g{g}^{\ast })$. Bounded displacement therefore bounds every matrix entry, and the determinant-one condition gives a closed bounded subset of a finite-dimensional real vector space. Passing to $PSL(2,\mathbb{C})$ preserves compactness. Conjugating moves any chosen base point to $I$. A discrete subgroup meets each such compact set in finitely many elements, proving escape of distinct elements and proper discontinuity, including finite stabilizers.

An ideal hyperbolic quadrilateral is the region bounded by four hyperbolic geodesics whose four consecutive endpoints are distinct points on the ideal boundary. The ideal vertices lie outside the hyperbolic plane. In the hyperbolic disk, the four vertices $1,i,-1,-i$ give a regular example: its sides are the interior arcs of the circles of radius one centered at $\pm 1\pm i$. Although the sides have infinite length, the quadrilateral has finite hyperbolic area $2\pi$ in curvature $-1$.

A geodesic polygon in the hyperbolic plane is bounded by finitely many geodesic segments. For curvature $-1$, its area is its angle defect, as given by hyperbolic polygon area. Pairing equally long edges produces hyperbolic surfaces, with smoothness at glued vertices determined by their total angles.

On the unit disc, the pseudohyperbolic distance isIt is invariant under disc Möbius transformations. For the curvature-minus-one hyperbolic metric with length element $2|dz|/(1-|z{|}^2)$, $\delta (z,w)=\tanh (\rho (z,w)/2)$ and $e^{-\rho (z,w)}=(1-\delta )/(1+\delta )$. The Schwarz-Pick theorem says that holomorphic functions from the disc into itself contract this distance. A Blaschke factor has modulus $\delta (z,a)$, so the distance also controls the size of a product with prescribed zeros.

The universal covering map $\tau \mapsto e^{i\tau }$ from the complex upper half-plane to the punctured unit disc pulls back the metric $|dz|/(|z|\log (1/|z|))$ to $|d\tau |/\mathrm{Im}\tau$. This is its complete curvature-minus-one hyperbolic metric, which is different from restricting the ordinary disk metric to the punctured disk.

// Destination: analysis.bigb

A connected Riemann surface whose universal cover is the unit disc inherits the complete curvature-minus-one metric displayed on its cover. Möbius transformations preserving the disc are isometries, so deck transformations preserve the metric and it descends to the surface. This uniformization notion must be distinguished from the potential-theoretic existence of a Green function. Holomorphic maps between such surfaces contract their metric by lifting to Schwarz-Pick theorem on the covers.

Vertical pressure gradient balances gravitational force per unit volume. Subtracting the resting hydrostatic state and using kinematic pressure gives $p_z^{\prime }=b^{\prime }$ for a Boussinesq approximation buoyancy anomaly. The approximation neglects vertical acceleration; this diagnostic relation is what couples buoyancy perturbation to the vertical pressure profile.

A localized vorticity distribution with nonzero hydrodynamic impulse induces $\mathbf{u}\sim [3\mathbf{n}(\mathbf{I}\cdot \mathbf{n})-\mathbf{I}]/(4\pi r^3)$. This curl-free exterior velocity can remain long-ranged even when the vorticity is localized. In a random ensemble it produces dipolar longitudinal and transverse correlation tails.

A Huffman code is the prefix code returned by Huffman coding; the algorithm chooses a code tree, while the code specifies the actual symbol-to-codeword assignment. For the probability distribution $(0.4,0.3,0.2,0.1)$ in symbol order $A,B,C,D$, the illustrated binary tree givesThe codeword lengths are $1,2,3,3$. This is a prefix code because no complete codeword is an initial segment of another complete codeword. Thus a decoder can start at the root of a tree, follow one edge per bit, emit a symbol on reaching its leaf, then restart at the root of a tree. In particular, 011010111 splits as 0 | 110 | 10 | 111 and decodes to $A,C,B,D$. No separators are transmitted: the leaf tells the decoder where a codeword ends.

The expected codeword length isbits per source symbol. Four symbols would require $2$ bits each if all codewords had the same length, so this Huffman code saves $0.1$ bit per symbol on average, or $5\%$ of that fixed-length payload. A particular message can grow: $A,C,B,D$ uses nine bits here instead of eight. These lengths count the encoded symbols only; transmitting a code description or message framing can add further cost.

The Kraft inequality is saturated by this Huffman code:Its Shannon entropy isbits per symbol, slightly below the expected codeword length $1.9$. The entropy lower bound for prefix codes applies to every binary prefix code for this probability distribution. It need not be attainable with integer codeword lengths for individual symbols; Huffman coding reaches the best mean within that class. ^[ref]

A Huffman code need not be unique. In the first example, the tied $B$ and $CD$ weights can exchange their $0/1$ edge labels, changing codewords but preserving their codeword lengths. Ties can also change the lengths themselves. For a second probability distribution $(0.4,0.2,0.2,0.2)$, first merge $C,D$ to weight $0.4$. The next merge can join $B$ with either $A$ or the $CD$ subtree, since both have weight $0.4$. Joining $B$ with $A$ permits $A\mapsto 00,B\mapsto 01,C\mapsto 10,D\mapsto 11$, with all lengths $2$. Joining $B$ with the $CD$ subtree permits $A\mapsto 0,B\mapsto 10,C\mapsto 110,D\mapsto 111$, with lengths $1,2,3,3$. Both are optimal prefix codes with expected codeword length $2$: for the latter, $0.4\cdot 1+0.2\cdot 2+0.2\cdot 3+0.2\cdot 3=2$. Tie choices can change the code tree without changing the minimum mean.

// Target: algebra.bigb

Apply the preceding Householder reflection to the columns ofThe first column becomes $(-5,0{)}^T$ and the second becomes $(-11/5,2/5{)}^T$:Thus an orthogonal matrix multiplying an upper triangular matrix reconstructs $A$. The zero below the diagonal came from a geometric operation that preserves Euclidean norms and inner products.

Our positive-diagonal convention for QR decomposition is obtained by a sign adjustment. With $D=\mathrm{diag}(-1,1)$, putThen $Q^{T}Q=I$ and $\boxed{A=Q{R}_{+}}$. The intermediate sign chooses an orientation for a basis vector; the adjustment makes the diagonal positive.

For a larger matrix, the next Householder reflection acts only on the lower rows of the remaining columns, retaining the zeros already created. Store its defining vector and apply $z\mapsto z-2u(u^{T}z)$ instead of forming a dense reflection matrix. This links a simple mirror operation to efficient QR decomposition, including least-squares solutions.

For a nonzero real vector $x\in {\mathbb{R}}^n$, choose $\alpha$ with $|\alpha |=\Vert x{\Vert }_2$ and put $v=x-\alpha e_1$. When $v\ne 0$, the Householder reflectionsatisfies $Hx=\alpha e_1$: every component except the first becomes zero. Here $e_1$ is the first Cartesian basis vector. The calculation is short:If $v=0$, the vector is already at the selected target, so the identity matrix suffices.

In floating-point arithmetic, a customary choice isThen $|v_1|=|x_1|+\Vert x{\Vert }_2$, avoiding subtraction of nearly equal positive quantities in the first component. Either sign can be valid in exact arithmetic; the numerical choice protects the construction from catastrophic cancellation. ^[ref]

For $x=(3,4{)}^T$, this choice gives $\alpha =-5$ and $v=(8,4{)}^T$. Dividing $v$ by its Euclidean norm gives $u=(2,1{)}^T/\sqrt{5}$, exactly the normal in the geometric example.

For a continuous interval map $F$ with a three-cycle $a<b<c$, after reflecting the coordinate if needed its ordering is $F(a)=b$, $F(b)=c$, $F(c)=a$. Then $F^2(a)=c$, $F^2(b)=a$. Also the intermediate value theorem gives $d\in (b,c)$ with $F(d)=b$, hence $F^2(d)=c$. Each of $[a,b]$ and $[b,d]$ therefore maps across $[a,c]$ under $F^2$. Choose first-passage subintervals between endpoint levels to avoid overshoots; their interiors are disjoint and both map exactly onto $(a,c)$. This is a horseshoe for an interval map, and establishes Glendinning chaos.