About

Janko Gravner is a researcher whose work spans a broad range of topics in probability, cellular automata, growth phenomena, and percolation theory. His research includes the study of bootstrap percolation, nucleation scaling, and the dynamics of growth models on various lattice structures, as well as cellular automata with random rules and their periodic solutions. Gravner has contributed to understanding the behavior of complex systems such as excitable media, disordered growth models, and the effects of pollution in bootstrap percolation, often employing rigorous probabilistic and combinatorial methods. His work also encompasses the analysis of cellular automata trajectories, the stability of these systems, and their applications to modeling physical and biological phenomena. Gravner's research has been published in numerous reputable journals, and he has collaborated with various researchers on topics including percolation on hypercubes, the evolution of reproductive isolation, and the modeling of snow crystal growth. His contributions are characterized by a focus on the mathematical underpinnings of growth processes, automata, and percolation, supported by a history of supported research from the National Science Foundation and the Slovenian Ministry of Science.

Research topics

• Algorithm
• Computer Science
• Mathematical analysis
• Mathematics
• Combinatorics
• Theoretical computer science
• Physics
• Discrete mathematics
• Statistics

Selected publications

• Young domination on Hamming rectangles

  ArXiv.org · 2025-01-07

  preprintOpen access1st authorCorresponding

  We introduce a family of domination-type problems in Cartesian products of two graphs. The framework captures several well-studied topics, including variants of bootstrap percolation, line growth, distance domination, and target set selection. We focus on Cartesian products of two complete graphs and formulate the notion of Young domination number in terms of a growth rule determined by a Young diagram; this number is the smallest cardinality of an initial set that covers the entire vertex set in a prescribed number $L$ of iterations of the rule. We compute the Young domination number with $L=1$ for several natural cases, including $k$-domination for Cartesian products of two complete graphs of the same order, thereby proving a conjecture from 2009 due to Burchett, Lane, and Lachniet. We show that the case of $L=1$ of Young domination is equivalent to computing bipartite Turán numbers for families of double stars, yielding implications of our results in extremal graph theory. For arbitrary fixed $L$, we devise constant-factor approximation algorithms for the problem. Our approach is based on a variety of techniques, including duality between Young diagrams, algebraic formulations, explicit constructions, and dynamic programming.

  PublisherOA PDFDOI

• Polluted Modified Bootstrap Percolation

  ArXiv.org · 2025-03-19

  preprintOpen access1st authorCorresponding

  In the polluted modified bootstrap percolation model, sites in the square lattice are independently initially occupied with probability $p$ or closed with probability $q$. A site becomes occupied at a subsequent step if it is not closed and has at least one occupied nearest neighbor in each of the two coordinates. We study the final density of occupied sites when $p$ and $q$ are both small. We show that this density approaches $0$ if $q\ge Cp^2/\log p^{-1}$ and $1$ if $q\le p^2/(\log p^{-1})^{1+o(1)}$. Thus we establish a logarithmic correction in the critical scaling, which is known not to be present in the standard model, settling a conjecture of Gravner and McDonald from 1997.

  PublisherOA PDFDOI

• Two-stage Bootstrap Percolation

  ArXiv.org · 2025-09-20

  preprintOpen access

  We introduce and study two variants of two-stage growth dynamics in $\mathbb{Z}^2$ with state space $\{0,1,2\}^{\mathbb{Z}^2}$. In each variant, vertices in state $0$ can be changed irreversibly to state $1$, and vertices in state $1$ can be changed permanently to state $2$. In the standard variant, a vertex flips from state $i$ to $i+1$ if it has at least two nearest-neighbors in state $i+1$. In the modified variant, a $0$ changes to a $1$ if it has both a north or south neighbor and an east or west neighbor in state $1$, and a $1$ changes to a $2$ if it has at least two nearest-neighbors in state $2$. We assume that the initial configuration is given by a product measure with small probabilities $p$ and $q$ of $1$s and $2$s. For both variants, as $p$ and $q$ tend to $0$, if $q$ is large compared to $p^{2+o(1)}$, then the final density of $0$s tends to $1$. When $q$ is small compared to $p^{2+o(1)}$, for standard variant the final density of $2$s tends to $1$, while for the modified variant the final density of $1$s tends to $1$. In fact, for the modified variant, the final density of $2$s approaches $0$ regardless of the relative size of $q$ versus $p$. These results remain unchanged if, in either variant, a $1$ changes to a $2$ only if it has both a north or south neighbor and an east or west neighbor in state $2$. An essential feature of these dynamics is that they are not monotone in the initial configuration.

  PublisherOA PDFDOI

• Two-dimensional supercritical growth dynamics with one-dimensional nucleation

  The Annals of Applied Probability · 2025-10-01 · 1 citations

  article

  We introduce a class of cellular automata growth models on the two-dimensional integer lattice with finite cross neighborhoods. These dynamics are determined by a Young diagram Z and the radius ρ of the neighborhood, which we assume to be sufficiently large, so that the resulting dynamics are supercritical. A point becomes occupied if the pair of counts of currently occupied points in the horizontal and vertical parts of the cross neighborhood lies outside Z. Starting with a small density p of occupied points, we focus on the first time T at which the origin is occupied. We show that T scales as a power of 1/p, and identify that power, when Z is a triangle, a rectangle, and the union of a finite rectangle with an infinite strip. The case of a triangle corresponds to the classical bootstrap percolation model. We give partial results when Z is a union of two finite rectangles. The distinguishing feature of these dynamics is nucleation of lines that grow to significant length before most of the space is covered.

  PublisherDOI

