High degree differences in bipartite graphs

Question

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us define the quantity:

$$\mathcal{I}_k(G) := \sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\mathrm{deg}(v_j)|\ge k}\Big\},$$ i.e. the number of all those pairs $(v_i,v_j)$ with degree difference greater or equal to $k$.

In the answer to a previous question,

Pairs of vertices with high degree difference

I was able to prove, that:

For $k>\frac{n}{2}$, we have

\begin{equation} \mathcal{I}_k(G) \ \le \ 2k(n-k). \end{equation}

Now, my current question is: does it also hold for bipartite graphs? More precisely, consider a bipartite graph with vertices $$\{v_1,v_2,\dots, v_n\} \cup \{w_1,w_2,\dots, w_n\}.$$ Is it also true that (still assuming $k>n/2$) $$\sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\mathrm{deg}(w_j)|\ge k}\Big\} \ \le \ 2k(n-k)? $$ If we would think about those two problems in terms of adjacency matrices, then the first (solved) problem is about symmetric matrices and the current one is about general matrices without the symmetry condition. Playing around with small $n$ seems to confirm this conjecture. Unfortunately, the proof suggested in the previous case does not seem to work in this case (it is not clear how to generalize it).

What I tried doing was incorporating the Gale–Ryser and Ford-Fulkerson conditions (about the bipartite realization of double integer sequences as degree sequences). Unfortunately, I did not succeed.

As previously: I would be very grateful for any comment or insight. Maybe looking on this question, You will think of some other related problem or theorem that might be helpful. Maybe You are able to say what a general strategy might be appropriate to handle this problem. It may turn out that for some reason this problem is trivial but I have overlooked it. I will appreciate any help or advice.

Answer 1

Please check carefully.

Denote $d_i=\deg(v_i)$, $\delta_i=\deg(w_i)$. We assume (without loss of generality) that $d_1\geqslant d_2\geqslant\ldots \geqslant d_n$ and $\delta_1\geqslant \delta_2\geqslant\ldots \geqslant \delta_n$. We start with the observation similar to that of Erdős, Chen, Rousseau and Schelp: there exists $s\in \{1,2,\ldots,n-k+1\}$ such that $d_s\leqslant \delta_{s+k-1}+k-1$.

Indeed, assume the contrary: $d_i\geqslant \delta_{i+k-1}+k$ for all $i=1,2,\ldots,n-k+1$. Then the total number of edges incident to $v_1,\ldots,v_{n-k+1}$ is at least $\delta_k+\ldots+\delta_n+k(n-k+1)$. Thus at least $k(n-k+1)$ these edges go to the vertices $\delta_1,\ldots,\delta_{k-1}$ (call such edges interesting), but each of them may be incident to at most $n-k+1$ interesting edges, so totally we have at most $(k-1)(n-k+1)$ interesting edges. A contradiction.

Analogously, there exists $t\in \{1,2,\ldots,n-k+1\}$ such that $\delta_t\leqslant d_{t+k-1}+k-1$.

Call $(i,j)$ a $D$-pair, corr. $\Delta$-pair, if $d_i\geqslant \delta_j+k$, corr. $\delta_j\geqslant d_i+k$. Since $k>n/2$, we have $d_i>n/2$ for a $D$-pair $(i,j)$ and $d_i<n/2$ for a $\Delta$-pair $(i,j)$. Thus there exists $i_0\in \{1,2,\ldots,n+1\}$ such that

$i\leqslant i_0-1$ for any $D$-pair $(i,j)$, and $i\geqslant i_0$ for any $\Delta$-pair $(i,j)$.

Analogously, choose $j_0\in \{1,2,\ldots,n+1\}$ such that

$j\leqslant j_0-1$ for any $\Delta$-pair $(i,j)$, and $j\geqslant j_0$ for any $D$-pair $(i,j)$.

Another restriction

for a $D$-pair $(i,j)$ is that either $i<s$ or $j>s+k-1$ (or both).

Analogously,

for $\Delta$-pairs we have $j<t$ or $i>t+k-1$.

And having all these restrictions (now forget about the initial graph), I claim that the total number of $D$-pairs and $\Delta$-pairs is at most $2k(n-k)$.

The proof is bit boring. Fix $i_0$ and $j_0$ and look for the value of $s$ for which the number of $D$-pairs satisfying our restrictions is maximal possible. It is not hard to see that it is maximized when $s=1$ or $s=n-k+1$ (if $i_0\leqslant n-k+1$ then putting $s=n-k+1$ we get no extra restrictions from "$i<s$ or $j>s+k-1$"; analogously, if $j_0\geqslant k+1$ we get no extra restriction for $s=1$. Finally, if $i_0\geqslant n-k+2$ and $j_0\leqslant k$, the extra restriction remove $(i_0-s)(s+k-j_0)$ pairs, which is a concave function in $s$, thus it is minimized on the interval $s\in [1,n-k+1]$ in one of the endpoints). Hence we may assume $s=1$ or $s=n-k+1$, analogously $t=1$ or $t=n-k+1$. There are two essentially different cases now:

1. $s=1$, $t=n-k+1$. We get $j\geqslant k+1$ for $D$-pairs and $j\leqslant n-k$ for $\Delta$-pairs $(i,j)$. Thus any $i$ participates in at most $n-k$ $D$-pairs and in at most $n-k$ $\Delta$-pairs, totally $i$ participates in at most $n-k$ pairs (since it can not participate in both types of pairs). Therefore the total number of pairs does not exceed $n(n-k)\leqslant 2k(n-k)$.

2. $s=t=1$. We get $j\geqslant k+1$ for $D$-pairs and $i\geqslant k+1$ for $\Delta$-pairs $(i,j)$. Denote $a=\max(k+1,j_0)$, $b=\max(k+1,i_0)$. Then the total number $D$-pairs is at most $(n-a+1)(b-1)$, the total number $\Delta$-pairs is at most $(n-b+1)(a-1)$. When $a,b\in [k+1,n+1]$, the sum $S:=(n-a+1)(b-1)+(n-b+1)(a-1)$ which is bilinear in $a$ and $b$ is maximized at one of four endpoints. When $a=b=k+1$ we get $S=2k(n-k)$, if, say, $a=n+1$, we get $S=n(n-b+1)\leqslant n(n-k)\leqslant 2k(n-k)$.

Answer 2

I confirmed via integer linear programming that the maximum value is $2k(n-k)$ for $n \le 20$ and $k>n/2$. The formulation is the same as in my answer to the linked question, except for the following changes:

• The node set is $N = \{1,\dots,2n\}$.
• The candidate edge set is $E = \{i \in N, j \in N: i \le n < j\}$.
• Constraints $(3)$ and $(4)$ become \begin{align} k - (d_i - d_j) &\le (k + n) (1 - u_{i,j}) &&\text{for $(i,j)\in E$} \tag3\\ k - (d_j - d_i) &\le (k + n) (1 - v_{i,j}) &&\text{for $(i,j)\in E$} \tag4\\ \end{align}