Papers

Let k be an integer at least 2, and let D_{N,k} be the set of permutations of {1,...,N} whose descent set is exactly {k, 2k, ..., k*floor((N-1)/k)}. We enumerate the elements of D_{N,k} avoiding each classical and each vincular pattern of length three. For classical patterns, we give recursive bijections from the 132- and 231-avoiding classes to ordered forests of complete k-ary trees, obtaining the Raney number. The 213- and 312-avoiding classes are obtained from these forest bijections by completing the last block and applying reverse-complement symmetry. The remaining classical case 321 is expressed by RSK. For vincular patterns, we enumerate the six fully consecutive patterns and the twelve patterns with exactly one adjacency. The closed-form results are accompanied by bijective models: the Catalan, Raney, Fuss-Catalan, and RSK cases are natural k-ary or fixed-descent extensions of classical bijections, while the product and poset cases arise from block-insertion and record/tree-poset encodings forced by the adjacency conditions.

For $n\ge1$, let $F(n)$ be the least $H$ such that any $H$ consecutive integers contain $n$ pairwise distinct integers $a_1, a_2, \dots, a_n$ with $k \mid a_k$ for $1\le k\le n$, and define $h_{\mathbb P}(n)$ analogously for the primes at most $n$. We prove \[ F(n)\le n^{4/3}\exp\!\left(O\!\left(\frac{\log n}{\log\log n}\right)\right), \qquad h_{\mathbb P}(n)\ll \frac{n^{4/3}}{(\log n)^{1/3}}, \] and \[ F(n) \ge h_{\mathbb P}(n)\ge n\exp\!\left( \left(\frac{\log 2}{2}-o(1)\right) \frac{\log n}{\log\log n} \right). \] The upper bounds follow from a new estimate for unions of arithmetic progressions. The lower bound adapts a quadratic-residue compression construction of Green and Ruzsa.

Let $k$ and $n$ be positive integers such that $2 \leq k \leq n+1$. We prove that the number of $k$-chains in a union-closed family with universe $[n]$ and size $m$ is minimized when its member sets are largest possible. We also show that, whenever the minimum is nonzero and $m>n$, there are no other minimizing families.

This paper defines a family of Hurwitz–Lerch type functions whose coefficients are the \(k\)-augmented centered triangular numbers. For this family, we obtain the convergence conditions, a reduction formula, and an Euler-operator form. A Vandermonde-based inversion formula is derived for a class of polynomially weighted Hurwitz–Lerch functions. The family considered here is the quadratic case with geometric factors \(1\), \(2\), and \(4\). The resulting formulas show that three consecutive functions recover the classical Hurwitz–Lerch transcendent and its first two Euler derivatives. We also derive recurrence formulas, ordinary generating functions, finite sums, and special values. The values at \(z=1\) are expressed through Hurwitz zeta functions and Bernoulli polynomials. When \(a=1\), the numerator polynomials of the rational values \(H_k(z,-m,1)\) are written in terms of Eulerian polynomials, while the alternating values \(H_k(-1,-m,a)\) are expressed through Euler polynomials.

Persistent homology summarizes the birth and death of topological features, but it does not by itself specify where a feature is located in the underlying complex. Harmonic persistent homology addresses this by assigning canonical harmonic cycle representatives to bars. In earlier work, Basu and Cox showed that harmonic representatives of simple bars maximize the total relative weight placed on essential simplices, the simplices that are forced to appear in representatives of the corresponding class. In this paper we prove that, for generic one-dimensional bars, this preference is stronger than an aggregate maximization statement. Every essential edge has strictly larger coefficient, in absolute value, than every non-essential edge in the harmonic representative, and the absolute values of the coefficients of all essential edges are equal. The key argument is a finite-dimensional variational characterization of the harmonic representative as a minimum-norm chain with prescribed boundary, combined with an elementary graph-theoretic cut argument. We then prove that the result is special to dimension one. In higher dimensions, the analogous coefficient-wise dominance statement fails. We give examples to show that harmonic representatives can place larger coefficients on non-essential higher-dimensional simplices than on essential ones. These results clarify both the power and the limitations of using harmonic representatives to assign geometric significance to simplices in persistent homology.

