Bipartite graph

A graph is bipartite when its vertices split into two classes and every edge joins the two different classes.

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

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

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

For a biregular graph of edge density of a bipartite graph $\gamma$, small rectangular discrepancy, a box norm fourth power close to ${\gamma }^4$, and a small second singular value of the normalized adjacency operator of a bipartite graph are equivalent notions of quasirandomness, with quantitative bounds independent of the part sizes. Centering the adjacency function removes the constant singular component.

Let $H=M-\delta J$ be the centered biadjacency matrix of an equal-part biregular graph, and put $s=\Vert H{\Vert }_{\mathrm{op}}$. For subsets $A,B$ of the two parts, their edge discrepancy is $1_A^{\mathsf{T}}H{1}_B$. The Cauchy-Schwarz inequality proves the displayed bound. If the part size is $n$, centering the two indicator vectors improves it to $sn\sqrt{\alpha (1-\alpha )\beta (1-\beta )}$. The centered four-cycle identity for a biregular graph shows that $t_4(G)\le {\delta }^4(1+c^4)$ implies $s\le c\delta n$ for $c\ge 0$.

For an equal-part biregular graph with part size $n$ and degree $\delta n$, let $M$ be its biadjacency matrix and $H=M-\delta J$, where $J$ is the all-ones matrix. The constant row and column sums make $H$ annihilate constants on both sides. Since $M{M}^{\mathsf{T}}={\delta }^{2}nJ+H{H}^{\mathsf{T}}$ and the two summands have zero products, their squared matrix trace splits as displayed. The bipartite four-cycle density counts the squared matrix trace of $M{M}^{\mathsf{T}}$ divided by $n^4$.

A half graph has two vertex classes $X=\{x_1,\dots ,x_n\}$ and $Y=\{y_1,\dots ,y_n\}$, with $x_i$ adjacent to $y_j$ exactly when $i\le j$. Its nested vertex neighbourhoods give a useful obstruction to partitions in which every pair is a regular pair of vertex sets.

Partition both sides of a half graph into classes of size at least $100$. A class of size $s$ has at most $2\lceil s/10\rceil$ elements with fewer than $s/10$ class elements on one side in the underlying order. If there are $k_X$ and $k_Y$ classes, the union of these boundary elements has size at most $2n/5+2(k_X+k_Y)\le 11n/25$. Some index $m$ is therefore away from both boundaries. The class containing $m$ on each side has at least one tenth of its points strictly above $m$ and strictly below $m$. Choosing lower $X$ points with upper $Y$ points, or upper $X$ points with lower $Y$ points, yields edge density of a bipartite graph values one and zero. Both cannot be within $1/10$ of the same class-pair edge density of a bipartite graph, so that pair is not a $1/10$-regular pair of vertex sets.

A graph is bipartite if and only if it contains no odd cycle. One direction follows because every cycle alternates between the two vertex classes. For the converse, in each connected component of a graph choose a root and partition the vertices according to the parity of their graph distance from it. An edge joining equal parities would close an odd cycle, so every edge crosses the partition.

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

A star graph is the complete bipartite graph with one centre and $m$ leaves. Any pair of its edges meet at the centre.

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