Biregular graph

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 with $m$ left vertices of degree $r$ and $n$ right vertices of degree $s$, let $X$ be the indicator vector of a uniformly selected independent set. Use base-two information entropy. Shearer inequality gives $H(X_U)\le r^{-1}{\sum }_{w\in W}H(X_{N(w)})$. Conditional on $X_U$, each right vertex with an empty selected neighbourhood is an independent fair binary choice, and the other right vertices are forbidden. Writing $q_w=\mathbb{P}(X_{N(w)}=0)$ gives $H(X)\le r^{-1}{\sum }_w[H(X_{N(w)})+r{q}_w]$. For the $2^s$ neighbourhood patterns, assign weight $2^r$ to the zero pattern and weight one to all others. Jensen's inequality implies $H(Y)+r{q}_w\le {\log }_2(2^r+2^s-1)$. Since $n/r=m/s$, the bound follows from $H(X)={\log }_{2}i(G)$. If $s$ divides $m$, the disjoint union of $m/s$ copies of the complete bipartite graph $K_{s,r}$ attains equality: each component has $2^s+2^r-1$ independent sets.

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