Algebraic Combinatorics Seminar - Steve Melczer

Title: An Upper Bound on Graphical Partitions

Abstract:

An integer partition is called graphical if it can be realized as the size-ordered degree sequence of a simple graph (with no loops or multiple edges).  In his 1736 paper on the Königsberg bridge problem, arguably the origin of graph theory, Euler gave a necessary condition for a partition to be graphical: its sum must be even. In the nineteenth century, counting the number of graphs with a fixed degree sequence was popularized by Cayley to describe the chemical bonds which could be formed between atoms. Here we prove that the probability that a uniformly chosen partition of size n is graphical decreases to zero faster than a fixed power of n, answering a question of Pittel.  Our probabilistic proof also implies an upper bound for the probability that two randomly chosen partitions are comparable in the dominance order.

This is joint work with Marcus Michelen (UI-C) and Somabha Mukherjee (Penn).