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.

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.

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 (equivalent to 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.

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.