The claw-free Schur-positivity conjecture, recorded by Stanley (1998) and credited there to Gasharov, asserts that the chromatic symmetric function of every claw-free graph is Schur-positive. We give a counterexample on 12 vertices: the line graph $G$ of the graph obtained from a 4-cycle by attaching triangles at two opposite vertices and pendant edges at the other two satisfies $[s_{(3,3,3,3)}]X_G = -64$. The coefficient follows from a short computation by hand and is also reproduced by three exact implementations. An exhaustive computation over all 216,777 connected claw-free graphs on at most 11 vertices shows that every one is Schur-positive, so 12 vertices is the minimum order of any counterexample. A complete census of the 1,728,404 connected claw-free graphs on 12 vertices finds exactly two non-Schur-positive isomorphism classes; the other has graph6 code K?`CR@`bAbRB and coefficient $[s_{(3,3,3,3)}] = -40$.

A 6-net is a simplicial triangulation of the $2$-sphere with maximum degree $\leq 6$. Experiments suggest that every $6$-net admits a unique realization as an undented Euclidean polyhedron built from unit equilateral triangles, and a unique realization as an ideal equilateral hyperbolic polyhedron. We call these neoplatonic solids and ideal neoplatonics. A net is prime if every 3-cycle bounds a face. A computer-assisted proof shows that every prime $6$-net with $v \leq 50$ has a unique realization as a convex ideal neoplatonic. Numerical homotopy from this realization yields an approximate Euclidean neoplatonic, and a computer-assisted proof shows that a true Euclidean neoplatonic lies nearby, though we do not prove uniqueness. Using the separating-triangle decomposition, we extend Euclidean existence to all $10{,}412{,}340$ $6$-nets with $v\leq50$, counted up to combinatorial isomorphism.

Motivated by the solution of Descartes famous problem on the chains of tangent circles given by D.Mathews and O.Zymaris, we give an algorithmic solution to the feasibility problem for radii of Steiner 4-chains studied by K.Kirajiev. More precisely, we obtain a complete characterization of the ordered quadruples of positive numbers which coincide with a quadruple of curvatures of the circles forming a Steiner 4-chain. Our approach makes essential use of the numerical invariants of Steiner chains introduced in a recent paper of R.Schwartz and S.Tabachnikov. We compute all invariants of Steiner 4-chains and establish the algebraic relations between those invariants which are used in the proof of the main result. Several related observations and illustrative examples are also given. Keywords: Steiner chain, parent circles, Steiner porism, poristic Steiner chains, Descartes circle theorem, invariant moments of curvatures, algebraic relations between invariants, symmetric Steiner chains, feasibility problem for Steiner chains

We study two planar unit-distance graphs (UDGs) that both look like heptagons but have opposite rigidity yet kindred arithmetic: the braced heptagon {35,1} (19 vertices, 35 edges) and the complete heptagon {21,2} (21 vertices, 42 edges). Neither is straightedge-and-compass constructible – already the regular 7-gon is not, by Gauss-Wantzel – so the natural setting is origametry: the construction of each realization by Huzita-Hatori folds, with the quadratic fold O5 (straightedge-and-compass strength) versus the cubic Beloch fold O6. The complete heptagon is over-braced and globally rigid, with a unique realization whose 42 edges are certified unit exactly over Q(cos 2pi/7), a cyclic cubic field: every vertex is an origami number, reached by one Beloch fold. The braced heptagon is isostatic (minimally rigid) with thousands of non-congruent realizations and a large generic realization count N = 3869504 = 2^6 * 103 * 587; yet we prove that its unit realization is again origami-constructible. In Pegg's explicit construction the pinning angle is a root of an irreducible degree-12 palindromic polynomial whose Chebyshev reduction, an irreducible sextic, factors into quadratics over the heptagon cubic Q(cos 2pi/7); hence the coordinate field is a {2,3}-tower of degree 3*2^k, reached by one trisection followed by quadratics. The primes 103 and 587 therefore belong to the generic complex count, not to the folded coordinates. We solve the governing cubic explicitly by folding (Lill's method and the Beloch fold), place both graphs inside Alperin's field of origami numbers, and read the fold-branch signs of the construction as mountain-valley assignments with an empirical Maekawa-type balance. All claims are checked in exact arithmetic.

