most recent 30 from http://mathoverflow.net 2013-06-18T06:52:53Z http://mathoverflow.net/feeds/question/16102 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16102/compare-standard-deviations-from-medians Adam 2010-02-22T23:18:53Z 2010-02-22T23:40:21Z

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

http://mathoverflow.net/questions/16102/compare-standard-deviations-from-medians/16106#16106 fedja 2010-02-22T23:40:21Z 2010-02-22T23:40:21Z

<p>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. </p>