Skip to main content
Notice removed Draw attention by user153000
Bounty Ended with Fedor Petrov's answer chosen by CommunityBot
added 4 characters in body
Source Link
user153000
user153000

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

Notice added Draw attention by user153000
Bounty Started worth 100 reputation by CommunityBot
deleted 8 characters in body
Source Link
user153000
user153000

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

Source Link
user153000
user153000

High degree differences in bipartite graphs

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.