Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Racial segregation has long been a problem in communities across the country. One approach to help understand such an important issue is to attempt to describe it quantitatively. Many metrics have been developed, all with various strengths and weaknesses, but none fully capture the nuances of this complicated issue. This work provides an overview of four of the mathematical approaches that have been developed to study segregation, explains how they function using small examples, and compares and contrasts their effectiveness in various situations. We then focus on segregation in Los Angeles (LA) County, including a detailed exploration of the most recent score proposed by authors Sousa and Nicosia, which conducts a random walk and outputs the number of steps it takes to reach all racial classes in the system. While we found there is a difference between the average step lengths of LA County vs. an unbiased null model, attempts to standardize outputs erases crucial data, and compressing this issue into one score is not representative of its complexity. This suggests that future exploration should attempt to study segregation more comprehensively rather than distilling an incredibly complicated and important issue into a single statistic. More work is needed to quantitatively represent the complexities of racial segregation in an effective matter.more » « lessFree, publiclyaccessible full text available July 1, 2025

We prove that a polynomial fraction of the set of $k$component forests in the $m \times n$ grid graph have equal numbers of vertices in each component, for any constant $k$. This resolves a conjecture of Charikar, Liu, Liu, and Vuong, and establishes the first provably polynomialtime algorithm for (exactly or approximately) sampling balanced grid graph partitions according to the spanning tree distribution, which weights each $k$partition according to the product, across its $k$ pieces, of the number of spanning trees of each piece. Our result follows from a careful analysis of the probability a uniformly random spanning tree of the grid can be cut into balanced pieces. Beyond grids, we show that for a broad family of latticelike graphs, we achieve balance up to any multiplicative $(1 \pm \varepsilon)$ constant with constant probability. More generally, we show that, with constant probability, components derived from uniform spanning trees can approximate any given partition of a planar region specified by Jordan curves. This implies polynomialtime algorithms for sampling approximately balanced treeweighted partitions for latticelike graphs. Our results have applications to understanding political districtings, where there is an underlying graph of indivisible geographic units that must be partitioned into $k$ populationbalanced connected subgraphs. In this setting, treeweighted partitions have interesting geometric properties, and this has stimulated significant effort to develop methods to sample them.more » « lessFree, publiclyaccessible full text available June 24, 2025

In the United States, regions (such as states or counties) are frequently divided into districts for the purpose of electing representatives. How the districts are drawn can have a profound effect on who is elected, and drawing the districts to give an advantage to a certain group is known as gerrymandering. It can be surprisingly difficult to detect when gerrymandering is occurring, but one algorithmic method is to compare a current districting plan to a large number of randomly sampled plans to see whether it is an outlier. Recombination Markov chains are often used to do this random sampling: randomly choose two districts, consider their union, and split this union up in a new way. This approach works well in practice and has been widely used, including in litigation, but the theory behind it remains underdeveloped. For example, it is not known if recombination Markov chains are irreducible, that is, if recombination moves suffice to move from any districting plan to any other. Irreducibility of recombination Markov chains can be formulated as a graph problem: for a planar graph G, is the space of all partitions of G into k connected subgraphs (k districts) connected by recombination moves? While the answer is yes when districts can be as small as one vertex, this is not realistic in realworld settings where districts must have approximately balanced populations. Here we fix district sizes to be k_1 +/ 1 vertices, k_2 +/ 1 vertices, ... for fixed k_1, k_2, ..., a more realistic setting. We prove for arbitrarily large triangular regions in the triangular lattice, when there are three simply connected districts, recombination Markov chains are irreducible. This is the first proof of irreducibility under tight district size constraints for recombination Markov chains beyond small or trivial examples. The triangular lattice is the most natural setting in which to first consider such a question, as graphs representing states/regions are frequently triangulated. The proof uses a sweepline argument, and there is hope it will generalize to more districts, triangulations satisfying mild additional conditions, and other redistricting Markov chains.more » « lessFree, publiclyaccessible full text available April 1, 2025

