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 $G = (U, V, E)$ be a bipartite graph with $|U| = |V|$, $|U|$ large. If the median degree of a node in U is 4, and the median degree of a node in V is 7, is there a way to tell whether the degree distribution of U or V has a greater standard deviation?

share|cite|improve this question

Not with this information alone. Indeed, nothing you assumed contradicts the maximal degree's being 11 or less and in that case you can just make another graph with degrees $11-d_j$ instead of $d_j$ (all you really need for the existence of the bipartite graph with given degrees is that the total degree of vertices in $U$ is the same as the total degree of vertices in $V$; this is literally true if you allow multiple edges and true under the assumption that all degrees are much less than $|U|,|V|$ if you do not). But that other graph has the medians reversed and the same standard deviations as the original one.

share|cite|improve this answer

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.