Triangle Percolation on the Grid

We consider a geometric percolation process partially motivated by recent work of Hejda and Kala. Specifically, we start with an initial set \(X \subseteq {\mathbb {Z}}^2\), and then iteratively check whether there exists a triangle \(T \subseteq {\mathbb {R}}^2\) with its vertices in \({\mathbb {Z}}^2\) such that T contains exactly four points of \({\mathbb {Z}}^2\) and exactly three points of X. In this case, we add the missing lattice point of T to X, and we repeat until no such triangle exists. We study the limit sets S, the sets stable under this process, including determining their possible densities and some of their structure.

This work was started at the 2022 Graduate Research Workshop in Combinatorics, which was supported in part by NSF grant 1953985 and a generous award from the Combinatorics Foundation. We thank the referees for their careful reading and useful comments that improved the presentation of this manuscript.

Authors and Affiliations

1. Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL, USA

   Igor Araujo & Robert A. Krueger

2. Department of Mathematics, Emory University, Atlanta, GA, USA

   Bryce Frederickson

3. Department of Mathematics, Iowa State University, Ames, IA, USA

   Bernard Lidický

4. Department of Mathematics and Statistics, University of Wyoming, Laramie, WY, USA

   Tyrrell B. McAllister

5. Department of Mathematical and Statistical Sciences, University of Colorado Denver, Denver, CO, USA

   Florian Pfender

6. Department of Mathematics, Rutgers University, Piscataway, NJ, USA

   Sam Spiro

7. Department of Algebra, Faculty of Mathematics and Physics, Charles University, Prague, Czechia

   Eric Nathan Stucky

Corresponding author

Correspondence to Igor Araujo.

Editor in Charge: János Pach

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Igor Araujo research partially supported by UIUC Campus Research Board RB 22000. Robert A. Krueger research supported the NSF Graduate Research Fellowship Program Grant No. DGE 21-4675. Bernard Lidický research of this author is supported in part by NSF Grant DMS-2152490 and Scott Hanna fellowship. Florian Pfender research is partially supported by NSF grant DMS-2152498. Sam Spiro research supported by the NSF Mathematical Sciences Postdoctoral research Fellowships Program under Grant DMS-2202730. Eric Nathan Stucky research partially supported by Czech Science Foundation Grant 21-00420M.

Appendix: Computer-Assisted Proofs

In this appendix, we discuss the Python code for a program that proves Lemmas 3.4 and 3.8, and classifies the sets considered in Remark 3.9 (Fig. 13). This code can be found in the supplementary files.

The code enumerates all B-stable subsets of a given set of points using a depth-first search. First we set up some helpful functions, including the main recursive step. Then we give the three applications. Lemma 3.4 states every B-stable set \(S \subsetneq {\mathbb {Z}}^2\) has \(|S \cap ([6]\times [6])|\le 9\) and Remark 3.9 describes all B-stable sets \(S \subseteq [6]^2\) with \(\Gamma (S) \ne \emptyset \) and \(|S|=9\) up to rotation and reflection; the code completes this calculation in only a few seconds on a personal computer. Lemma 3.8 states that every B-stable set \(S \subsetneq {\mathbb {Z}}^2\) with \(\Gamma (S) \cap ([6]\times [12]) \ne \emptyset \) has \(|S \cap ([6]\times [12])|\le 16\); this takes longer to calculate, about 6 min on the same hardware.

All B-stable sets \(S \subseteq [6]^2\) with \(\Gamma (S) \ne \emptyset \) and \(|S|=9\), up to reflection and rotation

Full size image

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions