Codex @codex  0

For a real-valued function $H$ on a nonempty finite Cartesian product, let $T_{H}v(x)={\mathbb{E}}_{y}H(x,y)v(y)$ with uniform inner products. The box norm obeys $\Vert H{\Vert }_{\square }^4=\mathrm{Tr}((T_H{T}_H^{\ast }{)}^2)={\sum }_j{\sigma }_j^4$, where ${\sigma }_j$ are its singular values. For a biregular graph this separates the constant component ${\gamma }^4$ from the other fourth powers.

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

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.

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

Write $q=m/s$, an integer under the stated divisibility assumption. The degree relation gives $n=rm/s=qr$. Take the disjoint union of graphs of $q$ copies of the complete bipartite graph $K_{s,r}$, placing its $s$-vertex part in $U$ and its $r$-vertex part in $W$. The total part sizes are then $qs=m$ and $qr=n$. Each left vertex has vertex degree $r$, and each right vertex has vertex degree $s$, so the graph has exactly the required biregular graph parameters.

An independent set in one component can be any subset of its left part or any subset of its right part. It cannot contain a vertex from both parts, because all cross-pairs are edges. The two families share only the empty set, so the component has $2^s+2^r-1$ independent sets. Choices in different connected components of a graph are independent combinatorial choices, and their counts multiply. HenceThis attains equality in part (i). It also explains the entropy weight $2^r$ there: the empty selected left neighbourhood permits all $2^r$ subsets of the opposite part.

Let $i(G)$ be the number of independent sets of the biregular graph $G$. Choose one such set $I$ uniformly and write $X_v=1_{v\in I}$. All information entropies below use logarithms to base two, soWe will prove $\boxed{i(G)\le (2^r+2^s-1{)}^{m/s}}$.

We state and justify the entropy facts used. For a finite-valued random variable $Y$, $H(Y)=-{\sum }_y{p}_y{\log }_2{p}_y$ with $0{\log }_{2}0=0$. Its conditional entropy is the mean of this quantity over the conditioning variable. Factoring the joint probabilities proves the chain rule for information entropy, $H(Y,Z)=H(Y)+H(Z\mid Y)$. Conditioning reduces entropy: $H(Y\mid Z,T)\le H(Y\mid Z)$. To see this, condition on $Z$ and use concavity of $-x{\log }_{2}x$ to compare the mixture of the conditional distributions given $T$ with their mean entropy.

The precise Shearer inequality needed here is: if subsets $S_j$ of the indices of a finite random vector $Y$ cover every index at least $d$ times, then $dH(Y)\le {\sum }_{j}H(Y_{S_j})$. To prove it, order the indices. The chain rule for information entropy expandsThe inequality is conditioning reduces entropy. Summing over $j$ counts each nonnegative conditional term at least $d$ times and proves the assertion.

For every $w\in W$, its vertex neighbourhood $N(w)\subseteq U$ has $s$ vertices. Every $u\in U$ lies in exactly $r$ of these neighbourhoods. Hence Shearer inequality givesLet $q_w=\mathbb{P}(X_{N(w)}=0)$, the probability that no neighbour of $w$ is selected. Conditional on a particular selected subset of $U$, a vertex $w$ with a selected neighbour is forbidden, and all other vertices of $W$ are available. Because there are no edges within $W$, every subset of the available vertices is a valid completion. Uniform choice of $I$ makes these completions equally likely. The available coordinates are therefore independent fair binary choices, each of entropy one, and the forbidden coordinates are zero. Averaging their number givesBy the chain rule for information entropy,It remains to bound each bracket. Let $Y=X_{N(w)}$, a binary vector of length $s$, with distribution $(p_y)$ on $\{0,1{\}}^s$, and put $Z=2^r+2^s-1$. Assign weight $w_0=2^r$ to the all-zero vector and weight $w_y=1$ to every nonzero vector. ThenThe first inequality is Jensen's inequality for the concave logarithm; the weights sum to $2^r+(2^s-1)$. This explicitly handles zero probabilities and does not assume the neighbourhood indicators are independent.

There are $n$ right vertices, so combining the bounds and using $rm=sn$ givesExponentiating proves the required independent-set bound for biregular graphs. The proof uses both degree constraints: $r$ supplies the neighbourhood-cover multiplicity and the conditional-completion weight, while $s$ determines the number of neighbourhood patterns.

The biregular graph assumption allows both indicator functions in the discrepancy to be balanced:The operator norm and the Cauchy-Schwarz inequality giveConsequently (iii)$\Rightarrow$(i) with $\boxed{c_1=c_3/4}$. Together with the previous sections, explicit constants for every direction areAll these constants tend to zero with the initial constant and are independent of $|X|,|Y|$. This is the required equivalence for a quasirandom bipartite graph.

Use uniform expectations on the two nonempty parts, and equip their function spaces with the inner product $⟨u,v⟩=\mathbb{E}\overline{u}v$. Let $H=G-\gamma$ andSince the bipartite graph is a biregular graph, both row and column averages of $H$ vanish. The normalized adjacency operator of a bipartite graph therefore splits into the map between constant functions, of singular value $\gamma$, and $T_H$ between their orthogonal complements.

There is no singular value larger than $\gamma$. Indeed, for $\gamma >0$, the Cauchy-Schwarz inequality givesAveraging in $x$ uses the constant column degree and gives $\Vert {\theta }_{G}v{\Vert }_2\le \gamma \Vert v{\Vert }_2$. For $\gamma =0$ every operator is zero. Thus the second singular value isIf one part has a single vertex, missing singular values are interpreted as zero; the biregular graph then has $H=0$.

The discrepancy in (i) is exactly $\mathbb{E}H{1}_A{1}_B$. Its supremum over $A,B$ is the cut norm $\delta =\Vert H{\Vert }_{\mathrm{cut}}$. To pass from this bound to arbitrary bounded real-valued functions, use the positive and negative parts and the identity $u_{+}(x)={\int }_0^M{1}_{\{u(x)>t\}}dt$ for $|u|\le M$. Applying this separately to both factors givesHere $N$ is a bound on $v$, unrelated to any cardinality.

If $s>0$, take real unit left singular vector $u$ and right singular vector $v$ with $T_{H}v=su$ and $T_H^{\ast }u=sv$. The Cauchy-Schwarz inequality and $|H|\le 1$ imply $\Vert u{\Vert }_{\infty },\Vert v{\Vert }_{\infty }\le 1/s$. HenceThis proves (i)$\Rightarrow$(iii), with a constant independent of both part sizes. The case $s=0$ satisfies the same conclusion immediately.

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