Combinatorics
See recent articles
Showing new listings for Monday, 29 June 2026
- [1] arXiv:2606.27451 [pdf, html, other]
-
Title: Totally Disjoint Diametral PathsSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
In this paper, we study totally disjoint diametral paths in simple connected graphs. A diametral path in a graph is a shortest path that connects two vertices whose mutual distance is equal to the diameter of the graph. Totally disjoint paths are paths that have no vertices in common, including their end vertices. We show that the problem of deciding whether a graph $G$ has $k$ totally disjoint diametral paths is NP-complete. We consider restricted classes of graphs for which the problem of determining the maximum size of a set of totally disjoint diametral paths is readily solved. We then give a linear-time algorithm for a subclass of maximal outerplanar graphs called 2-paths, define a polynomial-time algorithm for threshold graphs, and establish a structural bound for proper interval graphs. Finally, we define classes of extremal graphs with $k$ totally disjoint diametral paths of length $d$ having the fewest possible number of edges.
- [2] arXiv:2606.27497 [pdf, html, other]
-
Title: Enumerating matrices with prescribed entries in an adjoint orbitComments: 29 pagesSubjects: Combinatorics (math.CO); Algebraic Geometry (math.AG); Representation Theory (math.RT)
We study intersections of conjugacy classes of square matrices over a finite field with affine coordinate subspaces, or equivalently matrices in a fixed adjoint orbit with prescribed entries. Our main result treats the case of prescribed columns: for a partially defined linear map we give a Hall scalar product formula for the number of extensions to an endomorphism with prescribed similarity invariants. This formula is expressed in terms of skew modified Hall--Littlewood functions and $q$-Whittaker functions. As applications, we count monic matrix polynomials over $\mathbb{F}_q$ with prescribed Smith normal form and with prescribed determinant, and recover the Gerstenhaber--Reiner formula for the number of square matrices with a fixed characteristic polynomial. We also note that known point-count formulas for Hessenberg varieties imply related formulas for Hessenberg supports involving chromatic quasisymmetric functions, motivating polynomiality questions for more general supports and prescribed affine slices.
- [3] arXiv:2606.27503 [pdf, html, other]
-
Title: Tropical Fermat--Weber Problems over Non-Finite Data and their Inverse FormulationsSubjects: Combinatorics (math.CO); Optimization and Control (math.OC)
The term tropical pseudonorm refers to a family of (not necessarily symmetric) gauge functions that arise in tropical or idempotent geometry. An important characteristic of these gauges is their invariance under translation by a constant vector, allowing them to descent naturally to tropical projective spaces. In this work, we explore the tropical one-infinity pseudonorm, a polyhedral hybrid gauge that allows for tunable asymmetry, in the context of a Fermat--Weber location problem. We extend previous formulations in considering non-finite data, and we investigate several variants of the inverse problem, providing linear programming formulations for their solution.
- [4] arXiv:2606.27507 [pdf, html, other]
-
Title: A combinatorial proof for the positivity of the normalized Jacobi triple product tailsSubjects: Combinatorics (math.CO)
For $k\geq 1$, we prove that \[ [q^n z^s]J_k(z,q)\geq 0, \qquad (n\geq 0,\ s\in\mathbb Z) \] for the normalized Jacobi triple product tails \[ J_k(z,q) = \frac{ \sum_{j=k}^{\infty}(-1)^{j-k} q^{\binom{j+1}{2}}(z^{-j}+\cdots+z^j)} {(zq,q/z;q)_\infty}. \] This result not only implies Merca's stronger nonnegativity conjecture on truncated Jacobi triple product series in full generality, but also yields infinite families of linear inequalities for two-colored partitions and partitions with parts in the residue classes $\pm S \pmod{R}$. We present a combinatorial proof wherein a sign-reversing involution reduces the normalized Jacobi triple product tails to the invariant subsets according to the generalized minimal-excludant of partitions. Furthermore, by combing an invertible lift operator on Frobenius arms with Konan's size- and length-preserving bijection, an injection is constructed between the consecutive invariant subsets, which implies the coefficientwise positivity of the normalized Jacobi triple product tails.
- [5] arXiv:2606.27519 [pdf, html, other]
-
Title: Class-uniformly resolvable designs with all but one block having size twoSubjects: Combinatorics (math.CO)
A Class-Uniformly Resolvable Design (CURD) is a resolvable design in which each parallel class has the same block structure. We study CURDS in which each parallel class contains one block of size $m$ and the remaining blocks have size $2$, for $m \ge 3$. In addition to establishing necessary conditions for such a CURD to exist, we present two general constructions. The first transforms a particular type of cyclic design with block size $k$ into a CURD with partition $m^12^{\frac{n-m}{2}}$ where $m = 2k$. This construction is used to generate CURDS with 26 varieties (where $m=6$) and with 82 varieties (where $m=10$). The second constructs a CURD with partition $m^12^{\frac{n-m}{2}}$ for every value of $m$ that is the power of an odd prime.
- [6] arXiv:2606.27523 [pdf, html, other]
-
Title: Coordinate projections of $c$-vectors of cluster algebras from the annulusComments: 17 pages, 1 figure. Ancillary files: exact-integer Python verification code reproducing the computational classificationSubjects: Combinatorics (math.CO); Rings and Algebras (math.RA); Representation Theory (math.RT)
For an acyclic cluster algebra, the $c$-vectors are, up to sign, the real
Schur roots of the associated root system. We study the two-coordinate
projections $(c_v, c_w)$ of this configuration: when the difference
$c_v - c_w$ is bounded the image lies in a band of lattice lines, and we ask
when the projection fills that band. A band-existence dichotomy, valid in
every acyclic type, shows the difference is bounded if and only if the null
root satisfies $\delta_v = \delta_w$. For affine type $\widetilde{A}_n$ (the
annulus), in the source-sink orientation, we resolve the filling question
completely: every coordinate projection fills its band except along the
source-sink diagonal, which carries only the finite regular part. The
obstruction is the Auslander--Reiten defect, which a projection sees on its
diagonal exactly when the defect is a coordinate difference; the only such
pair is the source-sink pair of $\widetilde{A}_n$, so the pattern depends on
the chosen seed. More generally, every banded pair of null-root coefficient
one fills, except these diagonals. Off the diagonal a banded pair in
$\widetilde{E}_7$ fails to fill, so non-filling is not confined to type
$\widetilde{A}_n$; a computation classifies the pairs of coefficient at least
two over a range of affine types, where this $\widetilde{E}_7$ pair is the
only further failure, and the general classification remains open. - [7] arXiv:2606.27682 [pdf, html, other]
-
Title: Linkage problem on optimal $1$-planar graphsSubjects: Combinatorics (math.CO)
Enami and Maezawa give a complete characterization of $(s_1, s_2, \ldots, s_k)$-linked planar graphs for any $k$-tuple of positive integers. In this paper, we investigate linkage problems for optimal 1-planar graphs. In particular, we show that every optimal 1-planar graph with connectivity $6$ is $(5, 5)$-linked. Moreover, for an optimal $1$-planar graph $G$ that is not $(2,2,1)$-linked, we characterize disjoint vertex subsets $S_1, S_2, S_3$ in $G$ with $|S_1|=|S_2|=2$ and $|S_3|=1$ such that $G$ is not $\{S_1,S_2,S_3\}$-linked.
- [8] arXiv:2606.27703 [pdf, html, other]
-
Title: Another proof of the result on rotation compatible planar coversSubjects: Combinatorics (math.CO)
Negami's Planar Cover Conjecture asserts that a connected graph has a finite planar cover if and only if it can be embedded on the projective plane. While this statement has already been proven for rotation compatible planar covers, namely covers equipped with a certain condition on the rotation system, the existing proof relies on advanced algebraic and topological methods. In this paper, we provide another proof of this result, focusing primarily on combinatorial arguments based on a structural analysis with respect to a spanning tree in the base graph.
- [9] arXiv:2606.27758 [pdf, html, other]
-
Title: The Existence of Diagonal Quantum Latin Squares with Maximum CardinalitySubjects: Combinatorics (math.CO)
A quantum Latin square of order \(n\), denoted by \(\operatorname{QLS}(n)\), is an \(n \times n\) square whose entries are unit column vectors in the \(n\)-dimensional Hilbert space \(\mathcal{H}_n\), such that each row and each column forms an orthonormal basis of \(\mathcal{H}_n\). The cardinality of a QLS($n$) is the number of distinct vectors up to a global phase in the array. A \(\mathrm{QLS}(n)\) whose main diagonal and anti-diagonal each forms an orthonormal basis of \(\mathcal{H}_n\) is called a diagonal quantum Latin square (\(\mathrm{DQLS}(n)\)). In this paper, we focus on the existence of the \(\mathrm{DQLS}(n)\) with maximum cardinality ($\mathrm{MCDQLS}(n)$). By employing direct constructions based on row-quantum Latin rectangle and special complete mapping, together with the recursive techniques such as the singular direct product construction, We have almost completely determined the existence of \(\mathrm{MCDQLS}(n)\), except for a few exceptional cases. This result is based on the study of the existence of idempotent \(\mathrm{QLS}(n)\) with maximum cardinality (\(\mathrm{MCQLS}(n)\)), and implies an existence result for pandiagonal quantum Latin squares with maximum cardinality (\(\mathrm{MCPQLS}(n)\)).
- [10] arXiv:2606.27763 [pdf, html, other]
-
Title: Unimodular matrices and lattice paths enumeration via Pascal's triangleComments: 10 pages, 4 figuresJournal-ref: Communications in Combinatorics and Optimization, 2026Subjects: Combinatorics (math.CO)
This article investigates a remarkable combinatorial identity involving a distinguished family of matrices whose entries are defined via binomial coefficients. Specifically, we consider a class of \( n \times n \) matrices parameterized by a positive integer \( m \), where each entry reflects a structured pattern derived from Pascal's triangle, particularly the diagonals corresponding to figurate numbers such as triangular, tetrahedral, and higher-dimensional simplex numbers. We establish, by means of a bijective argument, that the determinant of any such matrix is identically equal to \( 1 \), independent of the specific values of \( m \) and \( n \), provided that \( 2 \leq m \leq n \). This result unveils a profound connection between classical binomial identities and the enumeration of lattice paths in grid graphs.
- [11] arXiv:2606.27987 [pdf, html, other]
-
Title: Maniplexes as a Foundation for Cross-Linked Databases of Symmetric ObjectsComments: Submitted (pre-peer-review) version. Accepted at CICM 2026; the Version of Record will appear in Springer LNAI. We'll add the DOI once the proceedings are publishedSubjects: Combinatorics (math.CO)
Graphs, maps on surfaces, and abstract polytopes are related combinatorial structures that tend to be studied by different communities using their own tools and databases. Maniplexes provide a unifying framework that captures all of them. A single database built around maniplexes would help researchers recognize shared structures and translate results across fields. Here we present a compact, interoperable format for storing maniplexes as edge-labeled graphs, designed with such a database in mind. As a first step, we connect two existing datasets of regular 4-maniplexes to the House of Graphs and to Potočnik's tetravalent graph censuses, using canonical forms of their flag graphs, 1-skeleton graphs, and 1-coskeleton graphs.
- [12] arXiv:2606.28041 [pdf, html, other]
-
Title: The Erdos n^2/25 max-cut conjecture for small multiples of five, via a per-root-MaxCut envelope and blow-up integralityComments: 9 pages. Computer-assisted. Ancillary files: order-10 per-root-MaxCut + rooted-Horn flag-algebra certificate with an independent exact-arithmetic verifier, a self-contained brute-force max-cut ground-truth checker, and the manifestly-PSD moment Gram certificateSubjects: Combinatorics (math.CO)
Erdős conjectured that every triangle-free graph on $N$ vertices can be made bipartite by deleting at most $N^2/25$ edges; the bound would be sharp, attained by the balanced blow-up $C_5[N/5]$. Writing $\beta(G)$ for the minimum number of edges whose deletion makes $G$ bipartite and $a(N) = \max\{\beta(G):G$ triangle-free on $N$ vertices$\}$, the conjecture is $a(N)\le N^2/25$, and for $N=5n$ it reads $a(5n)\le n^2$. Balogh, Clemen and Lidícký proved it for large $N$ in the two density tails (edge density at most $0.2486$ or at least $0.3197$) and proved the global bound $a(N)\le N^2/23.5$; the medium-density band remains open. We prove \[ a(5n) = n^2 \qquad \text{for every } 1 \le n \le 40, \quad \text{i.e. } N \in \{5,10,\dots,200\}. \] The proof is computer-assisted and combines three ingredients. (i) A \emph{per-root-MaxCut envelope}: for the $107$ triangle-free $7$-root types, the mean over types of the best per-type cut is an upper bound $d_{\rm mono}(W)\le U_7(W)$ that is \emph{tight} at the $C_5$-blow-up. (ii) An order-$10$ flag-algebra certificate -- the per-root-MaxCut rows at $7$ and $8$ roots together with rooted-Horn cuts and a manifestly-PSD moment block -- bounds the envelope on the medium band, $U_7(W)\le \tfrac{2}{25}+\delta$ with an explicit rational $\delta\approx 4.8558\times10^{-5}$, for every triangle-free graphon $W$ of edge density in $[0.2486,0.3197]$. (iii) The blow-up identity $\beta(G[t])=t^2\beta(G)$ plus integrality of $\beta$ turns this into $\beta(G)\le n^2+\tfrac{25}{2}n^2\delta$ for any $5n$-vertex band-density $G$, and $\tfrac{25}{2}n^2\delta<1$ for $n\le 40$; the two density tails are handled by the Balogh-Clemen-Lidícký bounds, transferred to finite $N$ by the same blow-up. The envelope bound $d_{\rm mono} \le U_7$ is a genuine graphon upper bound (each per-root rule is one global $2$-colouring), the certificate is verified in exact rational arithmetic, the moment positivity is Razborov's flag-algebra theorem exhibited as an exact Gram factorization, and the bound is cross-checked against brute-force max-cut on all triangle-free graphs of order at most $12$. The same envelope at orders $9$ and $10$ provably does not reach the constant needed for larger $n$; we explain why, and locate the all-$n$ conjecture at a single self-tight obstruction.
- [13] arXiv:2606.28047 [pdf, html, other]
-
Title: A combinatorial nerve theoremComments: 24 pagesSubjects: Combinatorics (math.CO)
The celebrated (homological) nerve theorem makes use of spectral sequences to determine the homology of a space. However, this theorem cannot effectively compute the homology in every circumstance. In this paper, we develop an effective version of the nerve theorem. Our theorem enables us to compute the homology of a simplicial complex explicitly using the combinatorial information of its subcomplexes and their non-trivial intersections using discrete Morse theory.
Suppose $X$ is a simplicial complex with subcomplexes $A_1, A_2, \dots ,A_k$ such that $X= \cup_{i=1}^{k}A_i$. Then the main theorem of this paper states that we can explicitly compute the homology of $X$ using the information of given gradient vector fields on $A_i$ for each $i \in [k]$, and on their possible non-trivial intersections. Our approach is purely combinatorial, in the sense that it does not involve any notions of geometric realization, continuity or homotopy. - [14] arXiv:2606.28108 [pdf, html, other]
-
Title: Mixed Products of Modified Greaves--Jing--Zhu OperatorsSubjects: Combinatorics (math.CO)
Let $\mathcal Y(z;t)$ be the modified Greaves--Jing--Zhu operator on the odd power-sum ring. We first point out that this operator can be obtained from the classical neutral operator by a simple diagonal change of variables. We then study products in which the two deformation parameters are not necessarily the same. For two parameters $t$ and $s$, we compute the scalar factor that appears in the mixed product. This factor has an explicit exponential form and, in a completed setting, can also be written as a quotient of infinite $t$-Pochhammer products. We also give a recurrence for its coefficients, a product formula for several mixed operators, and formulas for the coefficients obtained after applying the operators to $\mathbf 1$.
A particularly simple case occurs when $s=t^M$. In this case the scalar factor becomes the finite quotient $(u;t)_M/(-u;t)_M$. Its coefficients are signed principal specializations of one-row Schur $Q$-functions. As a result, after removing the signs, these coefficients are nonnegative palindromic polynomials. We also give a Gaussian-binomial formula and a finite-order recurrence. - [15] arXiv:2606.28121 [pdf, html, other]
-
Title: The Signless Laplacian Spectral Radius of $tK_3$-Free GraphsComments: 16 pagesSubjects: Combinatorics (math.CO)
The signless Laplacian matrix of a graph $G$ is $Q(G)=D(G)+A(G)$, where $D(G)$ and $A(G)$ are the diagonal degree matrix and the adjacency matrix of $G$, respectively. The signless Laplacian spectral radius of $G$ is the largest eigenvalue of $Q(G)$. For a positive integer $t$, a graph is called $tK_3$-free if it contains no $t$ vertex-disjoint triangles. In this paper, for every fixed $t\geq 2$ and all $n\geq 28t-17$, we determine the unique graph achieving the maximum signless Laplacian spectral radius among all $tK_3$-free graphs of order $n$.
- [16] arXiv:2606.28157 [pdf, html, other]
-
Title: A unit-distance graph in the plane with independence ratio below 1/4Subjects: Combinatorics (math.CO)
We prove that there exists a finite unit-distance graph in the plane with independence ratio strictly smaller than 1/4, answering a question of Erdős. Our proof closely follows the framework of Matolcsi, Ruzsa, Varga, and Zsámboki, based on the geometric fractional chromatic number, but adds a carefully chosen two-vertex augmentation that pushes their 27-vertex construction from geometric fractional chromatic number $4$ to a value strictly larger than 4. This disproves their Conjecture 1, and implies that the fractional chromatic number of the plane is strictly larger than 4. The proof can be made fully constructive, but the resulting finite graph has an enormous number of vertices.
- [17] arXiv:2606.28162 [pdf, html, other]
-
Title: All limit points of the largest roots of matching polynomials are determinedSubjects: Combinatorics (math.CO)
The largest matching root $\mu(G)$ of a graph $G$ is that of its matching polynomial. In this paper, all limit points of the largest matching roots of graphs are determined. More precisely, we identify the limit points of the largest matching roots of graphs less than $\tau^{\frac{1}{2}}+\tau^{-\frac{1}{2}}$. For any $\gamma \geq \tau^{\frac{1}{2}}+\tau^{-\frac{1}{2}}$ with $\tau=\frac{\sqrt{5}+1}{2}$, there exists a graph sequence $\{G_i\, |\, i\in \mathbb{N}\}$ such that $\lim\limits_{i \rightarrow \infty}\mu(G_i)=\gamma$.
- [18] arXiv:2606.28198 [pdf, html, other]
-
Title: Extremal graphs with no subgraph admitting $k+1$ edge-disjoint spanning treesSubjects: Combinatorics (math.CO)
A graph $G$ is $\tau_k$-maximal if $G$ contains no subgraph admitting $k+1$ edge-disjoint spanning trees, while the addition of any edge in the complement of $G$ yields a subgraph that admits $k+1$ edge-disjoint spanning trees. In this paper, we prove that for any integers $k\geq 1$ and $n\geq 2k+2$, every $\tau_k$-maximal graph of order $n$ satisfies $|E(G)|\leq (k+1)(n-1)-1$. Furthermore, we construct a family of $\tau_k$-maximal graphs on $n\ge 2k+2$ vertices that have exactly $(k+1)(n-1)-1$ edges, which establishes the tightness of the upper bound. Then we conjecture that every $\tau_k$-maximal graph on $n$ vertices has exactly $(k+1)(n-1)-1$ edges, and we verify the conjecture for the case $k=1$.
- [19] arXiv:2606.28216 [pdf, html, other]
-
Title: Fano Geometry and Slow Coupon CollectingComments: 13 pages, 3 tablesSubjects: Combinatorics (math.CO); Probability (math.PR)
We study the coupon collector's problem in a generalized setting where each draw reveals a fixed number of coupons and the sampling mechanism is required to be \emph{fair}, meaning that every coupon appears with the same frequency among the admissible draws. Grunbaum and Yaakobi conjectured that, among all fair mechanisms with fixed parameters, the fully random model maximizes the expected time to complete coverage. We disprove this conjecture by exhibiting explicit counterexamples arising from finite geometry. In particular, we show that the line set of the Fano plane yields a fair mechanism whose expected coverage time exceeds that of the full model. Further exact and computational results are obtained for projective planes of higher order. In addition, we analyze a simple infinite family of fair mechanisms, the star mechanism, for which the expected coverage time admits a closed form. Depending on the scaling regime, this mechanism can be asymptotically slower or faster than the full model, showing that no universal extremality principle holds for fair mechanisms without additional structural assumptions.
- [20] arXiv:2606.28231 [pdf, html, other]
-
Title: Minimum Size of a Poset Realizing $\Z_{2}\times\Z_{2^{n}}$ as its Automorphism GroupSubjects: Combinatorics (math.CO)
We study the realization of finite groups as automorphism groups of finite posets. Given a finite group $G$, let $\beta(G)$ denote the smallest number of elements in a poset $P$ with $\Aut(P)\cong G$. While $\beta(G)$ is known for several cyclic and small abelian groups, the non-cyclic abelian case is largely open. In this paper we prove that $\beta(\Z_{2}\times\Z_{2^{n}})=2^{\,n+1}+2$ for every $n\ge 3$.
- [21] arXiv:2606.28305 [pdf, html, other]
-
Title: Divisible Arm Lengths, Crystal Reflections, and Enumeration of Newly Found Decomposition ColumnsSubjects: Combinatorics (math.CO)
In recent work the authors determine complete columns of symmetric-group decomposition matrices in odd prime characteristic $p$ labeled by $p$-regular partitions for which every hook of length divisible by $p$ has even arm length. In the present paper we enumerate these partitions and prove that each block of $p$-weight $w$ contains precisely \[ \binom{w+\frac{p-3}{2}}{w} \] such partitions.
More generally, for any integers $d,e>1$, we study and enumerate $d$-balanced $e$-regular partitions -- partitions for which every hook of length divisible by $e$ has arm length divisible by $d$. Our first main result is that the crystal (affine) reflections preserve the $d$-balanced property for all $d,e > 1$. It follows that, for fixed $d$, $e$, and $w$, the number of $d$-balanced $e$-regular partitions in a block of $e$-weight $w$ is independent of the $e$-core. We then compute this number by working in RoCK blocks, obtaining an explicit binomial formula valid for every block.
We also investigate closely related odd sequences of partitions. Among others, we find the generating function of the number of odd sequences occurring in a block. Alongside their representation-theoretic relevance, we expect these results to be of independent combinatorial interest.
New submissions (showing 21 of 21 entries)
- [22] arXiv:2606.27501 (cross-list from cs.CG) [pdf, html, other]
-
Title: Unbent collections of non-planar $s$-grid-drawingComments: To appear at CCCG 2026Subjects: Computational Geometry (cs.CG); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
In a recent paper, Antić et al.~studied collections of planar orthogonal drawings of a graph where every edge is unbent in at least one drawing. This paper generalizes this concept to non-planar drawings, and shows that then two drawings always suffice (for planar drawings three drawings are sometimes needed). The results can also be generalized to $s$-grid drawings for $s\geq 3$.
- [23] arXiv:2606.27702 (cross-list from math.NT) [pdf, html, other]
-
Title: Separable integer partition classes and Slater's list -- IIComments: 17 pages, 1 table. Submitted for publicationSubjects: Number Theory (math.NT); Combinatorics (math.CO)
Slater's list of Rogers-Ramanujan type identities remains a central source of striking series-product formulas in the theory of partitions and basic hypergeometric series. Although many of these identities admit elegant analytic proofs through Bailey pairs, Bailey chains, or transformations of basic hypergeometric series, the partition-theoretic meaning of their series sides is often much less apparent. In this paper, which continues the program initiated in arXiv:2603.14179, we apply Andrews' theory of separable integer partition classes to further identities from Slater's list. We construct a strict overpartition class and two families of overpartitions with positional gap conditions, in which overlining is permitted only at alternating positions. Their multivariate generating functions give natural refinements of the series sides of Slater's identities (12), (28), (29), (47), (48), (50), and (51). We then use Heine-type transformations, a limiting form of Heine's transformations, Watson's $q$-analogue of Whipple's theorem, and classical theta-product identities to obtain alternative series representations and recover the associated products. In addition, we derive a new companion identity to a Slater identity and a signed companion formula. Our results further demonstrate that SIP classes provide a flexible framework for converting basic hypergeometric series into structured partition generating functions, while simultaneously producing refinements, transformations, and new Rogers-Ramanujan type identities.
- [24] arXiv:2606.27844 (cross-list from math.PR) [pdf, html, other]
-
Title: Critical percolation on preferential attachment graphs with infinite varianceComments: 35 pagesSubjects: Probability (math.PR); Combinatorics (math.CO)
We study the inhomogeneous random graph with preferential attachment kernel and degree distribution with power-law exponent $\tau\in(2,3)$ as a representative of the class of graphs of preferential attachment type with infinite variance degrees. Under bond percolation with a positive retention probability independent of the size $n$ of the graph there is a unique macroscopic component with high probability. We therefore investigate percolation probabilities $p_n\downarrow0$. We identify a moving critical window at $p_c \sim \beta n^{(\tau-3)/(2\tau-2)}$. Above this window, when $p_n \gg p_c$, the maximal component has size of order $n p^{_{(\tau-1)/(3-\tau)}}_{_n}$ and it is unique. Below this window, when $n^{1/(1-\tau)} \ll p_n \ll p_c$, it is non-unique, star-shaped and has size of order $n^{1/(\tau-1)} p_n$. In the critical window itself, the largest component scaled by $\sqrt{n}$ converges in distribution to a positive random variable with a law given in terms of a subcritical Norros-Reittu graph. This behaviour is markedly different from that seen for other classes of scale-free graphs and is conjectured to persist throughout the broad class of growing graphs with infinite variance.
- [25] arXiv:2606.27961 (cross-list from math.NT) [pdf, html, other]
-
Title: Transversal Difference Numbers in Finite Abelian QuotientsComments: 27 pages, comments welcomeSubjects: Number Theory (math.NT); Cryptography and Security (cs.CR); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
Given \(H\leq G\) finite abelian groups, a transversal \(T\subseteq G\) for \(G/H\) has fixed size \(|G/H|\), but its ambient difference support \(D(T)=T-T\) can vary with the embedding of \(H\) in \(G\). We call $ \delta(G,H)=\min_T |D(T)| $ the transversal difference number of the pair \((G,H)\). This invariant is related to finite abelian factorisation, tiling complements, and small-sumset questions, and is motivated by recent work regarding ambient Galois labels in CRT transforms for cyclotomic-subfield homomorphic encryption. We prove various results regarding this invariant, including a general lower bound $\delta(G,H)\geq 2|G/H|-m(G,H), $ where \(m(G,H)\) is the largest order of a subgroup of \(G\) disjoint from \(H\). The bound is sharp for cyclic quotients, and Kneser's theorem gives a cross-transversal estimate leading to exact product families with one nonsplit cyclic coordinate and arbitrary split factors. These results isolate the first genuinely new residual obstruction, namely the same-prime square plane \[ G=(\mathbb Z/p^2\mathbb Z)^2,\qquad H=pG. \] For odd \(p\), this case is the technical core of the paper. Here transversals are graphs of functions \(\mathbb F_p^2\to \mathbb F_p^2\), and \(D(T)\) decomposes into carry-corrected finite-field derivative images. We conjecture that \[ \delta(G,H)=(2p-1)^2 \] for all odd primes \(p\), prove the unconditional lower bound \(3p^2-p-1\), and give small-prime, probabilistic, and fixed-polynomial evidence for the conjecture.
- [26] arXiv:2606.28085 (cross-list from math.RT) [pdf, html, other]
-
Title: Average divisibility in character tables of $\mathrm{GL}_2(\mathbb{F}_q)$Comments: Version 1: 22 pagesSubjects: Representation Theory (math.RT); Combinatorics (math.CO); Number Theory (math.NT)
Let $q$ range over odd prime powers and let $G_q=\mathrm{GL}_2(\mathbb{F}_q)$. Fix a prime number $\ell$. Motivated by work of Peluse and Soundararajan on Miller's conjecture for character tables of symmetric groups, we study the proportion of entries in the character table of $G_q$ which are not divisible by $\ell$, in the sense of divisibility in the ring of algebraic integers. We prove that $N_\ell(q)=\frac{q^4}{2}+O_\epsilon(q^{3+\epsilon})$ for every $\epsilon>0$, where $N_\ell(q)$ denotes the number of entries which are not divisible by $\ell$. We also show that the number of zero entries is $\frac{q^4}{2}+O_\epsilon(q^{3+\epsilon})$. Consequently, the proportion of all entries not divisible by $\ell$ tends to $1/2$, while the proportion of nonzero entries not divisible by $\ell$ tends to $1$. This differs significantly from the symmetric-group case, where almost every character-table entry is divisible by any fixed prime. We also prove an angular equidistribution result for the nonzero character values as $q\to\infty$. We show that the arguments become equidistributed in $[0,2\pi]$. This proves an analogue of Miller's question on the distribution of signs among the nonzero entries in character tables of symmetric groups.
- [27] arXiv:2606.28315 (cross-list from cs.DM) [pdf, other]
-
Title: Pairwise Reflection Symmetry in Generalized Latin RectanglesComments: 16 pages, 2 figuresSubjects: Discrete Mathematics (cs.DM); Combinatorics (math.CO)
Many combinatorial designs ask for equal distribution of given symbols across the entries of a matrix. The paramount examples are Latin squares, where each symbol from $\{1,\dots,n\}$ appears once per row and column of an $n\times n$ matrix. Generalized Latin rectangles extend this to $\lambda n \times n$ matrices with repeated symbols under controlled column frequencies. In this more general setting, we examine structural properties of pairwise reflection-symmetry, which requires that, on every pair of columns, each ordered symbol pair $(p,q)$ occurs as often as its reversal $(q,p)$. This order-balance is precisely what makes head-to-head comparisons unbiased, i.e., no symbol gains a systematic advantage from the position it occupies relative to another, a fairness demand arising for instance when scheduling tournaments or laying out comparative trials. Existence of such objects for odd $\lambda$ turns out to be remarkably more subtle than for even $\lambda$. After showing that existence holds also for sufficiently large odd $\lambda$, we initiate the search for the smallest possible value of $\lambda$ in this setting. We obtain the insight that a column multiplicity of $\lambda=1$ can be achieved if and only if $n$ is a power of two. We complement the existence results with a direct product construction and add several further observations on the property. Finally, we propose and evaluate a quadratically constrained integer program to computationally search for these objects. The resulting experiments reveal that many of them possess an underlying group-theoretic structure which, as we conjecture, may even be unavoidable in certain settings.
Cross submissions (showing 6 of 6 entries)
- [28] arXiv:2307.16134 (replaced) [pdf, html, other]
-
Title: A new simple family of non-periodic tilings with square tilesSubjects: Combinatorics (math.CO); Logic (math.LO)
We define a new family of non-periodic tilings with square tiles that is mutually locally derivable with some family of tilings with isosceles right triangles. Both families are defined by simple local rules, and the proof of their non-periodicity is as simple as that of the non-periodicity of Robinson's tilings. We also relate the construction to the classical chair tiling: forgetting the decoration, our tilings map almost one-to-one onto the chair, our substitution is essentially a square root of the chair substitution, and our local rules are perfect, defining exactly the family of substitution tilings.
- [29] arXiv:2504.00404 (replaced) [pdf, html, other]
-
Title: Perfect state transfer on gcd-graphs over a finite Frobenius ringComments: To appear in International Journal of Algebra and ComputationSubjects: Combinatorics (math.CO)
The existence of perfect state transfer (PST) on quantum spin networks is a fundamental problem in mathematics and physics. Various works in the literature have explored PST in graphs with arithmetic origins, such as gcd-graphs over $\mathbb{Z}$ and cubelike graphs. In this article, building on our recent work on gcd-graphs over an arbitrary finite Frobenius ring, we investigate the existence of PST on these graphs. Our approach is algebraic in nature, enabling us to unify various existing results in the literature.
- [30] arXiv:2504.19325 (replaced) [pdf, html, other]
-
Title: Projective systems and bounds on the length of codes of non-zero defectSubjects: Combinatorics (math.CO); Information Theory (cs.IT)
We derive bounds on the lengths of linear codes with fixed Singleton defect $s$, working within the framework of projective systems as advocated by Tsfasman and Vlǎduţ. This geometric perspective allows us to unify and extend a range of existing results. We introduce the parameter $m^s(k,q)$, denoting the maximum length of a non-degenerate $[n,k,d]_q$ A$^s$MDS code, and more generally $m^s_t(k,q)$, where the dual code is additionally required to be A$^t$MDS. We also study $\kappa(s,q)$, the maximum dimension $k$ for which a length-maximal A$^s$MDS code exists. Among our main results, we provide sufficient conditions on $n$ and $k$ under which the dual of an A$^s$MDS code is necessarily A$^s$MDS, addressing a gap in the existing literature. We show that codes of sufficient length must be projective, meet the Griesmer bound, and be dual to an AMDS code. Our bounds subsume or improve several results in the literature. Two conjectures on the non-existence of length-maximal codes of dimension $k\ge 5$ are proposed, supported by computational evidence.
- [31] arXiv:2509.26630 (replaced) [pdf, html, other]
-
Title: Optimal Embeddings of Posets in HypercubesComments: 7 pages, 1 figureSubjects: Combinatorics (math.CO)
Given a finite poset $\mathcal P$, the hypercube-height, denoted by $h^*(\mathcal P)$, is defined to be the minimum $h$ such that there exists a natural number $n$ for which the subsets of $[n]$ of size at most $h$ contain an induced copy of $\mathcal P$. The hypercube-width, denoted by $w^*(\mathcal P)$, is the smallest $w$ such that the subsets of $[w]$ of size at most $h^*(\mathcal P)$ contain an induced copy of $\mathcal P$. In other words, $h^*(\mathcal P)$ asks how `low' can a poset be embedded, and $w^*(\mathcal P)$ asks for the first hypercube in which such an `optimal' embedding occurs.
These notions were introduced by Bastide, Groenland, Ivan and Johnston in connection to upper bounds for the poset saturation numbers. While it is not hard to see that $h^*(\mathcal P)\leq |\mathcal P|-1$ (and this bound can be tight), the hypercube-width has proved to be much more elusive. It was shown by the authors mentioned above that $w^*(\mathcal P)\leq|\mathcal P|^2/4$, but they conjectured that in fact $w^*(\mathcal P)\leq |\mathcal P|$ for any finite poset $\mathcal P$.
In this paper we prove this conjecture. The proof uses Hall's theorem for bipartite graphs as a precision tool for modifying an existing copy of our poset. - [32] arXiv:2510.18010 (replaced) [pdf, html, other]
-
Title: On the expansion of Hanoi graphsComments: 18 pages, 5 figuresSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
The famous Tower of Hanoi puzzle involves moving $n$ discs of distinct sizes from one of $p\geq 3$ pegs (traditionally $p=3$) to another of the pegs, subject to the constraints that only one disc may be moved at a time, and no disc can ever be placed on a disc smaller than itself. Much is known about the Hanoi graph $H_p^n$, whose $p^n$ vertices represent the configurations of the puzzle, and whose edges represent the pairs of configurations separated by a single legal move. In a previous paper, the present authors presented nearly tight asymptotic bounds of $O((p-2)^n)$ and $\Omega(n^{(1-p)/2}(p-2)^n)$ on the treewidth of this graph for fixed $p \geq 3$. In this paper we show that the upper bound is tight, by giving a matching lower bound of $\Omega((p-2)^n)$ for the expansion of $H_p^n$.
- [33] arXiv:2511.17034 (replaced) [pdf, html, other]
-
Title: Affine Jacobi-Trudi Identities and $q,t$-Rogers-Ramanujan IdentitiesJournal-ref: SIGMA 22 (2026), 062, 50 pagesSubjects: Combinatorics (math.CO); Number Theory (math.NT); Representation Theory (math.RT)
We conjecture affine or Hall-Littlewood analogues of the dual Jacobi-Trudi identities for orthogonal and symplectic Schur functions indexed by rectangular partitions of maximal height. These conjectures are then used to derive $t$-analogues of many known Rogers-Ramanujan identities for the characters of standard modules of affine Lie algebras. This includes $t$-analogues of the classical Rogers-Ramanujan identities, (some of) the Andrews-Gordon identities and the $\mathrm{C}_n^{(1)}$, $\mathrm{A}_{2n}^{(2)}$ and $\mathrm{D}_{n+2}^{(2)}$ GOW identities. We also prove an affine analogue of the dual Jacobi-Trudi identity for Schur functions indexed by rectangular partitions of arbitrary height.
- [34] arXiv:2511.21144 (replaced) [pdf, html, other]
-
Title: On the order-diameter ratio of girth-diameter cagesComments: 23 pagesSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
For integers $k,g,d$, a $(k;g,d)$-cage (or simply girth-diameter cage) is a smallest $k$-regular graph of girth $g$ and diameter $d$ (if it exists). The order of a $(k;g,d)$-cage is denoted by $n(k;g,d)$. We determine asymptotic lower and upper bounds for the ratio between the order and the diameter of girth-diameter cages as the diameter goes to infinity. We also prove that this ratio can be computed in constant time for fixed $k$ and $g$.
We theoretically determine the exact values $n(3;g,d)$, and count the number of corresponding girth-diameter cages, for $g \in \{4,5\}$. Moreover, we design and implement an exhaustive graph generation algorithm and use it to determine the exact order of several open cases and obtain -- often exhaustive -- sets of the corresponding girth-diameter cages. The largest case we generated and settled with our algorithm is a $(3;7,35)$-cage of order 136. - [35] arXiv:2512.14939 (replaced) [pdf, html, other]
-
Title: Excluding a line from positroidsComments: To appear in European Journal of Combinatorics. This version includes new corollaries of the main resultSubjects: Combinatorics (math.CO)
For all positive integers $\ell$ and $r$, we determine the maximum number of elements of a simple rank-$r$ positroid without the rank-$2$ uniform matroid $U_{2,\ell+2}$ as a minor, and characterize the matroids with the maximum number of elements. We prove this as a consequence of a more general result, which also determines the maximum number of elements of a simple rank-$r$ bicircular matroid, lattice path matroid, multi-path matroid, or colaminar matroid with no $U_{2,\ell+2}$-minor. This result continues a long line of research into upper bounds on the number of elements of matroids from various classes that forbid $U_{2,\ell+2}$ as a minor. This is the first paper to study positroids in this context, and it suggests methods to study similar problems for other classes of matroids, such as gammoids or base-orderable matroids.
- [36] arXiv:2604.05146 (replaced) [pdf, html, other]
-
Title: Equitable coloring of large bipartite graphsSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM)
For a graph $G$, the \emph{equitable chromatic number} of $G$, denoted by $\chi_e(G)$, is the smallest integer $k$ such that $G$ admits a proper $k$-coloring whose color classes differ in size by at most one. We prove that for every $\zeta>41/2$, there exists a constant $c=c(\zeta)\in\mathbb{N}$ such that every bipartite graph $G$ with maximum degree $\Delta(G)\ge c$ and $|V(G)|\ge \zeta\Delta(G)$ satisfies $\chi_e(G)\le \left\lceil\Delta(G)/2\right\rceil+1$. The leading term $\Delta(G)/2$ in this bound is best possible for upper bounds stated solely in terms of $\Delta(G)$ for bipartite graphs. Our proof yields an $O(|V(G)|^2)$-time algorithm for constructing such a coloring.
- [37] arXiv:2606.00420 (replaced) [pdf, html, other]
-
Title: Counterexamples regarding elementary symmetric partitionsComments: 18 pages. Comments welcome! v2. Small correction to Conjecture 1.3, updated a reference v3. Added Remark 1.4 and acknowledgments, noted progress made on Question 5.3Subjects: Combinatorics (math.CO)
Ballantine, Beck, and Merca defined the elementary symmetric partition map pre$_j$ that sends a partition $\lambda$ to a larger partition whose parts are the summands appearing in the evaluation of the $j$-th elementary symmetric polynomial on $\lambda$. They conjectured that pre$_j$ is injective on the set of partitions of $n$ with length $\ell \geq j$. The $\ell = j$ case was disproved by Devnani and Eyyunni; they instead conjectured the statement to be true for $\ell > j$. In this article, we answer this refined conjecture in the negative by proving that pre$_j$ is not injective on partitions of $n$ with length $2j$ for $j \geq 3$. We also prove that the analogous map prh$_j$ defined via the complete homogenous symmetric polynomial is injective on the set of all partitions.
- [38] arXiv:2606.20043 (replaced) [pdf, html, other]
-
Title: Improved bound on symmetric differences of intersecting familiesSubjects: Combinatorics (math.CO)
For a family $\mathcal{F}$, it is called intersecting if $F\cap F'\neq \emptyset$ for all $F,F'\in\mathcal{F}$. We use $\mathcal{SD}(\mathcal{F}) = \{F \triangle G : F, G \in \mathcal{F}\}$ to denote the family of symmetric differences of $\mathcal{F}$. In 2023, Frankl, Kiselev and Kupavskii conjectured that for any intersecting family $\mathcal{F} \subseteq \binom{[n]}{k}$ with $n > 10k$, the inequality $|\mathcal{SD}(\mathcal{F})| \le \sum_{\ell=0}^{k-1} \binom{n-1}{2\ell}$ holds. They further observed that a proof for the range $n>3k^2$ could likely be obtained via arguments similar to those in their earlier work, though no detailed derivation was given. In this paper, we establish the conjecture under the conditions $n\ge 100k\ln k$ and $k\ge 50$. We also determine the extremal families, which are precisely a certain class of stars. A concentration inequality plays a central role in the proof.
- [39] arXiv:2606.26582 (replaced) [pdf, html, other]
-
Title: Time Structure in Infinite Extensive GamesSubjects: Combinatorics (math.CO)
We extend graph theoretic characterizations of time structurable extensive games from finite informational digraphs to countable and continuum digraphs built on continuum rooted real trees. Introducing the symmetric class quotient poset of information sets as the canonical object an external clock must order, we develop a theory of transitive reduction for these quotients and prove existence and uniqueness under an interval finiteness condition. Under natural topological regularity assumptions like closed reachability classes, order density, and sigma compactness, we give necessary and sufficient conditions for real valued time labelings and construct measurable selection procedures in Polish spaces. We also provide constructive algorithms and a differential game example illustrating applications and computational implications.
- [40] arXiv:2409.13240 (replaced) [pdf, other]
-
Title: Discrete (P)-closed Groups Acting On TreesComments: 17 pages, 3 figures. Revised Definition 1.2 and added Lemma 2.3, Proposition 2.4, and Proposition 3.1. Improved proof of Theorem 3.2Subjects: Group Theory (math.GR); Combinatorics (math.CO)
Reid-Smith recently parametrised groups acting on trees with Tits' independence property (P) using graph-based combinatorial structures known as local action diagrams. Properties of the acting (topological) group, such as being locally compact, compactly generated or simple, are reflected in its local action diagram. In this article we provide necessary and sufficient conditions on the local action diagram for the associated group to be discrete.
- [41] arXiv:2410.02135 (replaced) [pdf, html, other]
-
Title: Fine multidegrees, universal Grobner bases, and matrix Schubert varietiesComments: To appear in Journal of the London Math SocietySubjects: Algebraic Geometry (math.AG); Commutative Algebra (math.AC); Combinatorics (math.CO)
We give a criterion for a collection of polynomials to be a universal Gröbner basis for an ideal in terms of the multidegree of the closure of the corresponding affine variety in $(\mathbb{P}^1)^N$. This criterion can be used to give simple proofs of several existing results on universal Gröbner bases. We introduce fine Schubert polynomials, which record the multidegrees of the closures of matrix Schubert varieties in $(\mathbb{P}^1)^{n^2}$. We compute the fine Schubert polynomials of permutations $w$ where the coefficients of the Schubert polynomials of $w$ and $w^{-1}$ are all either 0 or 1, and we use this to give a universal Gröbner basis for the ideal of the matrix Schubert variety of such a permutation.
- [42] arXiv:2502.16625 (replaced) [pdf, html, other]
-
Title: On a problem of Erdos and HajnalSubjects: Logic (math.LO); Combinatorics (math.CO)
We address a question of Erdős and Hajnal about the ordinary partition relation $\aleph_{\omega+1}\nrightarrow(\aleph_{\omega+1},(3)_{\aleph_0})^2$. For $\theta=\mathrm{cf}(\lambda)<\lambda$, assuming $2^\lambda=\lambda^+$ they proved the negative relation $\lambda^+\nrightarrow(\lambda^+,(3)_\theta)^2$ and asked whether the (local instance of) GCH is indispensable. We show that this negative relation is consistent with $\lambda$ being a strong limit and $2^{\lambda}>\lambda^+$. The result can be pushed down to $\aleph_{\omega}$.
- [43] arXiv:2505.01193 (replaced) [pdf, html, other]
-
Title: Going deep and going wide: Counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidthComments: arXiv admin note: text overlap with arXiv:2308.06044Subjects: Logic in Computer Science (cs.LO); Discrete Mathematics (cs.DM); Combinatorics (math.CO)
We study the expressive power of first-order logic with counting quantifiers, especially the $k$-variable and quantifier-rank-$q$ fragment, using homomorphism indistinguishability. Recently, Dawar, Jakl, and Reggio~(2021) proved that two graphs satisfy the same $k$-variable and quantifier-rank-$q$ sentences if and only if they are homomorphism indistinguishable over the class of graphs admitting a $k$-pebble forest cover of depth $q$. After reproving this result using elementary means, we provide a graph-theoretic analysis of this graph class. This allows us to separate it from the intersection of the class of all graphs of treewidth at most $k-1$ and the class of all graphs of treedepth at most $q$, provided that $q$ is sufficiently larger than $k$.
We are able to lift this separation to a (semantic) separation of the respective homomorphism indistinguishability relations. We do this by showing that the graph classes of all graphs of treedepth at most $q$ and of graphs admitting a $k$-pebble forest cover of depth $q$ are homomorphism distinguishing closed, as conjectured by Roberson~(2022).
In order to prove Roberson's conjecture for the class of graphs admitting a $k$-pebble forest cover of depth $q$ we characterise the class in terms of a monotone Cops-and-Robber this http URL crux is to prove that if Cop has a winning strategy then Cop also has a winning strategy that is this http URL that end, we show how to transform Cop's winning strategy into a pre-tree-decomposition, which is inspired by decompositions of matroids, and then applying an intricate breadth-first `cleaning up' procedure along the pre-tree-decomposition (which may temporarily lose the property of representing a strategy), in order to achieve monotonicity while controlling the number of rounds simultaneously across all branches of the decomposition via a vertex exchange argument. - [44] arXiv:2605.11833 (replaced) [pdf, html, other]
-
Title: Self-similar dendrites with finite boundary and P-sproutsComments: 22 pages, 10 figuresSubjects: Metric Geometry (math.MG); Combinatorics (math.CO)
Each self-similar dendrite K with a finite self-similar boundary defines a finite acyclic edge-labeled bipartite graph G, called the sprout of K. The paper shows that the sprout G determines the combinatorial properties of the dendrite K and its topological structure.
- [45] arXiv:2605.16478 (replaced) [pdf, html, other]
-
Title: A nonabelian twist on differences of bijectionsComments: Remark 5.3 has been added, and minor typos have been corrected. To appear in Utilitas MathematicaSubjects: Group Theory (math.GR); Combinatorics (math.CO)
Hall's theorem on differences of bijections characterizes the multisets $$ \{a_1,\ldots,a_{|G|}\} $$ in a finite abelian group $G$ that can be written in the form $$ a_i=b_i-c_i, $$ where both $b_1,\ldots,b_{|G|}$ and $c_1,\ldots,c_{|G|}$ are enumerations of $G$. The necessary and sufficient condition is the zero-sum condition $$ a_1+\cdots+a_{|G|}=0. $$ This paper studies the corresponding problem for finite nonabelian groups, with differences replaced by quotients. Thus we ask when a multiset $A$ of cardinality $|G|$ can be represented as $$ A=\{b(i)c(i)^{-1}:1\le i\le |G|\}, $$ where $b$ and $c$ are bijections onto $G$.
Passing to the abelianization gives a necessary condition, namely that the product of the images of the elements of $A$ is trivial in $ G_{\rm ab}. $ We show that this condition is not sufficient in general, even when the elements of $A$ admit an ordering whose product is the identity in $G$. The main structural result is a cycle-tiling criterion: quotient-realizability is equivalent to a decomposition of $A$ into product-one words whose partial-product sets tile $G$ by right translates. The use of permutation cycles is standard, but the criterion translates quotient-realizability into an exact tiling condition. We then use this criterion to construct a counterexample in $ S_3, $ and we extend the same obstruction to infinitely many finite nonabelian groups. - [46] arXiv:2605.28770 (replaced) [pdf, html, other]
-
Title: Cutoff profiles for conjugacy invariant random walks on symmetric groupsComments: v2: 27 pages, 5 figures, comments welcome!Subjects: Probability (math.PR); Combinatorics (math.CO); Representation Theory (math.RT)
We prove asymptotic equivalents of characters for finite-level representations of symmetric groups, that is, for Young diagrams which have all but finitely many boxes on their first row. The proofs rely on computing the number of ribbon tableaux of different types, which allows us to estimate characters via the Murnaghan--Nakayama rule. We deduce that random walks on symmetric groups generated by conjugacy classes with a macroscopic number of fixed points have a Poissonian cutoff profile. We also prove that the random involution walk exhibits cutoff and find its cutoff profile. Finally, we obtain numerics for the random transposition walk on a deck of 52 cards, giving concrete estimates on the question that originally motivated Diaconis and Shahshahani.
- [47] arXiv:2606.18234 (replaced) [pdf, html, other]
-
Title: On zero-sum problems of new typesComments: 17 pages. Mainly make Theorem 1.1 stronger and add Conjecture 1.1Subjects: Number Theory (math.NT); Combinatorics (math.CO)
In this paper, we investigate zero-sum problems of new types. For example, given $2n-1$ integers $a_1,\ldots,a_{2n-1}$ not divisible by an integer $n>1$, we prove that for some nonempty $I\subseteq\{1,\ldots,2n-1\}$ with $|I|\leqslant n$, the sum $\sum_{i\in I}a_i$ is divisible by $n$ but not divisible by $n^2$. We also pose several conjectures for further research.
- [48] arXiv:2606.24583 (replaced) [pdf, html, other]
-
Title: More sum-product type counterexamples: products with shifts and $AA+A$Comments: Added Carl Schildkraut as an author, and added further expander resultsSubjects: Number Theory (math.NT); Combinatorics (math.CO)
Adapting the construction disproving the sum-product conjecture over $\mathbb R$ present in Bloom, Sawin, Schildkraut and Zhelezov, we show the existence of a constant $c>0$ and arbitrarily large finite sets $A \subseteq \mathbb R$ such that
$$|AA+A+A| \ll |A|^{2-c}.$$ As a corollary, all of the sets $A+A$, $AA$, $(A+1)(A+1)$, $A(A+1)$ and $AA+A$ are of size $O(|A|^{2-c})$ for this construction. - [49] arXiv:2606.26564 (replaced) [pdf, html, other]
-
Title: Characterizing Pure Strategy Nash Equilibria in Finite Noncooperative GamesSubjects: Computer Science and Game Theory (cs.GT); Combinatorics (math.CO)
The classical existence result of Nash guarantees that every finite noncooperative game admits an equilibrium in mixed strategies, but it leaves open the question of when pure strategy equilibria exist. This paper develops a structural approach to that question by exploiting properties of the best-response correspondence on finite strategy sets. Building on recent work, we derive new sufficient conditions for the existence of pure strategy Nash equilibria in finite games. We introduce several broad classes of finite games for which pure equilibria are guaranteed, including a class that generalizes unilaterally competitive games and a class characterized by the existence of an aggregate-payoff maximizer over an ordered set. Our results clarify the role of acyclicity, and aggregation in producing pure equilibria and connect disparate sufficient-condition results in the literature into a unified framework.
- [50] arXiv:2606.26776 (replaced) [pdf, other]
-
Title: Artin monoids, their homomorphisms and twinsComments: AmsLaTeX+amsrefs, 79 pages; some misprints corrected. Parts of this paper appeared previously in the preprint arXiv:2405.18821. The current paper has been substantially reorganized and includes new approachesSubjects: Quantum Algebra (math.QA); Combinatorics (math.CO); Representation Theory (math.RT)
Motivated by the twin homomorphism problem for Coxeter groups and the corresponding Hecke monoids, we find a large class of its solutions originating from standard homomorphisms of Artin monoids and their compositions. These homomorphisms are expected to be injective when they are optimal and injective on generators, which generalizes the homogeneous homomorphisms and the famous Tits conjecture settled by Crisp and Paris. We classify disjoint standard homomorphisms and conjecture the complete classification when the domain is of rank two.
- [51] arXiv:2606.27179 (replaced) [pdf, html, other]
-
Title: Linear Code Conversion in the Merge Regime: General Bounds and Reed-Muller ConstructionsComments: arXiv admin note: text overlap with arXiv:2601.10341Subjects: Information Theory (cs.IT); Discrete Mathematics (cs.DM); Combinatorics (math.CO); Number Theory (math.NT)
Erasure codes are a core component of most existing large-scale distributed storage systems, ensuring reliability against node failures. Recent work has shown that adapting code parameters to changing node failure rates can lead to significant storage savings. The default approach is to re-encode the data under a new code, which consumes substantial system resources. Code conversion was introduced to reduce this cost. However, existing work has mainly focused on conversions within specific classes of codes. In this paper, we study scalar linear code conversion in the merge regime for arbitrary linear codes. We derive universal lower bounds on the write and read costs in terms of unchanged and read symbols. The bounds are refined using generalized Hamming weights, which capture support-growth properties of subcodes and can give sharper estimates than minimum-distance-only arguments. We show that the framework recovers known bounds for important special cases and can be strictly stronger when the final code has nontrivial jumps in its generalized Hamming weight hierarchy. We then apply the framework to Reed-Muller codes and construct explicit Reed-Muller convertible codes using the Plotkin decomposition. For a natural Reed-Muller parameter regime, the construction attains the derived write-cost lower bound. For the read cost, the generalized-Hamming-weight analysis is sharp for one initial block, while a gap remains for the other block.