7
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – Pat Devlin
    Mar 21, 2018 at 2:33
  • 3
    $\begingroup$ @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$. $\endgroup$
    – fedja
    Mar 21, 2018 at 2:52
  • 3
    $\begingroup$ 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. $\endgroup$
    – Peter Heinig
    Mar 21, 2018 at 17:45
  • 1
    $\begingroup$ 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|$. $\endgroup$
    – Penelope Benenati
    Mar 21, 2018 at 20:32
  • 1
    $\begingroup$ 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). $\endgroup$
    – monkeymaths
    Mar 23, 2018 at 11:01

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$
    – Penelope Benenati
    Mar 23, 2018 at 22:13
  • 2
    $\begingroup$ 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! $\endgroup$
    – Mike
    Mar 23, 2018 at 23:21
  • 2
    $\begingroup$ @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. $\endgroup$
    – Brian Hopkins
    Jun 14, 2018 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.