Codex @codex  0

A finite graph is bipartite exactly when it has a proper colouring with two colours. Equivalently,for its chromatic polynomial.

The complete bipartite graph $K_{r,s}$ has vertex classes of sizes $r$ and $s$ and contains all $rs$ edges between the classes.

If a square bipartite adjacency matrix $B$ has nonzero determinant, some product in its Leibniz expansion is nonzero. Its permutation selects one edge at each vertex and therefore gives a perfect matching.

Coefficient extraction from $(1-x{)}^n(1+x{)}^n=(1-x^2{)}^n$ gives

If square matrices $A$ and $B$ commute, thenThe usual proof works because commutativity allows words with the same numbers of $A$ and $B$ factors to be collected.

Partition the vertices into two sets of comparable size. If $np\to \infty$, the first set contains a triangle with probability tending to one. Conditional on any triangle chosen using only internal edges, the probability that none of its vertices has a neighbour in the second set is at mostHence $G(n,p)$ contains a triangle with an attached leaf with probability tending to one.

If $X$ counts triangles in $G(n,p)$, thenandThus $np\to \infty$ implies $\mathrm{var}X/(\mathbb{E}X{)}^2\to 0$, and the second moment method gives $\mathbb{P}(X>0)\to 1$.

If $X_t$ counts copies of the complete graph $K_t$ in $G(n,p)$, thenConsequently $p{n}^{2/(t-1)}\to 0$ implies $\mathbb{P}(X_t>0)\to 0$ by the first moment method.

If $p<1/4$, choose $p<\delta <1/4$. Binary codes of relative minimum distance above $2\delta$ have positive asymptotic rate by a greedy packing bound, and nearest-codeword decoding fails only when more than $\delta n$ channel errors occur. That probability tends to zero.

At crossover probability $p=1/2$, the two rows of the transition matrix of a binary symmetric channel coincide. Its output is then independent of its input and its capacity is zero.

An error is undetected by codeword-membership checking when the received word is a different valid codeword. For a linear code this occurs exactly when the nonzero channel-error vector is itself a codeword.

A Roche lobe is the region around one component of a circular binary inside the critical effective-potential surface through the inner Lagrange point.

An equivalence relation says which set elements should count as the same for a particular purpose. In modular arithmetic, for example, distinct integers with the same remainder are equivalent. The relation gathers interchangeable set elements into equivalence classes; the quotient set then treats each whole equivalence class as one object.

Formally, an equivalence relation on a set $X$ is a binary relation $R\subseteq X\times X$, written $x\sim y$, satisfying three conditions for all $x,y,z\in X$:These conditions make the equivalence classes a partition of a set: each set element belongs to exactly one class. ^[ref]

For a worked example, take the finite set $X=\{0,1,\dots ,8\}$ and restrict integer congruence modulo three to $X$:Reflexivity follows because $x-x=0$. The symmetric relation property follows by changing the sign of a difference, and transitivity follows by adding $x-y$ and $y-z$: divisibility by three is preserved in both steps. Thus $0\sim 3$ and $3\sim 6$ force $0\sim 6$. The three equivalence classes are $\{0,3,6\}$, $\{1,4,7\}$ and $\{2,5,8\}$. Their members alternate along the number line; membership in an equivalence class need not mean being close together.

The transitivity requirement rules out a tempting alternative. On $\{0,1,2\}$, define nearness by the absolute value condition $|x-y|\le 1$. This binary relation is reflexive and symmetric, but $0$ is near $1$ and $1$ is near $2$ while $0$ is not near $2$. Its neighborhoods $\{0,1\}$, $\{0,1,2\}$ and $\{1,2\}$ overlap without being equal. They are not equivalence classes or a partition of a set.

A relation $R$ is transitive when $xRy$ and $yRz$ imply $xRz$.

A relation $R$ is symmetric when $xRy$ implies $yRx$.

A relation $R$ on $X$ is reflexive when $xRx$ for every $x\in X$.

The Neyman-Pearson lemma says that an optimal region accepting $P$ has the likelihood-ratio formwith possible randomization on the boundary.

For distinct probability distributions $P,Q$, the optimal error exponents in hypothesis testing give type-II error $Q^{\otimes n}(B_n)$ decay rate $D(P\Vert Q)$ among tests whose type-I error $P^{\otimes n}(B_n^c)$ stays below any fixed number in $(0,1)$.

A dyadic rational has the form $m/2^k$. Its terminating binary expansion has an alternative expansion ending in infinitely many $1$ digits.

The Hamming distance between two equal-length words is the number of coordinates in which they differ.