An official website of the United States government
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 polynomial-time 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 lattice-like 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 polynomial-time algorithms for sampling approximately balanced tree-weighted partitions for lattice-like 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$$ population-balanced connected subgraphs. In this setting, tree-weighted partitions have interesting geometric properties, and this has stimulated significant effort to develop methods to sample them.
more »
« less
Maximal Chains in Bond Lattices
Let $$G$$ be a graph with vertex set $$\{1,2,\ldots,n\}$$. Its bond lattice, $BL(G)$, is a sublattice of the set partition lattice. The elements of $BL(G)$ are the set partitions whose blocks induce connected subgraphs of $$G$$. In this article, we consider graphs $$G$$ whose bond lattice consists only of noncrossing partitions. We define a family of graphs, called triangulation graphs, with this property and show that any two produce isomorphic bond lattices. We then look at the enumeration of the maximal chains in the bond lattices of triangulation graphs. Stanley's map from maximal chains in the noncrossing partition lattice to parking functions was our motivation. We find the restriction of his map to the bond lattice of certain subgraphs of triangulation graphs. Finally, we show the number of maximal chains in the bond lattice of a triangulation graph is the number of ordered cycle decompositions.
more »
« less
- Award ID(s):
- 1928930
- PAR ID:
- 10347945
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 29
- Issue:
- 3
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Exceptional sequences are certain sequences of quiver representations. We introduce a class of objects called strand diagrams and use these to classify exceptional sequences of representations of a quiver whose underlying graph is a type An Dynkin diagram. We also use variations of these objects to classify $$c$$-matrices of such quivers, to interpret exceptional sequences as linear extensions of explicitly constructed posets, and to give a simple bijection between exceptional sequences and certain saturated chains in the lattice of noncrossing partitions.more » « less
-
Abstract A barcode is a finite multiset of intervals on the real line. Jaramillo-Rodriguez (2023) previously defined a map from the space of barcodes with a fixed number of bars to a set of multipermutations, which presented new combinatorial invariants on the space of barcodes. A partial order can be defined on these multipermutations, resulting in a class of posets known as combinatorial barcode lattices. In this paper, we provide a number of equivalent definitions for the combinatorial barcode lattice, show that its Möbius function is a restriction of the Möbius function of the symmetric group under the weak Bruhat order, and show its ground set is the Jordan-Hölder set of a labeled poset. Furthermore, we obtain formulas for the number of join-irreducible elements, the rank-generating function, and the number of maximal chains of combinatorial barcode lattices. Lastly, we make connections between intervals in the combinatorial barcode lattice and certain classes of matchings.more » « less
-
We investigate the rich combinatorial structure of premodel structures on finite lattices whose weak equivalences are closed under composition. We prove that there is a natural refinement of the inclusion order of weak factorization systems so that the intervals detect these composition closed premodel structures. In the case that the lattice in question is a finite total order, this natural order retrieves the Kreweras lattice of noncrossing partitions as a refinement of the Tamari lattice, and model structures can be identified with certain tricolored trees.more » « less
-
null (Ed.)Let C be a class of graphs closed under taking induced subgraphs. We say that C has the clique-stable set separation property if there exists c ∈ N such that for every graph G ∈ C there is a collection P of partitions (X, Y ) of the vertex set of G with |P| ≤ |V (G)| c and with the following property: if K is a clique of G, and S is a stable set of G, and K ∩ S = ∅, then there is (X, Y ) ∈ P with K ⊆ X and S ⊆ Y . In 1991 M. Yannakakis conjectured that the class of all graphs has the clique-stable set separation property, but this conjecture was disproved by M. G¨o¨os in 2014. Therefore it is now of interest to understand for which classes of graphs such a constant c exists. In this paper we define two infinite families S, K of graphs and show that for every S ∈ S and K ∈ K, the class of graphs with no induced subgraph isomorphic to S or K has the clique-stable set separation property.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.37236/10983
