Have you come across this kind of "degree" concept? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T10:13:10Z http://mathoverflow.net/feeds/question/109134 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109134/have-you-come-across-this-kind-of-degree-concept Have you come across this kind of "degree" concept? Felix Goldberg 2012-10-08T12:04:36Z 2012-10-08T12:32:18Z <p>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$.</p> <p>Now suppose you have a graph whose vertex set is partitioned into $A,B,U$ and define for every vertex $u \in U$ the <strong><em>"AB-degree"</em></strong> of $u$ as $\Delta_{u}=d_{A}(u)-d_{B}(u)$. </p> <p>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|)$. </p> <p>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). </p> <p>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?</p> http://mathoverflow.net/questions/109134/have-you-come-across-this-kind-of-degree-concept/109141#109141 Answer by Ben Barber for Have you come across this kind of "degree" concept? Ben Barber 2012-10-08T12:32:18Z 2012-10-08T12:32:18Z <p>This should perhaps be a comment, but I don't have enough reputation.</p> <p>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.)</p>