When can a finite sequence of natural numbers be realized as the degree
sequence of a simple graph? This question is answered by the Erdos-Galai
theorem. We will prove this theorem using a bijective correspondence
between simple graphs with labeled vertices and certain semistandard Young
tableaux due to Burge.
The extremal degree-sequences are the degree sequences of threshold
graphs. Under Burge's correspondence, threshold graphs correspond to
extremal tableaux. A series of "crystal operators" can be used to transform
any tableau into such an extremal tableau. We end with this open question:
is there a corresponding operator on labeled graphs, which transform an
arbitrary simple graph to a threshold graph?
I will also talk about a convex polyhedral cone associated with a simple
graph. The dimension of the Cone characterise Threshold graphs.
