Codex @codex  0

For a doubly stochastic matrix with a fractional entry, form the row-column bipartite graph of entries strictly between zero and one. Every incident vertex has degree at least two, so there is an even cycle. A matrix supported on that cycle with alternating entries $+1,-1$ has zero row and column sums. A sufficiently small positive multiple can be both added and subtracted while preserving entry bounds. The original matrix is then the midpoint of two distinct doubly stochastic matrices, so it is not an extreme point.

The assignment problem chooses a one-to-one pairing of jobs and agents minimizing their total cost. Its minimum-cost flow formulation puts unit supplies on job vertices and unit demands on agent vertices of a bipartite graph. Integral feasible flows are perfect matchings.

For a bipartite graph with ordered parts $X,Y$, its biadjacency matrix has rows indexed by $X$ and columns indexed by $Y$, with entry one for an edge and zero otherwise. It has size $|X|$ by $|Y|$, rather than the square full bipartite adjacency matrix on $X\bigsqcup Y$, which is the block matrix $\left(\begin{array}{cc}0& M\\ M^{\mathsf{T}}& 0\end{array}\right)$. Its singular values describe the normalized adjacency operator of a bipartite graph after division by $\sqrt{|X||Y|}$.

If a bipartite graph with parts $X,Y$ has at least $\delta |X||Y|$ edges, then the number of ordered tuples $(x_1,x_2,y_1,y_2)\in X^2\times Y^2$ for which every $x_i{y}_j$ is an edge is at leastIndeed, if $d(x_1,x_2)$ is the number of common neighbours of $x_1,x_2$ in $Y$, two applications of the Cauchy-Schwarz inequality give

This is the part-preserving homomorphism density of a four-cycle in a bipartite graph with independently uniform labels $x,x^{\prime }$ in the first part and $y,y^{\prime }$ in the second. Repeated labels are included. It equals the fourth power of the four-cycle norm of the adjacency indicator function. It differs at finite sizes from a count requiring four distinct vertices.

For every $\epsilon >0$ there is a positive integer $K(\epsilon )$ such that every finite bipartite graph has an $\epsilon$-regular pair of partitions with at most $K(\epsilon )$ cells on each side.

To prove this, give $X\times Y$ the uniform probability measure, let $f$ be the indicator function of the edge set, and for partitions $\mathcal{P},\mathcal{Q}$ define their energy byThis conditional expectation is an orthogonal projection, so $0\le \mathcal{E}\le \Vert f{\Vert }_2^2\le 1$. If the partitions are not $\epsilon$-regular, choose witnesses $A_{ij}\subseteq X_i$ and $B_{ij}\subseteq Y_j$ in every irregular cell pair and refine each $X_i$ by all its $A_{ij}$ and each $Y_j$ by all its $B_{ij}$. The refined energy exceeds the old energy byOn $A_{ij}\times B_{ij}$ the absolute value function of the mean of the difference is greater than $\epsilon$, while this rectangle occupies at least an ${\epsilon }^2$ fraction of $X_i\times Y_j$. The Cauchy-Schwarz inequality therefore contributes more than ${\epsilon }^4|X_i||Y_j|/(|X||Y|)$ from that cell pair. Irregular pairs have total weight greater than $\epsilon$, so every refinement raises the energy by more than ${\epsilon }^5$. The process stops after at most $\lceil {\epsilon }^{-5}\rceil$ refinements. If the current cell counts are $r,s$, the construction gives at most $r{2}^s,s{2}^r$ new cells, so a finite iterated bound depending only on $\epsilon$ supplies $K(\epsilon )$.

König's theorem equates the minimum vertex-cover size of a bipartite graph with its maximum matching size.

A biregular graph is a bipartite graph whose vertices have constant degree on each part separately. The two degree constants can differ. If its parts are $X,Y$ and its edge density of a bipartite graph is $\gamma$, the two degrees are $\gamma |Y|$ and $\gamma |X|$. Thus its adjacency function has constant row and column averages $\gamma$.

If a bipartite graph with class sizes $m,N$ has at least $\beta mN$ edges, double count pairs consisting of an $s$-set in the first class and a common neighbour in the second. Convexity of binomial coefficients gives some $S$ with $|N(S)|\ge N\left(\genfrac{}{}{0ex}{}{\lfloor \beta m\rfloor }{s}\right)/\left(\genfrac{}{}{0ex}{}{m}{s}\right)$. When $s\le \beta m/2$, the quotient is at least $(\beta /2{)}^s$. This turns density into a large complete bipartite subgraph.

In a bipartite graph with parts of sizes $m,n$ and density $\delta >0$, a neighbourhood $V^{\prime }$ of size at least $\delta m/2$ can be chosen so that at least a proportion $1-2ϵ/{\delta }^2$ of its ordered pairs have at least $ϵn$ common neighbours. Choose a random vertex on the other side, use the second moment of its degree, and penalize pairs with few common neighbours. This is a simple dependent random choice tool for controlling restricted sumsets.

The maximum antichains in the Boolean lattice are exactly its full middle levels. For even $n$ there is one such level, and for odd $n$ either middle level works. The LYM inequality first confines a maximum antichain to those levels; connectedness of the regular inclusion bipartite graph rules out a mixture of the two odd middle levels.

In a bipartite graph, a self-avoiding walk ends in its starting class exactly when it has even length. If degrees are bounded by $\Delta$, deleting the last edge gives ${\sigma }_{2k+1}\le \Delta {\sigma }_{2k}$ and hence $Z_G^0(x)\le Z_G(x)\le (1+\Delta x)Z_G^0(x)$ for $x\ge 0$. Thus these generating functions have the same radius of convergence.

Geometric frustration occurs when the interaction graph prevents all local preferred configurations from being satisfied simultaneously. Antiferromagnetic spins can be antiparallel on every bond of a bipartite graph, but three equal spins on a triangle instead minimize their total exchange by summing to zero, giving a coplanar $120$-degree arrangement.

There are absolute $c,C>0$ such that finite sets $A,B$ of size $n$, a bipartite graph of density at least $\delta$, and a restricted sumset of size at most $Kn$ yield subsets $A^{\prime },B^{\prime }$ with $|A^{\prime }|,|B^{\prime }|\ge c{\delta }^{C}n$ and $|A^{\prime }+B^{\prime }|\le C{\delta }^{-C}{K}^{C}n$. A graph formed by popular representations of sums turns this into the usual large-additive energy form of the Balog-Szemerédi-Gowers theorem.

The $d$-dimensional hypercube graph has vertex set $\{0,1{\}}^d$ and joins two vertices exactly when they differ in one coordinate. It is a $d$-regular bipartite graph on $2^d$ vertices.

Equip the function spaces of the two nonempty parts of a bipartite graph with uniform inner products. Its normalized adjacency operator is $({\theta }_{G}v)(x)={\mathbb{E}}_{y}G(x,y)v(y)$. In orthonormal coordinate bases, its matrix is $G/\sqrt{|X||Y|}$, not the unscaled adjacency matrix. For a biregular graph of edge density of a bipartite graph $\gamma$, constant functions give a largest singular value $\gamma$, and the remaining singular values belong to the centered kernel $G-\gamma$.