2026/07/21 by Andrew Elvey Price, Juliette Schabanel, Paul Thévenin
#math.CO
In this paper, we study a bootstrap percolation process on the finite triangular grid \mathfrakTn of side length n. We say that a subset η of points in \mathfrakTn percolates if the final configuration, starting from η, is the whole grid \mathfrakTn. A basis of size n is then a subset of points of \mathfrakTn of minimum cardinality which percolates. In this paper, we first prove that the generating function counting bases satisfies an algebraic differential equation. Then, by analysing a modified version of this equation, we prove that the number tn of bases of size n exhibits a stretched exponential asymptotic behaviour. More precisely, we show that tn ∼ c n!e√(12n)n5/12, for some constant c>0. These bases were recently shown by the second author to be in bijection with 3-permutations avoiding the patterns (12, 12) and (231, 312), so this represents to our knowledge the first proven example of an asymptotic stretched exponential appearing in the study of pattern avoiding permutations.