Let $q$ be an odd prime power, and let $A_n=(a_{ij})\in\mathbb F_q^{n\times n}$ be a random matrix whose entries are independent and uniformly distributed on $\mathbb F_q$. The permanent of $A_n$ is defined by $\operatorname{per}(A_n)=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}$, where $S_n$ denotes the symmetric group on $[n]$. Ghasemi, Gross, and Kopparty conjectured the zero-mass asymptotic $\Pr[\operatorname{per}(A_n)=0]=1/q+o(1)$ for every fixed odd prime power $q$, and Hunter, Kwan, and Sauermann subsequently stated its equivalent full-distribution formulation: for every fixed $q$ and every $x\in\mathbb F_q$, \[ \lim_{n\to\infty}\Pr[\operatorname{per}(A_n)=x]=\frac1q. \] In this paper, we prove this conjecture. More precisely, we prove that there is an absolute constant $C>0$ such that \[\frac12\sum_{x\in\mathbb F_q}\left|\Pr[\operatorname{per}(A_n)=x]-\frac1q\right|\le C\frac{\log n}{n}\] for every odd prime power $q$ and every $n\ge 7$. The estimate is uniform in $q$, so the conclusion remains valid for every sequence $q=q(n)$ of odd prime powers.

Let G be a nonempty finite simple graph of order n, and let m(G) be the upper median of its degree sequence. We prove that the 2-domination number satisfies gamma_2(G) <= n - m(G) + 1. This proves Graffiti.pc Conjecture 387. In fact, the argument establishes the inequality for every nonempty finite simple graph, so the connectedness hypothesis in the original formulation is unnecessary. The proof uses the complement graph and a minimally linearly dependent family of polynomials encoding selected nonneighborhoods.

We extend the nice treatment of V. Bardenova, E. Insko, K. Johnson, and S. Sullivan of the combinatorics of two-lane mergings to the multi-lane case.

Alon and Füredi proved that at least $n$ affine hyperplanes are required to cover $\{0,1\}^n\setminus\{\textbf{0}\}$ while avoiding the origin, and that this bound is sharp. We study how small the largest Boolean intersection among the hyperplanes can be in a cover attaining this minimum. Let $F(n)$ denote the minimum possible value of $\max_{H\in\mathcal H} |H\cap\{0,1\}^n|$ over all families $\mathcal{H}$ of $n$ affine hyperplanes covering $\{0,1\}^n\setminus{\mathbf{0}}$ and avoiding the origin. We give an explicit construction, proving that $F(n)=(1+o(1))\frac{2^n}{n},$ and hence asymptotically attain the averaging lower bound.

Martinsson and Steiner recently proved that the fractional chromatic number of any $d$-degenerate triangle-free graph $G$ satisfies $\chi_f(G) = O\left(\frac{d}{\log d}\right)$. They further conjectured a sharp leading constant $1 + o(1)$. In this paper, we confirm their upper bound conjecture for graphs having girth at least $5$. Our proof is constructive: it gives an efficient randomized algorithm that, with high probability, computes a fractional coloring of weight at most $(1 + o(1))\frac{d}{\log d}$ in such graphs. Furthermore, we establish their conjectured lower bound in a stronger form: for any constant $g \ge 4$, there exist $d$-degenerate graphs having girth at least $g$ with $\chi_f(G) \ge (1 - o(1))\frac{d}{\log d}$. This lower bound is achieved by analyzing a random graph based on the uniform attachment model. Notably, our results reveal that this model lacks the typical computational complexity barriers found in Erdős-Rényi graphs, where there is a conjectured factor-$2$ algorithmic gap for this problem.

