arXiv daily

Combinatorics (math.CO)

Fri, 21 Apr 2023

Other arXiv digests in this category:Thu, 14 Sep 2023; Wed, 13 Sep 2023; Tue, 12 Sep 2023; Mon, 11 Sep 2023; Fri, 08 Sep 2023; Tue, 05 Sep 2023; Fri, 01 Sep 2023; Thu, 31 Aug 2023; Wed, 30 Aug 2023; Tue, 29 Aug 2023; Mon, 28 Aug 2023; Fri, 25 Aug 2023; Thu, 24 Aug 2023; Wed, 23 Aug 2023; Tue, 22 Aug 2023; Mon, 21 Aug 2023; Fri, 18 Aug 2023; Thu, 17 Aug 2023; Wed, 16 Aug 2023; Tue, 15 Aug 2023; Mon, 14 Aug 2023; Fri, 11 Aug 2023; Thu, 10 Aug 2023; Wed, 09 Aug 2023; Tue, 08 Aug 2023; Mon, 07 Aug 2023; Fri, 04 Aug 2023; Thu, 03 Aug 2023; Wed, 02 Aug 2023; Tue, 01 Aug 2023; Mon, 31 Jul 2023; Fri, 28 Jul 2023; Thu, 27 Jul 2023; Wed, 26 Jul 2023; Tue, 25 Jul 2023; Mon, 24 Jul 2023; Fri, 21 Jul 2023; Thu, 20 Jul 2023; Wed, 19 Jul 2023; Tue, 18 Jul 2023; Mon, 17 Jul 2023; Fri, 14 Jul 2023; Thu, 13 Jul 2023; Wed, 12 Jul 2023; Tue, 11 Jul 2023; Mon, 10 Jul 2023; Fri, 07 Jul 2023; Thu, 06 Jul 2023; Wed, 05 Jul 2023; Tue, 04 Jul 2023; Mon, 03 Jul 2023; Fri, 30 Jun 2023; Thu, 29 Jun 2023; Wed, 28 Jun 2023; Tue, 27 Jun 2023; Mon, 26 Jun 2023; Fri, 23 Jun 2023; Thu, 22 Jun 2023; Wed, 21 Jun 2023; Tue, 20 Jun 2023; Fri, 16 Jun 2023; Thu, 15 Jun 2023; Tue, 13 Jun 2023; Mon, 12 Jun 2023; Fri, 09 Jun 2023; Thu, 08 Jun 2023; Wed, 07 Jun 2023; Tue, 06 Jun 2023; Mon, 05 Jun 2023; Fri, 02 Jun 2023; Thu, 01 Jun 2023; Wed, 31 May 2023; Tue, 30 May 2023; Mon, 29 May 2023; Fri, 26 May 2023; Thu, 25 May 2023; Wed, 24 May 2023; Tue, 23 May 2023; Mon, 22 May 2023; Fri, 19 May 2023; Thu, 18 May 2023; Wed, 17 May 2023; Tue, 16 May 2023; Mon, 15 May 2023; Fri, 12 May 2023; Thu, 11 May 2023; Wed, 10 May 2023; Tue, 09 May 2023; Mon, 08 May 2023; Fri, 05 May 2023; Thu, 04 May 2023; Wed, 03 May 2023; Tue, 02 May 2023; Mon, 01 May 2023; Fri, 28 Apr 2023; Thu, 27 Apr 2023; Wed, 26 Apr 2023; Tue, 25 Apr 2023; Mon, 24 Apr 2023; Thu, 20 Apr 2023; Wed, 19 Apr 2023; Tue, 18 Apr 2023; Mon, 17 Apr 2023; Fri, 14 Apr 2023; Thu, 13 Apr 2023; Wed, 12 Apr 2023; Tue, 11 Apr 2023; Mon, 10 Apr 2023
1.Multidimensional polynomial patterns over finite fields: bounds, counting estimates and Gowers norm control

Authors:Borys Kuca

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.

00:00
00:00
00:00
2.On uniquely packable trees

Authors:A. Alochukwu, M. Dorfling, E. Jonck

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

00:00
00:00
00:00
3.Pinned-base simplex, a Furstenberg type problem, and incidences in finite vector spaces

Authors:Thang Pham

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 Fq2\mathbb{F}_q^2. More precisely, for A,B,CFq2A, B, C\subset \mathbb{F}_q^2, if ABC1/2q4|A||B||C|^{1/2}\gg q^4, then for any λFq{0}\lambda\in \mathbb{F}_q\setminus \{0\}, the number of congruence classes of triangles with vertices in A×B×CA\times B\times C and one side-length λ\lambda is at least q2\gg q^2. As a consequence, the number of congruence classes of triangles with vertices in A×B×CA\times B\times C is at least q3\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 kk-rich rigid motions in studying the distribution of simplex. A number of related questions will be also addressed in this paper.

00:00
00:00
00:00
4.Austrian Solitaire

Authors:Philip Mummert

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.

00:00
00:00
00:00
5.Local dimer dynamics in higher dimensions

Authors:Ivailo Hartarsky, Lyuben Lichev, Fabio Toninelli

Abstract: We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes [n]d[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[n]^d features order nd2n^{d-2} alternating cycles of length at most 4d24d-2. We also prove that the dynamics of dimer configurations on the unit hypercube of dimension dd is ergodic when switching alternating cycles of length at most 4d44d-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.

00:00
00:00
00:00