Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.