Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.02030 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916879166078976 |
|---|---|
| author | Huibregtse, Mark Lemus-Vidales, Cristobal Vella, David |
| author_facet | Huibregtse, Mark Lemus-Vidales, Cristobal Vella, David |
| contents | We study the process of bootstrap percolation on n x n permutation matrices, inspired by the work of Shapiro and Stephens [5]. In this percolation model, cells mutate (from 0 to 1) if at least two of their cardinal neighbors contain a 1, and thereafter remain unchanged; the process continues until no further mutations are possible. After carefully analyzing this process, we consider how it interacts with the notion of (in)decomposable permutations. We prove that the number of indecomposable permutations whose matrices "fill up'' to contain all 1's (or are "full") is half of the total number of full permutations. This leads to a new proof of a key result in [5], that the number of full n x n permutations is the (n-1)st large Schroeder number. Finally, after rigorously justifying a heuristic argument in [5], we find a new formula for the number of n x n "no growth" permutations, and hence a new solution to the well-known n-kings problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02030 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bootstrap Percolation, Indecomposable Permutations, and the n-Kings problem Huibregtse, Mark Lemus-Vidales, Cristobal Vella, David Combinatorics 05A15 We study the process of bootstrap percolation on n x n permutation matrices, inspired by the work of Shapiro and Stephens [5]. In this percolation model, cells mutate (from 0 to 1) if at least two of their cardinal neighbors contain a 1, and thereafter remain unchanged; the process continues until no further mutations are possible. After carefully analyzing this process, we consider how it interacts with the notion of (in)decomposable permutations. We prove that the number of indecomposable permutations whose matrices "fill up'' to contain all 1's (or are "full") is half of the total number of full permutations. This leads to a new proof of a key result in [5], that the number of full n x n permutations is the (n-1)st large Schroeder number. Finally, after rigorously justifying a heuristic argument in [5], we find a new formula for the number of n x n "no growth" permutations, and hence a new solution to the well-known n-kings problem. |
| title | Bootstrap Percolation, Indecomposable Permutations, and the n-Kings problem |
| topic | Combinatorics 05A15 |
| url | https://arxiv.org/abs/2508.02030 |