MIT Combinatorics Seminar

From Characterizations to Algorithms

Persi Diaconis, (Stanford University)

Monday, Arpil 24, 2006   4:30 PM;   Building 4 Room 270 


"There are many characterizations proved because they are elegant, with no apparent further use." In joint work with Joe Blitzstein, we show how to convert these into algorithms for counting and random generation. Examples include graphs with given degree sequences (Erdos-Gallai characterization) simplicial complexes with given f-vectors (Kruskal-Katona characterization) and many others. Application to ecology and statistics are given."