Bootstrap Percolation, Indecomposable Permutations, and the n-Kings problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _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 |