Abstract :

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.