# Browsing by Subject "spanning trees"

###### Results Per Page

###### Sort Options

Item Open Access METROPOLIZED FOREST RECOMBINATION FOR MONTE CARLO SAMPLING OF GRAPH PARTITIONS(SIAM Journal on Applied Mathematics, 2023-08-01) Autry, E; Carter, D; Herschlag, GJ; Hunter, Z; Mattingly, JCWe develop a new Markov chain on graph partitions that makes relatively global moves yet is computationally feasible to be used as the proposal in the Metropolis-Hastings method. Our resulting algorithm is able to sample from a specified measure on partitions or spanning forests. Being able to sample from a specified measure is a requirement of what we consider as the gold standard in quantifying the extent to which a particular map is a gerrymander. Our proposal chain modifies the recently developed method called recombination (ReCom), which draws spanning trees on joined partitions and then randomly cuts them to repartition. We improve the computational efficiency by augmenting the statespace from partitions to spanning forests. The extra information accelerates the computation of the forward and backward proposal probabilities which are required for the Metropolis-Hastings algorithm. We demonstrate this method by sampling redistricting plans on several measures of interest and find promising convergence results on several key observables of interest. We also explore some limitations in the measures that are efficient to sample from and investigate the feasibility of using parallel tempering to extend this space of measures.Item Open Access Metropolized Multiscale Forest Recombination for Redistricting(Multiscale Modeling & Simulation, 2021-01) Autry, EA; Carter, D; Herschlag, GJ; Hunter, Z; Mattingly, JCItem Open Access Minimal Resolutions of Monomial Ideals(2020) Ordog, Erika AnastasiaIt has been an open problem since the early 1960s to construct free resolutions of monomial ideals. Beginning with the 1966 Taylor resolution, the first resolution for arbitrary monomial ideals, there have since been many constructions of free resolutions of monomial ideals, satisfying some of the following properties: canonical, minimal, universal, closed form, and combinatorial. The goal is for such a construction to satisfy all of the desired properties. The constructions given so far each satisfy some subset of these properties. This dissertation gives a full solution to the problem,satisfying all of the desired properties, over a field of characteristic 0 and most positive characteristics, with these positive characteristics depending on the ideal. The differential is a weighted sum over lattice paths in $\mathbb{Z}^n$ that come from analogues of spanning trees in simplicial complexes that are indexed by the lattice. Over a field of any characteristic, noncanonical sylvan resolutions are defined. The noncanonical resolutions are minimal, universal, closed form, and combinatorial. The differentials sum over choices of these generalized spanning trees at points along the lattice paths. Finally, a combinatorial description of the canonical three-variable case is given, and noncanonical sylvan resolutions are used to produce planar graph resolutions in the three-variable case and a minimal resolution of the Stanley–Reisner ideal of the minimal triangulation of $\mathbb{RP}^2$ in characteristic 2. Substantial portions of the results are based on joint work with John Eagon and Ezra Miller.