The problems of characterizing the graphs $G$ which are generically rigid in ${\mathbb R}^d$, or more generally, determining the rank function of the $d$-dimensional rigidity matroid ${\cal R}_d(G)$ of an arbitrary graph $G$, have been solved when $d\leq 2$ but are major open problems in discrete geometry when $d\geq 3$. In this paper we shall concentrate on the case when $d=3$. We first revisit a conjecture of Dress from 1987 that the rank of the ${\cal R}_3$-closure of a graph $G$ is determined by its maximal complete subgraphs of size at least five. We show that his conjectured value for the rank of the closure gives an upper bound on the actual value. We also deduce that the truth of this conjecture would imply a good characterization of the rank of ${\cal R}_3(G)$ for all graphs $G$. The rank formula in Dress's conjecture leads us to consider the family of $K_t$-covered graphs, i.e., graphs in which every edge belongs to a complete subgraph $K_t$, for some $t\geq 3$. This family contains several well-studied graph classes such as body-pin graphs, combinatorial zeolites, and molecular graphs. We introduce a new notion of rank contributions of vertices in an arbitrary matroid on the edge set of a graph $G$, and use it to obtain lower bounds on the rank contributions of vertices in ${\cal R}_3(G)$ and ${\cal C}^1_2(G)$ when $G$ is $K_t$-covered. We use these bounds to show that a conjectured min-max formula for the rank of body-pin graphs in ${\cal R}_3$ holds for the $C_2^1$-cofactor matroid (which is conjectured by Whiteley to be equal to ${\cal R}_3$), and to obtain new sufficient connectivity conditions for the (global) rigidity of $K_4$- and $K_5$-covered graphs in ${\mathbb R}^3$.

We show stability of persistent path homology of path complexes. As a consequence, we deduce the stability of persistent path homology of hypergraphs and of sequence hypergraphs, and recover the known stability result for digraphs, originally due to Chowdhury and Mémoli.

We construct two families of commutative Frobenius rings: discrete and continuous Frobenius quotients $K_f$, resp. $A_g$, which are defined as the quotients of shift, resp. differential operator algebras by the annihilator of a polynomial. These constructions model the numerical $K$-rings and Chow rings of smooth complete varieties. We show that there is a naturally defined isomorphism $\mathbb{Q} K_f \cong \mathbb{Q} A_g$ playing the role of the Chern character, precisely when the polynomials satisfy a combinatorial analogue of the Hirzebruch-Riemann-Roch theorem, which states that there exists an invertible element $\mathrm{td} \in \mathbb{Q} A_g^\times$, called the Todd class, such that $f = \mathrm{td} \cdot g$. In this case we show that $K_f$ carries all the structure needed to make it a suitable model for $K$-rings of complete smooth varieties: $K_f$ is a $\lambda$-ring, has well-defined Chern classes, determinants, and satisfies a combinatorial analogue of Serre duality. We further show that the construction is functorial and obtain a combinatorial analogue of the Grothendieck-Riemann-Roch theorem. Lastly, we investigate the existence of larger families of isomorphisms between Frobenius quotients defined by the action of a power series on a generating set, such as the truncated Chern character which yields an integral isomorphism $K_f \cong A_g$. We provide numerous examples and applications: we give a new formula for computing Snapper polynomials of matroids, show that the dualizing class of $K_f$ coincides with dualizing classes of matroids and linear families of polytopes, realize $K$-rings of toric variety bundles as Frobenius quotients, and study $K$-rings of Ehrhart fans as well as exceptional isomorphisms in this setting.

