Sequential Importance Sampling and Tomescu's Conjecture

-
Xiaoyu He, Princeton University
Fine Hall 214

Sequential importance sampling (SIS) is a powerful Monte Carlo technique for estimating the answers to otherwise intractable counting and statistics problems. In its most basic form, SIS approximates the number of leaves in a decision tree by sampling a random path down from the root and taking the product of all the nonzero down-degrees along this path. This simple idea has been used to efficiently count Latin Squares, bipartite matchings, and self-avoiding walks, to generate random graphs with fixed degree sequence, and to give a new proof of Bregman's permanent theorem. In this talk, we give an overview of SIS and then present a purely theoretical application, using it to prove a graph-coloring conjecture of Tomescu from 1971: that every connected graph with n vertices and chromatic number k > 3 has at most k!(k-1)^{n-k} proper k-colorings. Based on joint work with Jacob Fox and Freddie Manners.