• Polluted Modified Bootstrap Percolation

  Electronic Communications in Probability · 2025-01-01

  articleOpen access1st authorCorresponding

  In the polluted modified bootstrap percolation model, sites in the square lattice are independently initially occupied with probability p or closed with probability q. A site becomes occupied at a subsequent step if it is not closed and has at least one occupied nearest neighbor in each of the two coordinates. We study the final density of occupied sites when p and q are both small. We show that this density approaches 0 if q≥Cp2∕logp−1 and 1 if q≤p2∕(logp−1)1+o(1). Thus we establish a logarithmic correction in the critical scaling, which is known not to be present in the standard model, settling a conjecture of Gravner and McDonald from 1997.

  PublisherOA PDFDOI

• Competing deterministic growth models in two dimensions

  Electronic Journal of Probability · 2025-01-01

  articleOpen access1st authorCorresponding

  We consider three-state cellular automata in two dimensions in which two colored states, blue and red, compete for control of the empty background, starting from low initial densities p and q. When the growth of each colored type is one-dimensional, the dynamics have three distinct phases characterized by a power relationship between p and q: two in which one of the colors is prevalent, and one when the colored types block each other and leave most of the space forever empty. When one of the colors spreads in two dimensions and the other in one dimension, we also establish a power relation between p and q that characterizes which of the two colors eventually controls most of the space. We use a multiscale construction to show that the one-dimensional growth significantly impedes the two-dimensional growth in the appropriate parameter regime.

  PublisherDOI

• Competing deterministic growth models in two dimensions

  arXiv (Cornell University) · 2024-05-23

  preprintOpen access1st authorCorresponding

  We consider three-state cellular automata in two dimensions in which two colored states, blue and red, compete for control of the empty background, starting from low initial densities $p$ and $q$. When the dynamics of both colored types are one-dimensional, the dynamics has three distinct phases, characterized by a power relationship between $p$ and $q$: two in which one of the colors is prevalent, and one when the colored types block each other and leave most of the space forever empty. When one of the colors spread in two dimensions and the other in one dimension, we also establish a power relation between $p$ and $q$ that characterizes which of the two colors eventually controls most of the space.

  PublisherOA PDFDOI

• Transitive closure in a polluted environment

  The Annals of Applied Probability · 2023-02-01 · 1 citations

  articleOpen access1st authorCorresponding

  We introduce and study a new percolation model, inspired by recent works on jigsaw percolation, graph bootstrap percolation, and percolation in polluted environments. Start with an oriented graph G0 of initially occupied edges on n vertices, and iteratively occupy additional (oriented) edges by transitivity, with the constraint that only open edges in a certain random set can ever be occupied. All other edges are closed, creating a set of obstacles for the spread of occupied edges. When G0 is an unoriented linear graph, and leftward and rightward edges are open independently with possibly different probabilities, we identify three regimes in which the set of eventually occupied edges is either all open edges, the majority of open edges in one direction, or only a very small proportion of all open edges. In the more general setting where G0 is a connected unoriented graph of bounded degree, we show that the transition between sparse and full occupation of open edges occurs when the probability of open edges is (logn)−1/2+o(1). We conclude with several conjectures and open problems.

  PublisherOA PDFDOI

• Two-dimensional supercritical growth dynamics with one-dimensional nucleation

  arXiv (Cornell University) · 2023-05-07

  preprintOpen access

  We introduce a class of cellular automata growth models on the two-dimensional integer lattice with finite cross neighborhoods. These dynamics are determined by a Young diagram $\mathcal Z$ and the radius $ρ$ of the neighborhood, which we assume to be sufficiently large. A point becomes occupied if the pair of counts of currently occupied points on the horizontal and vertical parts of the neighborhood lies outside $\mathcal Z$. Starting with a small density $p$ of occupied points, we focus on the first time $T$ at which the origin is occupied. We show that $T$ scales as a power of $1/p$, and identify that power, when $\mathcal Z$ is the triangular set that gives threshold-$r$ bootstrap percolation, when $\mathcal Z$ is a rectangle, and when it is a union of a finite rectangle and an infinite strip. We give partial results when $\mathcal Z$ is a union of two finite rectangles. The distinguishing feature of these dynamics is nucleation of lines that grow to significant length before most of the space is covered.

  PublisherOA PDFDOI

• Zdravje otrok in mladostnikov / Health of Children and Adolescents

  2022-01-01

  paratextOpen access

  The impact of the environment on the distress and suicidal behaviour of children and adolescents Marjeta Logar ČučekThe influence of Roma women's education regarding their reproductive health on the health of their children Anja Magajna, Barbara Artnik

  PublisherOA PDFDOI

Recent grants

• Monotone and Nonmonotone Growth Models

  NSF · $126k · 2005–2010

• Probabilistic aspects of growth processes

  NSF · $210k · 2008–2012

• Probabilistic approach to cellular automata and related models

  NSF · $153k · 2015–2019

Frequent coauthors

• David Sivakoff

  58 shared

• David Griffeath

  University of Wisconsin–Madison

  45 shared

• Hanbaek Lyu

  University of Wisconsin–Madison

  31 shared

• Matthew Junge

  27 shared

• Michael Damron

  27 shared

• Alexander E. Holroyd

  University of Bristol

  20 shared

• Marcello Potocco

  16 shared

• Aleksandra Brezovec

  University of Primorska

  16 shared