Neighboring seeds in a cluster algebra of affine type are seeds that are as close as possible to the boundary of the g-vector fan. This short note highlights the characterization of neighboring seeds given in a recent paper of Reading, Rupel, and Stella and applies that characterization in two ways. We prove a conjecture on the construction of universal geometric cluster algebras of affine type. We also characterize extended exchange matrices of affine type that are mutation-finite.

Graph expansion has long been recognised as an important and desirable property with applications in a wide range of areas in computer science and mathematics. A particular form of expansion known as `sublinear expansion' has recently been used particularly effectively in extremal graph theory, leading to the resolution of many long-standing and notable problems over the last decade and an improved understanding of the structure of sparse graphs. This survey will cover these advances.

For the algebra $\mathbb{R}[x^1,\ldots,x^d]$ of polynomials in $d\geqslant 1$ variables, regard the complete generalised Wronskian $W_d^k$ of differential order $k\geqslant 1$ over $\mathbb{R}^d$ as the $N=\tbinom{d+k}{d}$-ary Lie bracket. Take an $N$-tuple of polynomials, calculate their Wronskian, and keep re-using the newly-created polynomials to produce more of them. The problem is: how fast do their maximal total degrees grow with the number $n$ of iterations of the bracket? Here enter the $N$-bonacci numbers defined by the recurrence $F^{(N)}_n=F^{(N)}_{n-1}+\cdots+F^{(N)}_{n-N}\in \mathbb{N}$. We prove that for any choice of the initial arguments, the sequence of highest total degrees ${\mathsf{D}}^{(N)}_n \geqslant 0$ grows (if at all) asymptotically no faster than the $n$th $N$-bonacci number: $\lim_{n\to+\infty} ({\mathsf{D}}^{(N)}_n/F^{(N)}_n )<\infty$. We show that for $d=1$ and $k$ odd, the highest polynomial degrees do attain the $N$-bonacci bound. Keywords: Differential polynomial, $N$-ary Lie bracket, multivariate Wronskian determinant, Fibonacci numbers, $N$-bonacci numbers, asymptotic growth rate, growth of polynomial degrees, Skolem–Pisot problem.

A nonempty subfamily of a $k$-uniform hypergraph is an even cover if every vertex lies in an even number of its hyperedges; for $k=2$ these are edge-disjoint unions of cycles, so the minimum size of an even cover is the natural hypergraph analogue of girth. We prove Feige's 2008 conjecture on the hypergraph Moore bound: there are absolute constants $A$ and $C$ (independent of $k$) such that for every $k\ge3$ and every $1\le\ell\le n$, any $k$-uniform hypergraph on $n$ vertices with more than $C\,n^{k/2}/\ell^{k/2-1}$ hyperedges contains an even cover of size at most $A\,\ell\log(en/\ell)$. Our proof is based on sharp spectral bounds for Kikuchi matrices, which we expect to be of independent interest; we apply them to the refutation of random constraint satisfaction problems in a companion paper.

This paper explores the theory of letter transducers, Mealy automata, and bireversible automata from a combinatorial perspective analogous to the theory of Latin squares. We view the sets of transitions of letter transducers as analogs of orthogonal arrays, and discuss two other combinatorial encodings of Mealy automata analogous to orthogonal pairs of Latin squares and to $(k,n)$-nets. We characterize various classes of automata (Mealy, reversible, invertible, bireversible) in terms of these combinatorial structures. In particular, we represent the inversion and dualization of transducers as parastrophisms. Further, similarly to the notion of the isotopisms of the quasigroups associated to Latin squares, we develop the notion of isotopisms of letter transducers generalizing transducer symmetry and preserving the class of bireversible automata.

We have previously given a factorization of a symplectic column under the action of the parity involution which enabled to explicitly have written the inverse of the reduction map in the quantum Littlewood-Richardson bijection. Watanabe has written the reduction map as a composition of several maps, among them, combinatorial $R$-matrices on single columns and a reduction map on a shorter column with rank reduced by one. We now use this approach to write the inverse of the reduction map on a symplectic column by detecting the corresponding symplectic column of rank reduced by one and thus avoiding going through several map compositions.

We prove that the size $\# \{ k(m-k) : 1\leq k\leq m/2\} \cap \{ l(n-l) : 1\leq l\leq n/2\}$ is $(mn)^{o(1)}$, but can be arbitrarily large. This resolves Erdős problem $\# 443$.

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.

In this paper, we prove the existence of two completely independent spanning trees in the $n$-dimensional dual-cube $F_n$, a variant of the hypercube, for every $n \geq 5$. To this end, we use the hypercube structure of the clusters of $F_n$ to extend the construction of CIST from the $(n-1)$-dimensional hypercube to the dual-cube. In addition, we provide a recursive algorithm that builds the two trees while improving their diameters. Finally, we propose a conjecture regarding the existence of $k$ completely independent spanning trees in the dual-cube.

For all $\delta>0$ and infinitely many $n \in \mathbb N$, we show that there exists a set $L$ of $n$ lines in $\mathbb R^2$ such that there are no intersecting quadruples, but for every subset $L' \subset L$ such that $|L'| \geq n^{\frac{4}{5}+\delta}$, there exist three lines from $L'$ with a common point of intersection. This gives an improved bound for a dual form of a theorem of Balogh and Solymosi. As a consequence, we derive an improved lower bound for the Hadwiger-Debrunner number $HD_2(p,3)$. We also give, for all $0 \leq s \leq 1$ and arbitrarily large $n \in \mathbb N$, a construction of a point set $S \subset [n]^3$ with cardinality $|S|\geq n^{3-s}$, such that $S$ contains $O(n^{6-4s})$ collinear triples. This shows that a supersaturation lemma of Balogh and Solymosi is optimal, up to logarithmic factors.

We determine exactly which proper multiplicative subgroups of a prime field can be represented as a restricted sumset of the form $A\mathbin{\widehat{+}} A=\{a+a':a,a'\in A,\ a\ne a'\}$. We prove that a proper multiplicative subgroup $H\le\mathbb F_p^*$ cannot satisfy $H=A\mathbin{\widehat{+}} A$ whenever $|H|\ge7$, and that this threshold is sharp. In fact, such a decomposition exists precisely when $|H|\in\{1,3,6\}$, and we classify all decompositions in these exceptional cases. This gives a sharp, complete resolution of the restricted-sumset analogue of the generalized Sárközy conjecture over prime fields. This significantly extends and refines previous results of Shkredov and Yip.

Characterizing when the symbolic and ordinary powers of an ideal coincide is a central problem in commutative algebra, and ideals satisfying this property are called Simis ideals. In this article, we investigate the Simis property of monomial ideals by studying the recent conjecture of Mendez, Pinto, and Villarreal on monomial ideals with minimal irreducible decomposition. Let $I$ be a monomial ideal, and let $\mathcal{F}(I)$ denote the collection of supports of the minimal generators of $I$. Assuming that $\mathcal{F}(I)=\mathcal{F}(\sqrt{I})$, we prove that if $I$ admits more than one minimal generator with a fixed support, then it is not Simis. Using this reduction, we establish the Mendez-Pinto-Villarreal conjecture for two broad classes of monomial ideals, namely support-$3$ monomial ideals and monomial ideals whose associated simplicial complexes are simplicial forests. Finally, we study the Cohen-Macaulay property of monomial ideals whose associated simplicial complexes are grafted and satisfy $\mathcal{F}(I)=\mathcal{F}(\sqrt{I})$.

In this work, we introduce $t$-colorable $k$-plane drawings, that is, drawings of graphs with a $t$-edge-coloring where every edge is crossed by at most $k$ edges of each color. We give tight upper bounds on the edge- and crossing density for small values of $t$ and $k$ and show that the recognition of such drawings is NP-complete if $t\geq 2$ and $k\geq1$.