When analyzing large systems that have an enormous number of possibilities, studying collections of randomly selected pieces can provide an effective way to understand likely properties or behaviors of the entire system. Random sampling can be applied to polling, estimating quantities in physical systems, detecting gerrymandering, and more. However, it is challenging to do random sampling in a way that is both fast and accurate. This project will study the fundamental mathematics behind methods for random sampling, including introducing new sampling methods, developing new tools to analyze existing sampling methods, and finding problems amenable to the new approaches the investigator develops. One goal is to improve methods used to quantify and detect gerrymandering, making those methods both faster and more reliable. Part of the award will support a summer program where students learn about math, computer science, and data science motivated by problems related to democracy. This project considers random sampling of structures on graphs, such as spin configurations on the vertices of a graph or partitions of a graph into connected pieces. In one direction, the investigator will consider Pirogov-Sinai theory (PST), an approach from statistical physics that could help advance the state-of-the-art in sampling/counting algorithms for spin systems and more. Specific questions include adapting PST from infinite to finite settings; using PST and the additional probabilistic infor