In this paper, we study a bootstrap percolation process on the finite triangular grid $\mathfrak{T}_n$ of side length $n$. We say that a subset $\eta$ of points in $\mathfrak{T}_n$ percolates if the final configuration, starting from $\eta$, is the whole grid $\mathfrak{T}_n$. A basis of size $n$ is then a subset of points of $\mathfrak{T}_n$ 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 $t_n$ of bases of size $n$ exhibits a stretched exponential asymptotic behaviour. More precisely, we show that $t_n \sim c n!e^{\sqrt{12n}}n^{5/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.
In this paper, we study the asymptotic behaviours of a critical branching random walk in $\mathbb{R}^d$ under the assumption that the offspring distribution belongs to the domain of attraction of an $\alpha$-stable law with $\alpha\in(1,2]$, and that the jump distribution has a finite $\frac{2\alpha}{\alpha-1}$-th moment. First, we establish the precise decay rate for the tail probability of the all-time maximal displacement $M^d$. Next, we investigate the maximal displacement $M_n^d$ at generation $n$ and prove a conditional limit theorem for the distribution of $M_n^d$ given that the process survives up to generation $n$. These results extend the corresponding 1-dimensional results of Lalley and Shao (2015) to the case $d\ge2$. Finally, we study the asymptotic behaviour of the total progeny $\zeta$. In particular, we show that, conditioned on the event $\{M^d\ge x\}$, $\zeta$ converges in distribution under an appropriate normalization. This result reveals a quantitative relationship between the maximal displacement and the total progeny size.
We study the diagonal Green function $\widetilde{u}(x)=[L_N^{-1}]_{x,x}$ of the operator $L_N=I-\alpha P$ on the finite torus $(\mathbb{Z}/N\mathbb{Z})^2$, where $P$ is the transfer operator of the discrete cat map $T_N(x)=Ax \bmod N$. We prove the exact formula $\widetilde{u}(x)=(1-\alpha^{k_x})^{-1}$, where $k_x$ is the minimal period of $x$ under $T_N$. This formula appears to be new. It shows that the diagonal landscape is a complete spectral invariant of the orbit structure, depending on each point only through its orbit length. Since $\det(A-I)=-1$ is a unit in $\mathbb{Z}/N\mathbb{Z}$ for every $N\ge2$, the origin is the unique fixed point of $T_N$ and the unique global maximum of $\widetilde{u}$. The resulting localization is driven by arithmetic alone, with no disorder and no broken symmetry, a mechanism distinct from classical Anderson theory and from Filoche--Mayboroda landscape theory. We further establish the Chandra Green--Zeta Identity, showing that the Green trace satisfies $\operatorname{tr}(G_N)=N^2-\alpha\frac{d}{d\alpha}\log Z_N(\alpha)$, where $Z_N$ is the dynamical zeta function of $T_N$, and that a Laplacian perturbation degrades the localization gap at first order in $\varepsilon$. All results are verified computationally.
Given a subset $A \subseteq \mathbb F_2^n$, we can consider the distribution of the intersection size of $A$ with a uniformly random $d$-flat $F$. Motivated by the edge statistics problem and the hypercube statistics problem, the affine subspace statistics problem concerns the maximum of $\mathbb{P}[|F\cap A|=s]$ among $A \subseteq \mathbb F_2^n$ for any fixed $s\in\{1,\dots,2^d\}$ over a uniformly random $d$-flat $F$. We use $\lambda^*(d,s)$ to denote the limit of the maximum when $n$ goes to infinity. In this note, we prove tight bounds for $\lambda^*(d,s)$ in two different regimes. For $s=j2^k$ where $j$ is a positive odd integer, the best known lower bound construction achieving $\lambda^*(d,s)\ge 1-2^{-k}$ is due to taking $A$ as the union of $j$ parallel $(n-d+k)$-flats in $\mathbb F_2^n$. Our main result is a matching upper bound with an additive error term of $O(2^{-3k/2})$. We also study the case $s=1$, where we determine $\lambda^*(d,1)$ exactly. We show that the random construction where each point is included with probability $2^{-d}$ is optimal.
Ting-Wei Chao, Zixuan Xu, D. Zakharov· 0 citations
Let $g_n$ be the largest number of Euclidean balls of diameter $1$ which may be needed to cover a set of diameter $1$ in $\mathbb{R}^n$. We study this problem for finite sets invariant under all coordinate permutations. We prove that the exponential growth rate in this symmetric problem can be characterized exactly as a finite-alphabet squared-error rate-distortion supremum $\alpha_0$. Specialized to the two-point case, i.e., for subsets of Boolean cubes, this gives the explicit lower bound \[g_n\ge (1.160235457\ldots-o(1))^n,\] improving the previous best bound $(2/\sqrt3-o(1))^n$. Using Fix's Gaussian characterization of the rate-distortion problem, we give a numerical three-point construction with exponent base greater than $1.160497831$. Finally, we show that $\alpha_0$ is not attained by any finitely supported distribution.
Andrii Arman, A. Bondarenko, A. Prymak et al.· 0 citations
We determine the sharp asymptotic behavior of the optimal constants in the discrete Hardy-Rellich inequalities on the lattice $\mathbb{Z}^d$. For every fixed integer $m\ge 1$, let ${\mathcal C}_{m,d}$ be the best constant in the $m$-th order Hardy-Rellich inequality. We prove that $$\lim_{d\to\infty}\frac{\mathcal C_{m,d}}{d^m}=2^m.$$ Our approach combines a Fourier reduction to weighted inequalities with the flat torus and general weighted Hardy-Rellich identities of first and second order. A key novelty is the use of probabilistic concentration estimates, specifically Hoeffding's inequality and entropy methods, to handle estimates involving the anisotropic weight $\omega^\gamma$ $(\gamma\geq 1)$ where $$\omega(x)=\sum_{j=1}^{d} \Big(\sin\frac{x_j}{2}\Big)^2$$ in a dimension-uniform manner. These tools yield asymptotically sharp weighted estimates on the torus, from which the lattice inequalities follow by iteration.
Let $\mathrm{Sym(n,k)}$ denote the set of permutations on $\{1,2,\ldots,n\}$ with exactly $k$ cycles. A family $\mathcal{F}\subset\mathrm{Sym}(n,k)$ is said to be intersecting if $\sigma^{-1}\tau$ has a fixed point for all $\sigma,\tau\in\mathcal{F}$. In this paper, we investigate the size and structure of maximum-sized intersecting families of permutations in $\mathrm{Sym}(n,k)$. In the regime $k\leq n^{0.25}$, we show that every maximum-sized intersecting family is a star, meaning it consists of all permutations in $\mathrm{Sym}(n,k)$ that agree at a given point in $[n]$. We establish this result by proving a stronger stability result that bounds the maximum possible size of a non-centred intersecting family. Specifically, in the regime $k\leq n^{0.25}$, the size of any non-centred intersecting family is at most $\left(2/3+o(1)\right)$ times the maximum possible size of a star. In the tighter polylogarithmic regime $k\leq (\ln n)^{d}$, we improve this bound to $\left(1-1/e+o(1)\right)$ times the maximum possible size of a star; we show that this bound is asymptotically sharp. Thus, we establish both an Erd\H{o}s--Ko--Rado theorem and its corresponding stability version for $\mathrm{Sym}(n,k)$.
