Pairs of vertices with high degree difference

Question

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following 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$?

After some consideration, I am quite convinced that the following inequality is true:

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

but I am stuck on actually proving it. What can be done, we can divide $V$ into the following parts $$A := \{v_i : \mathrm{deg}(v_i)\ge k\},$$ $$B := \{v_i : \mathrm{deg}(v_i)\le n-k\},$$ $$R=V\setminus(A\cup B).$$ Obviously, we can assume that $A$ is a clique and $B$ is an anticlique. So in the case of $|A|\ge k+1$ we get the bound directly - it is enough to erase all edges outside of $A$. The case of $|B|\ge k+1$ is similar. I am however stuck in the case of $\max(|A|, |B|)\le k$. I thought about rewriting $\mathcal{I}_k(G)$ as $$\mathcal{I}_k(G) = \sum_{i=k}^{n}|C_i|\sum_{j=0}^{i-k}|C_j|,$$ where $$C_i := \{v_j: \mathrm{deg}(v_j)=i \},$$ and using some kind of degree sequence criterion, such as Erdős–Gallai and similar.

But I did not succeed. 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

I have just found out a very similar theorem to the one in the question. Some work still must be done, but it seems clear that it is very closely related.

https://arxiv.org/pdf/1806.08303.pdf

Let $G = (V, E)$ be a simple graph. For $B$ a subset of the vertex set $V$ , we define the spread of $B$ as $$\mathrm{sp}(B) = \Big\{\max[\mathrm{deg}(u)]− \min[\mathrm{deg}(v)] : u, v ∈ B\Big\}.$$ We then define, for an integer $k ≥ 0$, quantity $\mathrm{sp}(G, k)$ as: $$\max{\Big\{|B|: \ {sp(B) ≤ k}\Big\}},$$ i.e. "the largest cardinality of a subset of vertices of $G$ with spread at most $k$".

Now, we have the following,

Theorem (Erdős, Chen, Rousseau and Schelp):

Let $G$ be a graph on $n ≥ k+1$ vertices, then $\mathrm{sp}(G, k-1) ≥ k + 1.$

EDIT: I think that this indeed answers the question. Let $m$ be the minimal degree of $\mathrm{sp}(G,k-1)$, and let $M$ be the maximal. Define $$A:=\{v_i : \mathrm{deg}(v_i)<m\},$$ $$B:=\{v_j: \mathrm{deg}(v_j)>M\}.$$ Set $a=|A|, b=|B|$. We know that $a+b<n-k-1$. Now, take a vertex $v\in \mathrm{sp}(G, k-1)$ and observe that $v$ cannot be "connected" with a vertex in $A$ and $B$ simultaneously. Thus we can define

$$\mathrm{sp}_A = \{ v\in \mathrm{sp}(G,k-1): \ |\mathrm{deg}(u)-\mathrm{deg}(v)|\ge k \ \text{for some} \ u \in A \ \},$$ $$\mathrm{sp}_B = \{ v\in \mathrm{sp}(G,k-1): \ |\mathrm{deg}(u)-\mathrm{deg}(v)|\ge k \ \text{for some} \ u \in B \ \},$$ $$\mathrm{sp}_A \cap \mathrm{sp}_B = \emptyset.$$ Set $x_1=|\mathrm{sp}_A|, x_2=|\mathrm{sp}_B|$. Thus $$a+b\le n-k-1,$$ $$x_1+x_2\le k+1,$$ and we have $$\mathcal{I}_k(G)\le ab+ax_1+bx_2.$$ We can further assume that $a\ge b$, thus: $$ab+ax_1+bx_2 \le ab+a(x_1+x_2)\le ab+a(k+1),$$ and as $a\le n-k-1 \le k+1$, we get $$ab+a(k+1)\le (a+b)(k+1)\le (n-k-1)(k+1), $$ which ends the proof.

Answer 2

