The imbalance theorem
The imbalance conjecture is now a theorem. James Alexander Schreib and Yousof Yavari posted a proof last week.
What does the conjecture theorem say? Start with a graphG with no edge between two nodes of the same degree. Then for every edge, calculate the absolute value of the difference of the degree of each end. The imbalance theorem says there exists another graphH whose vertices have degrees corresponding to the differences of degrees inG.
For example, letG be the graph below.
The edges from the top red vertexA to each of the blue vertices around it all have degree difference 5 becauseA has degree 6 and the vertices a0 to a4 have degree 1. The edge between the two red vertices,A andB, has degree difference 2. The remaining vertices have degree difference 3.
So the multiset of degree differences is
{5, 5, 5, 5, 5, 2, 3, 3, 3}
The imbalance theorem says there exists a graphH whose nodes have these degrees. Here is an example of such anH.
Note that inH, the 5 red nodes have degree 5, the single green node has degree 2, and the three blue nodes have degree 3.
More graph postsThe post The imbalance theorem first appeared on John D. Cook.