# Combinatorial optimization problem for bipartite graphs

Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote its degree by $d_i$.

How can we prove that, if $m \le \frac{|V_1||V_2|}{2}=\frac{n^2}{8}$, then we must have $$\sum_{(i,j): i\in V_1,\,j\in V_2} \left(d_i+d_j\right)\le (1-c)n\,m~,$$

where $c$ is a positive constant (bounded away from zero)?

Additionally, I am also interested in finding the minimum value of $c$ satisfying the above inequality.

• So a double counting argument shows that what you’re trying to bound is equal to $\sum_i d_i ^2$ where the sum is taken over all vertices. This is probably minimized when the graph is regular and maximized when we have as many vertices of max degree as possible. – Pat Devlin Mar 21 '18 at 2:33
• @PatDevlin Indeed, it is. The largest sum occurs when we have $m/(n/2)$ vertices of degree $n/2$ on the left and, correspondingly, $n/2$ (all) vertices of degree $m/(n/2)$ on the right giving the value $\frac{mn}2+\frac{m^2}{n/2}$ (assuming natural divisibility conditions), so the sharp upper bound in the case under consideration is $1-c=\frac 34$. – fedja Mar 21 '18 at 2:52
• The most relevant article is, I think: [Cheng, T.C.Edwin; Guo, Yonglin; Zhang, Shenggui; Du, Yongjun, Extreme values of the sum of squares of degrees of bipartite graphs. Discrete Math. 309, No. 6, 1557-1564 (2009).]. The authors report to have solved your problem completely. I did not read the article. Maybe I will, but please do not wait for that. The results are sufficiently complicated to make it impossible (for me at least) to read off the optimal value of $c$. It's also worth pointing out that de Caen's 1998 general bound merely yields a bound of $\frac54 n m$, too large for you. – Peter Heinig Mar 21 '18 at 17:45
• Thank you Fedja, Devlin, Peter. It seems that, in the above article, Lemma 2 states what Fedja said for the specific case of the question I asked, when $|V_1|=|V_2|$. – Penelope Benenati Mar 21 '18 at 20:32
• Quick question: Is the sum over all pairs $(i,j) \in E$ or is it $(i,j) \in E, i \in V_1, j \in V_2$? (in the first case, every edge would be counted twice). – monkeymaths Mar 23 '18 at 11:01

Here, let $E$ be the set of edges, $I=V_1$ one side of the graph, $J=V_2$ the other side. Let $S$ be the set of edges $(i,j)$ s.t. both $d(i) \geq .9(n/2)$ and $d(j) \geq .9(n/2)$. Further suppose that $|S| \geq .95|E|$ or we are done.

Now let $I_S$ be the set of $i \in I$ s.t. $i$ is incident to an edge in $S$. Then each $i \in I_S$ has degree at least $.9(n/2)$ in $G$; as there are only $n^2/8$ edges in $G$ it follows that $|I_S|$ is at most $\frac{m}{.9(n/2)} = \frac{20m}{9n}$. Likewise let $J_S$ be the set of $j$ s.t. $j$ is incident to an edge in $S$. It follows that $|J_S|$ is at most $\frac{20m}{9n}$.

Now, for each $i \in I$, let $d_S(i)$ be the number of edges in $S$ that $i$ is incident to. likewise for each $j \in J$ let $d_S(j)$ be the number of edges in $S$ that $j$ is incident to. Then on the one hand, assuming that $|S| \geq .95|E|$:

$$\sum_{i \in I} d_S(i) = \sum_{i \in I_S} d_S(i) \geq .95 \sum_{i \in I} d(i) \geq .95 \sum_{i \in I_S} d(i)$$

$$\geq .95 |I_s| \left(.9 \times \frac{n}{2}\right) \ \geq \ |I_S| \times \frac{2n}{5}.$$

On the other hand, $\sum_{i \in I_S} d_S(i) \leq |I_S| \times |J_S|$ (since every edge in $S$ goes from $I_S$ to $J_S$), and $J_S$ is no more than $\frac{20m}{9n}$, which is no greater than $n/3$ for $m \leq \frac{n^2}{8}$.

So $S$ cannot be more than $.95|E|$, which as mentioned in the first paragraph, implies your bound.

• Thank you. However, Fedja already explained above that the minimum value of $c$ that satisfies the problem inequality is $\frac{1}{4}$, which is consistent with Lemma 2 of [Cheng, T.C.Edwin; Guo, Yonglin; Zhang, Shenggui; Du, Yongjun, Extreme values of the sum of squares of degrees of bipartite graphs. Discrete Math. 309, No. 6, 1557-1564 (2009)] (the article above mentioned by Peter). The bound $\frac{3}{4}n\,m$ is therefore tight and cannot be improved (asymptotically when $n$ goes to infinity). – Penelope Benenati Mar 23 '18 at 22:13
• Yes just saw after I filled out. I am still learning my way around this site. Good question, and quite an elegant solution by Fedja! – Mike Mar 23 '18 at 23:21
• @PenelopeBenenati, in case you're going to cite the result formally, Cheng 2009 attributes Lemma 2 to [Ahlswede, R.; Katona, G. O. H., Graphs with maximal number of adjacent pairs of edges. Acta Math. Acad. Sci. Hungar. 32 (1978), no. 1-2, 97–120] where it's Theorem 1. – Brian Hopkins Jun 14 '18 at 12:45