PACM Colloquium: Xiaoyu He, Mathematics, Princeton University

*This event is in-person and open only to Princeton University ID holder 

Sequential Importance Sampling and Tomescu's Conjecture

Abstract: 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. 

_{Bio: Xiaoyu He is a mathematician working in extremal and probabilistic combinatorics with applications to theoretical computer science. He completed his PhD on probabilistic methods in combinatorics at Stanford University in 2021 and is currently an NSF Postdoctoral Research Fellow in the Department of Mathematics at Princeton University.}