Timeline for Have you come across this kind of "degree" concept?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 8, 2012 at 16:47 | vote | accept | Felix Goldberg | ||
| Oct 8, 2012 at 12:50 | comment | added | Ben Barber | 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$. | |
| Oct 8, 2012 at 12:37 | comment | added | Felix Goldberg | 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|)$. | |
| Oct 8, 2012 at 12:32 | history | answered | Ben Barber | CC BY-SA 3.0 |