Mathematics

The Slow-coloring Game: Online Sum-Paintability

Douglas B. West (Illinois Math and Zhejiang Normal University)

Abstract: The slow-coloring game is played by Lister and Painter on a graph $G$. Initially, all vertices of $G$ are uncolored. In each round, Lister marks a non-empty set $M$ of uncolored vertices, and Painter colors a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. The score of the game is the sum of the sizes of all sets marked by Lister. The goal of Painter is to minimize the score, while Lister tries to maximize it; the score under optimal play is the cost. A greedy strategy for Painter keeps the cost of $G$ to at most $\chi(G)n$ when $G$ has $n$ vertices, which is asyptotically sharp for Turan graphs. On various classes Painter can do better. For $n$-vertex trees the maximum cost is $\lfloor 3n/2\rfloor$. There is a linear-time algorithm and inductive formula to compute the cost on trees, and we characterize the extremal $n$-vertex trees. Also, Painter can keep the cost to at most $(1+3k/4)n$ when $G$ is $k$-degenerate, $7n/3$ when $G$ is outerplanar, and $3.9857n$ when $G$ is planar. These results involve various subsets of Grzegorz Gutowski, Tomasz Krawczyk, Thomas Mahoney, Gregory J. Puleo, Hehui Wu, Michal Zajac, and Xuding Zhu.

Fighting Gerrymandering with the Blue Waters Supercomputer

Wendy K. Tam Cho (Dept of Political Science, Illinois)

Abstract: Important insights into redistricting can be gained through an interdisciplinary approach that combines research from many fields, including statistics, operations research, computer science, high performance computing, math, law, and political science. Our work integrates insights from all of these disciplines to create a novel approach for analyzing and reforming redistricting in a way that is tightly coupled with the framework that the Supreme Court has outlined over the past 5 decades.

Wendy K. Tam Cho is Professor in the Departments of Political Science, Statistics, Asian American Studies, and the College of Law, Senior Research Scientist at the National Center for Supercomputing Applications, a Guggenheim Fellow, Faculty in the Illinois Informatics Institute, and Affiliate of the Cline Center for Democracy, the CyberGIS Center for Advanced Digital and Spatial Studies, the Computational Science and Engineering Program, and the Program on Law, Behavior, and Social Science, at the University of Illinois at Urbana-Champaign. She also founded and teaches at the Champaign-Urbana Math Circle.

Her research on redistricting has been published in many scholarly fields, including operations research, computer science, high performance computing, political science, and law. Its premise as a standard for adjudicating partisan gerrymandering was the subject of 11 amicus briefs and was presented in oral arguments before the Supreme Court.

Cancelled

Abstract: Cancelled