Search

A $k$-height on a graph $G=(V, E)$ is an assignment $V\to\{0, \ldots, k\}$ such that the value on ajacent vertices differs by at most $1$. We study the Markov chain on $k$-heights that in each step selects a vertex at random, and, if admissible, increases or decreases the value at this vertex by one. In the cases of $2$-heights and $3$-heights we show that this Markov chain is rapidly mixing on certain families of grid-like graphs and on planar cubic $3$-connected graphs. The result is based on a novel technique called block coupling, which is derived from the well-established monotone coupling approach. This technique may also be effective when analyzing other Markov chains that operate on configurations of spin systems that form a distributive lattice. It is therefore of independent interest., Comment: 31 pages, 8 figures. Supplemental code available at Zenodo, doi:10.5281/zenodo.13912818

Xavier and Yushi run a ``random race'' as follows. A continuous probability distribution $\mu$ on the real line is chosen. The runners begin at zero. At time $i$ Xavier draws $\mathbf{X}_i$ from $\mu$ and advances that distance, while Yushi advances by an independent drawing $\mathbf{Y}_i$. After $n$ such moves, Xavier wins a valuable prize provided he not only wins the race but leads after every step; that is, $\sum_{i=1}^k \mathbf{X}_i > \sum_{i=1}^k \mathbf{Y}_i$ for all $k = 1,2, \dots, n$. What distribution is best for Xavier, and what then is his probability of getting the prize?, Comment: 9 pages

We derive a large deviation principle for random permutations induced by probability measures of the unit square, called permutons. These permutations are called $\mu$-random permutations. We also introduce and study a new general class of models of random permutations, called Gibbs permutation models, which combines and generalizes $\mu$-random permutations and the celebrated Mallows model for permutations. Most of our results hold in the general setting of Gibbs permutation models. We apply the tools that we develop to the case of $\mu$-random permutations conditioned to have an atypical proportion of patterns. Several results are made more concrete in the specific case of inversions. For instance, we prove the existence of at least one phase transition for a generalized version of the Mallows model where the base measure is non-uniform. This is in contrast with the results of Starr (2009, 2018) on the (standard) Mallows model, where the absence of phase transition, i.e., phase uniqueness, was proven. Our results naturally lead us to investigate a new notion of permutons, called conditionally constant permutons, which generalizes both pattern-avoiding and pattern-packing permutons. We describe some properties of conditionally constant permutons with respect to inversions. The study of conditionally constant permutons for general patterns seems to be a challenging problem., Comment: 36 pages, 7 figures; to appear in International Mathematics Research Notices

At MOVES 2019, Barry Cipra casually introduced a new "Sol Lewitt" puzzle to fellow conference goers. Several brainstorming sessions ensued with Barry, Peter Winkler , Donna Dietz, and other attendees. This paper is to document the puzzle and some insights so others can enjoy and build on this lovely puzzle. (Look for it in an upcoming book by Peter!), Comment: 28 figures, 14 pages