MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $A \subseteq V(G)$ be a set of vertices in a graph $G$ and let $v \in V(G)$ be some vertex. Define $d_{A}(v)$ as the number of neighbours of $v$ inside $A$.

Now suppose you have a graph whose vertex set is partitioned into $A,B,U$ and define for every vertex $u \in U$ the "AB-degree" of $u$ as $\Delta_{u}=d_{A}(u)-d_{B}(u)$.

My interest is in the special case when each vertex in $A \cup B$ has exactly $d$ neighbours in $U$. Obviously then $\sum_{u \in U}{\Delta_{u}}=d(|A|-|B|)$.

But what about $\sum_{u \in U}{|\Delta_{u}|}$? I want to find a nice upper bound for it in terms of $|A|,|B|$ and $d$ (and perhaps $|U|$, although I don't see how it can help).

I have a kind of hand-waiving argument that says it can't be too big, but I hope that somebody has already treated this kind of problem before in some detail before. Or maybe it's simple and I'm missing something?

share|cite|improve this question
up vote 2 down vote accepted

This should perhaps be a comment, but I don't have enough reputation.

What sort of bound are you hoping for? The trivial bound $d(|A|+|B|)$ appears to be tight: take $G=K_{d,d}$ with $A$ one of the parts and $B$ empty. (Two copies of this will give you an example with $A$ and $B$ the same size.)

share|cite|improve this answer
Ok, you are right, of course - but I have in mind a situation where $A,B$ are non-empty and somewhat smaller than $U$ - in that case the trivial bound is excessively large. My feeling is that the true value can be bounded by something like $2.5d(|A|-|B|)$. – Felix Goldberg Oct 8 '12 at 12:37
It looks like you'll still need some more structure. Taking any example, we can obtain an example with $|A|=|B|$ by taking two disjoint copies, and then the hoped for bound will vanish. The "$U$ large" condition doesn't seem very useful, as we only care about the at most $d(|A|+|B|)$ vertices adjacent to $A \cup B$. For $\sum_{u \in U} \Delta_u$ to be smaller than $d(|A|+|B|)$ you need to know something about how many $u \in U$ have neighbours in both $A$ and $B$. – Ben Barber Oct 8 '12 at 12:50

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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