For small $n$ and $k$, you can solve the problem via integer linear programming as follows. Let $N = \{1,\dots,n\}$ be the node set, and let $E = \{i \in N, j \in N: i < j\}$ be the set of node pairs. For $(i,j)\in E$, let binary decision variable $x_{i,j}$ indicate whether edge $(i,j)$ appears in the graph. For $i\in N$, let integer decision variable $d_i$ be the degree of node $i$. For $(i,j)\in E$, let binary decision variables $u_{i,j}$ and $v_{i,j}$ indicate whether $d_i - d_j \ge k$ or $d_j - d_i \ge k$, respectively. The problem is to maximize $$\sum_{(i,j) \in E} (u_{i,j} + v_{i,j}) \tag1$$ subject to \begin{align} \sum_{(i,j) \in E} x_{i,j} + \sum_{(j,i) \in E} x_{j,i} &= d_i &&\text{for $i\in N$} \tag2\\ k - (d_i - d_j) &\le (k + n - 1) (1 - u_{i,j}) &&\text{for $(i,j)\in E$} \tag3\\ k - (d_j - d_i) &\le (k + n - 1) (1 - v_{i,j}) &&\text{for $(i,j)\in E$} \tag4\\ \end{align} The objective $(1)$ maximizes the number of times that $|d_i-d_j| \ge k$. Constraint $(2)$ enforces the definition of degree. Constraint $(3)$ enforces the implication $u_{i,j} = 1 \implies d_i - d_j \ge k$. Constraint $(4)$ enforces the implication $v_{i,j} = 1 \implies d_j - d_i \ge k$.

For $n \le 20$ and $\lfloor n/2 \rfloor \le k \le n-1$, the optimal objective value turns out to be $(k+1)(n-k-1)$.

Answer 3

This is too long for a comment, but it's really just a modification of John Tuwim's answer. By using the reductions discussed in the original post, the proof becomes even simpler and it shows that $$\mathcal{I}_k(G)\leq \mathrm{sp}(G,k-1)(n-\mathrm{sp}(G,k-1))\leq (k+1)(n-k-1).$$

Let $G$ be a graph on $n$ vertices, let $\lceil n/2\rceil\leq k\leq n-1$, let $A=\{v\in V(G): d(v)\geq k\}$, $B=\{v\in V(G):d(v)\leq n-k-1\}$, and $R=V(G)\setminus (A\cup B)$. As mentioned in the original post, we can assume $A$ is clique, $B$ is an independent set, $R=\emptyset$, and $$n-\mathrm{sp}(G,k-1)< b:=|B|\leq |A|=:a<\mathrm{sp}(G,k-1)$$ (we can assume $b\leq a$ since $\mathcal{I}_k(G)=\mathcal{I}_k(\bar{G})$).

Now using the result of Erdős et al., there exists $S\subseteq V(G)$ such that $\mathrm{sp}(G,k-1)=|S|\geq k+1$ and for all $u,v\in S$, $|d(u)-d(v)|\leq k-1$. Let $|s_A|=|S\cap A|$ and $s_B=|S\cap B|$ and note that $$ s_A+s_B=\mathrm{sp}(G,k-1)>a\geq b.\tag1 $$ Thus \begin{align*} \mathcal{I}_k(G)&\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)(b-s_B)\\ &\leq s_A(b-s_B)+s_B(a-s_A)+(a-s_A)s_A+(b-s_B)s_B\\ &=(s_A+s_B)(n-s_A-s_B)\\ &\leq (k+1)(n-k-1) \end{align*} where we used ($1$) in the second inequality and $\mathrm{sp}(G,k-1)\geq k+1>n/2$ in the last inequality.

Note that this calculation gives an upper bound in terms of $\mathrm{sp}(G, k-1)=s_A+s_B$ and shows that even when $\mathrm{sp}(G, k-1)=s_A+s_B=k+1$ we have a strict inequality provided $s_A<a$ and $s_B<b$.