Combinatorics (math.CO)

Abstract: We examine multidimensional polynomial progressions involving linearly independent polynomials in finite fields, proving power saving bounds for sets lacking such configurations. This jointly generalises earlier results of Peluse (for the single dimensional case) and the author (for distinct degree polynomials). In contrast to the cases studied in the aforementioned two papers, a usual PET induction argument does not give Gowers norm control over multidimensional progressions that involve polynomials of the same degrees. The main challenge is therefore to obtain Gowers norm control, and we accomplish this for all multidimensional polynomial progressions with pairwise independent polynomials. The key inputs are: (1) a quantitative version of a PET induction scheme developed in ergodic theory by Donoso, Koutsogiannis, Ferr\'e-Moragues and Sun, (2) a quantitative concatenation result for Gowers box norms in arbitrary finite abelian groups, motivated by earlier results of Tao, Ziegler, Peluse and Prendiville; (3) an adaptation to combinatorics of the box norm smoothing technique, recently developed in the ergodic setting by the author and Frantzikinakis; and (4) a new version of the multidimensional degree lowering argument.

Abstract: An $i$-packing in a graph $G$ is a set of vertices that are pairwise distance more than $i$ apart. A \emph{packing colouring} of $G$ is a partition $X=\{X_{1},X_{2},\ldots,X_{k}\}$ of $V(G)$ such that each colour class $X_{i}$ is an $i$-packing. The minimum order $k$ of a packing colouring is called the packing chromatic number of $G$, denoted by $\chi_{\rho}(G)$. In this paper we investigate the existence of trees $T$ for which there is only one packing colouring using $\chi_\rho(T)$ colours. For the case $\chi_\rho(T)=3$, we completely characterise all such trees. As a by-product we obtain sets of uniquely $3$-$\chi_\rho$-packable trees with monotone $\chi_{\rho}$-coloring and non-monotone $\chi_{\rho}$-coloring respectively.

Abstract: In this paper we prove a sharp condition to guarantee of having a positive proportion of all congruence classes of triangles in given sets in $\mathbb{F}_q^2$. More precisely, for $A, B, C\subset \mathbb{F}_q^2$, if $|A||B||C|^{1/2}\gg q^4$, then for any $\lambda\in \mathbb{F}_q\setminus \{0\}$, the number of congruence classes of triangles with vertices in $A\times B\times C$ and one side-length $\lambda$ is at least $\gg q^2$. As a consequence, the number of congruence classes of triangles with vertices in $A\times B\times C$ is at least $\gg q^3$. The main ingredients in our proof are a recent incidence bound between points and rigid motions due to the author and Semin Yoo (2023) and a result on a Furstenberg type problem. When three sets are the same, we give a unified and new proof for all the best current results due to Bennett, Hart, Iosevich, Pakianathan, and Rudnev (2017) and McDonald (2020). The novelty of this approach is to present an application of results on the number of $k$-rich rigid motions in studying the distribution of simplex. A number of related questions will be also addressed in this paper.

Abstract: Austrian Solitaire is a variation of Bulgarian Solitaire. It may be described as a card game, a method of asset inventory management, or a discrete dynamical system on integer partitions. We prove that the limit cycles in Austrian Solitaire do not depend on the initial configuration. We show that a full Farey sequence completely characterizes these unique (and balanced) cycles.

Abstract: We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes $[n]^d$. These consist of successively switching the dimers along alternating cycles of prescribed (small) lengths. We study the connectivity properties of the dimer configuration space equipped with these transitions. Answering a question of Freire, Klivans, Milet and Saldanha, we show that in three dimensions any configuration admits an alternating cycle of length at most 6. We further establish that any configuration on $[n]^d$ features order $n^{d-2}$ alternating cycles of length at most $4d-2$. We also prove that the dynamics of dimer configurations on the unit hypercube of dimension $d$ is ergodic when switching alternating cycles of length at most $4d-4$. Finally, in the planar but non-bipartite case, we show that parallelogram-shaped boxes in the triangular lattice are ergodic for switching alternating cycles of lengths 4 and 6 only, thus improving a result of Kenyon and R\'emila, which also uses 8-cycles. None of our proofs make reference to height functions.