We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or
graphlets ) of rooted, bounded degree graphs. Our algorithm utilizes a vertexpercolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near lineartime perfect sampling algorithms for polymer models and weighted nonrooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.Free, publiclyaccessible full text available January 31, 2025 
Berry, Jonathan ; Shmoys, David ; Cowen, Lenore ; Naumann, Uwe (Ed.)In the United States, regions (such as states or counties) are frequently divided into districts for the purpose of electing representatives. How the districts are drawn can have a profound effect on who's elected, and drawing the districts to give an advantage to a certain group is known as gerrymandering. It can be surprisingly difficult to detect when gerrymandering is occurring, but one algorithmic method is to compare a current districting plan to a large number of randomly sampled plans to see whether it is an outlier. Recombination Markov chains are often used to do this random sampling: randomly choose two districts, consider their union, and split this union up in a new way. This approach works well in practice and has been widely used, including in litigation, but the theory behind it remains underdeveloped. For example, it's not known if recombination Markov chains are irreducible, that is, if recombination moves suffice to move from any districting plan to any other. Irreducibility of recombination Markov chains can be formulated as a graph problem: for a planar graph G, is the space of all partitions of G into κ connected subgraphs (κ districts) connected by recombination moves? While the answer is yes when districts can be as small as one vertex, this is not realistic in realworld settings where districts must have approximately balanced populations. Here we fix district sizes to be κ1 ± 1 vertices, κ2 ± 1 vertices,… for fixed κ1, κ2,…, a more realistic setting. We prove for arbitrarily large triangular regions in the triangular lattice, when there are three simply connected districts, recombination Markov chains are irreducible. This is the first proof of irreducibility under tight district size constraints for recombination Markov chains beyond small or trivial examples. The triangular lattice is the most natural setting in which to first consider such a question, as graphs representing states/regions are frequently triangulated. The proof uses a sweepline argument, and there is hope it will generalize to more districts, triangulations satisfying mild additional conditions, and other redistricting Markov chains.more » « less

Abstract Finding outlying elementsin probability distributions can be a hard problem. Taking a real example from Voting Rights Act enforcement, we consider the problem of maximizing the number of simultaneous majorityminority districts in a political districting plan. An unbiased random walk on districting plans is unlikely to find plans that approach this maximum. A common search approach is to use a
biased random walk : preferentially select districting plans with more majorityminority districts. Here, we present a third option, calledshort bursts , in which an unbiased random walk is performed for a small number of steps (called theburst length ), then restarted from the most extreme plan that was encountered in the last burst. We give empirical evidence that shortburst runs outperform biased random walks for the problem of maximizing the number of majorityminority districts, and that there are many values of burst length for which we see this improvement. Abstracting from our use case, we also consider short bursts where the underlying state space is a line with various probability distributions, and then explore some features of more complicated state spaces and how these impact the effectiveness of short bursts. 
Chakrabarti, Amit ; Swamy, Chaitanya (Ed.)We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertexpercolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near lineartime perfect sampling algorithms for polymer models and weighted nonrooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.more » « less

null (Ed.)At the macroscale, controlling robotic swarms typically uses substantial memory, processing power, and coordination unavailable at the microscale, e.g., for colloidal robots, which could be useful for fighting disease, fabricating intelligent textiles, and designing nanocomputers. To develop principles that can leverage physical interactions and thus be used across scales, we take a twopronged approach: a theoretical abstraction of selforganizing particle systems and an experimental robot system of active cohesive granular matter that intentionally lacks digital electronic computation and communication, using minimal (or no) sensing and control. As predicted by theory, as interparticle attraction increases, the collective transitions from dispersed to a compact phase. When aggregated, the collective can transport nonrobot “impurities,” thus performing an emergent task driven by the physics underlying the transition. These results reveal a fruitful interplay between algorithm design and active matter robophysics that can result in principles for programming collectives without the need for complex algorithms or capabilities.more » « less

Chawla, Shuchi (Ed.)Understanding the complexity of approximately counting the number of weighted or unweighted independent sets in a bipartite graph (#BIS) is a central open problem in the field of approximate counting. Here we consider a subclass of this problem and give an FPTAS for approximating the partition function of the hardcore model for bipartite graphs when there is sufficient imbalance in the degrees or fugacities between the sides (L, R) of the bipartition. This includes, among others, the biregular case when λ = 1 (approximating the number of independent sets of G) and Delta_R >= 7 Delta_L log(Delta_L). Our approximation algorithm is based on truncating the cluster expansion of a polymer model partition function that expresses the hardcore partition function in terms of deviations from independent sets that are empty on one side of the bipartition. Further consequences of this method for unbalanced bipartite graphs include an efficient sampling algorithm for the hardcore model and zerofreeness results for the partition function with complex fugacities. By utilizing connections between the cluster expansion and joint cumulants of certain random variables, we go beyond previous algorithmic applications of the cluster expansion to prove that the hardcore model exhibits exponential decay of correlations for all graphs and fugacities satisfying our conditions. This illustrates the applicability of statistical mechanics tools to algorithmic problems and refines our understanding of the connections between different methods of approximate counting.more » « less