Papers

Let $m,n\geq2$ be integers. We study the least exponent $t_{m,n}$ such that the $m$-fold additive energy of any subset $A$ of the discrete cube $\{0,1,\cdots,n-1\}^d$ in any dimension $d$ satisfies $E_m(A)\leq |A|^{t_{m,n}}$. For every fixed $m$, we obtain the asymptotic formula $$ t_{m,n}=2m-1-(1+o(1))\log_n \frac{(2m-1)^{m-1/2}}{(2m)^{m-1}} \qquad(n\to\infty). $$ For $m=2$, this gives $$ t_{2,n} = 3 - (1+o(1)) \log_n\frac{3\sqrt{3}}{4}, $$ proving a conjecture of the first author.

A family of paths in a graph $G$ strongly separates the edges of $G$ if for every ordered pair of distinct edges $(e,f)$ some path in the family contains $e$ and avoids $f$; the minimum size of such a family is denoted by $\operatorname{ssp}(G)$. Bonamy, Botler, Dross, Naia, and Skokan proved, for every $n$-vertex graph $G$, that $\operatorname{ssp}(G)\le 19n$; Liu, Xu, and Yang recently improved this to $\operatorname{ssp}(G)\le 10n-o(n)$. We prove, for every $n$-vertex graph $G$, that $\operatorname{ssp}(G)\le 7.75n$.

We formulate a version of Schur–Weyl duality for the current Lie algebra $\mathfrak{gl}_V[x,y]=\mathfrak{gl}_V\otimes\mathbb{C}[x,y]$. Under this duality, the Garsia–Haiman modules of the $N!$-conjecture become cyclic and cocyclic $\mathfrak{gl}_V[x,y]$-modules, and we describe them as iterated fusion and cofusion products of tautological $\mathfrak{gl}_V$-modules. We show that Haiman's $N!$-theorem for a diagram is equivalent to the coincidence of the fusion and the cofusion filtrations on the tensor product of the local Weyl modules attached to its rows, and that the fusion and cofusion products of Garsia–Haiman modules are associative. Let $\lambda$ and $\mu$ be Young diagrams obtained by removing two different corners from the same diagram. We construct an iterated fusion product of $S^2V$ with local Weyl modules, which is a quotient of the common quotient of the Garsia–Haiman modules of $\lambda$ and $\mu$, fits into short exact sequences with each of them, and has Butler's intersection polynomial as its character. This gives a representation-theoretic proof of Butler's conjecture. The same construction gives lower bounds for the dimensions in the $N!/k$-conjecture.

The hypersimplex $\Delta_{k,n}$ is the convex hull of all 0/1-vectors of length $ n $ with coordinate sum $ k $. Early conjectured, and Kim proved, a combinatorial formula for the $ h^* $-polynomial of $\Delta_{k,n}$ in terms of hypersimplicial decorated ordered set partitions. In this paper, we refine the Early–Kim formula to the flag $h$-numbers of the alcove triangulation of $\hyp$. We also give a representation-theoretic interpretation of its flag $f$-numbers in terms of Young permutation modules.

We introduce extendable pattern avoidance for alternating sign rectangles (ASRs), the natural rectangular generalization of alternating sign matrices (ASMs). An ASR extendably avoids a pattern $\pi$ if it is the upper left corner of an ASM avoiding $\pi$. For each of the four length-three patterns in the equivalence class $\{312, 132, 213, 231\}$ we establish a complete system of recurrence relations enumerating extendably $\pi$-avoiding ASRs of size $r \times k$ with a prescribed number $d$ of nonempty rows. For $\pi = 312$ we further conjecture a closed-form expression and prove it on several diagonal slices via bijections involving Schröder ballot numbers, refined Schröder numbers and Delannoy paths that do not cross the main diagonal vertically. For ASRs of size $(r-1) \times (r+1)$ extendably avoiding $213$ we give a bijection to little Schröder paths of length $r$. The remaining patterns of length three, $123$ and $321$, are more elusive, mirroring the situation of ASMs.

For a finite poset, we partition the edges of the order polytope and of the chain polytope into classes indexed by the connected convex subsets of the poset, and we establish that corresponding classes have the same cardinality. This yields a closed formula for the common number of edges, and it identifies the bijection of Hibi, Li, Sahara and Shikama, given by them through an explicit formula, as a disjoint union of simple bijections between corresponding classes, which explains why it is a bijection and how it acts on edge directions and lengths. As consequences, the two polytopes have equally many edge directions, with matching multiplicities; the chain polytope has at least as many edges parallel to each coordinate subspace as the order polytope; and the edge lengths of the chain polytope are dominated by those of the order polytope. Strict inequality occurs in the last two comparisons exactly when the poset contains a three-element chain. We discuss implications for linear and convex combinatorial optimization over ideals and antichains. We also express the number of edges in terms of the comparability graph, in a form that extends to stable-set polytopes of arbitrary graphs, give a recursion for series-parallel posets and closed formulas for layered, zigzag and crown posets, characterize the distributive lattices for which the two polytopes are unimodularly equivalent, and demonstrate that, although the two polytopes have the same number of edges, either one can have the larger diameter, by an arbitrary amount; on the other hand, both diameters are bounded by the width of the poset, and they coincide for ordinal sums, series-parallel posets, and zigzag and crown posets.

We formally initiate the study of $\lambda$-fold $(s,t)$ near-factorizations in association schemes. Namely, given an association $(X, \mathcal{A})$, we consider the existence of a factorization of $\lambda(J-I)$ into 01-matrices $S$ and $T$ with the constraint that $S$ and $T$ must belong to the adjacency algebra of $(X, \mathcal{A})$. We establish basic properties of $\lambda$-fold $(s,t)$ near-factorizations in association schemes and calculate bounds for $\lambda$, $s$, and $t$ relative to the order of the association scheme. We completely determine all near-factorizations in symmetric and asymmetric 2-class association schemes. Furthermore, we construct near-factorizations in certain Hamming schemes, cyclotomic association schemes, Schurian schemes on small primitive groups, and the folded cube and halved cube association schemes. Finally, we establish that certain Hamming schemes, Johnson schemes, and Grassmann schemes do not admit a $\lambda$-fold near-factorization.

We show that, in random hypergraphs with several permitted edge sizes, non-uniformity affects existential and algorithmic bounds for 2-colorability (Property B) in fundamentally different ways. Assigning weight $2^{-k}$ to each $k$-edge, we obtain upper and lower bounds in terms of the total edge weight that asymptotically match the uniform bounds as the minimum permitted edge size grows, regardless of how edges are distributed among sizes. We also extend the best-known algorithm for 2-coloring random uniform hypergraphs to the non-uniform setting. With weight $\frac{k}{2^k}$ assigned to each $k$-edge, we construct non-uniform instances whose expected total edge weight per vertex is arbitrarily large, yet the algorithm finds a proper coloring asymptotically almost surely. In the uniform setting, the algorithm fails with high probability once this quantity exceeds a constant. Our construction uses sufficiently separated edge sizes, so that edges of different sizes become relevant at well-separated stages of the execution and their effects are essentially independent.

We study list coloring of common independent sets of two matroids. We construct a graphic matroid $M_1$ and a partition matroid $M_2$ with common chromatic number two and common list chromatic number three, showing that the two parameters need not be equal. This resolves a question raised by Király, later stated as a conjecture by Aharoni, Berger, Guo, and Kotlar. We also show that if two strongly base-orderable matroids are each $2$-colorable, then their intersection is $2$-list-colorable.

The complex of injective words is a cell complex that arises in a number of different areas. It has applications to proving homological stability and to the study of group cohomology, and it is closely related to the random-to-random Markov chain. This complex was first studied by Farmer, who proved it has the homology of a wedge of top-dimensional spheres. Later, Björner and Wachs established its shellability, and Reiner and Webb uncovered its $S_n$-module structure, observing in the process that the rank of its top homology group is the $n$th derangement number. We introduce natural subcomplexes of the complex of injective words by fixing a permutation pattern $\sigma$ and considering only those injective words in the alphabet $\{1,2,\dots,n\} $ that avoid $\sigma$. We prove that such pattern-avoiding complexes are shellable if $\sigma$ begins or ends with its largest or smallest letter, and we construct homology bases for the complexes avoiding such patterns. For patterns of length 3, all of which have this property, we show that the rank of the top homology of the resulting complex is a Riordan number. All but four patterns of length 4 also have this property, and for two of the remaining four patterns, we establish shellability using a different method. We also introduce a technique to use enumerative combinatorics to prove shellability, and we apply it to the complex of separable injective words, thereby deducing shellability in this case. Along the way, we give a combinatorial formula for all of the $h$-numbers in the full complex of injective words as well as for each of the subcomplexes which we prove are shellable. Going in the other direction, we use shellability of complexes of pattern-avoiding injective words to deduce new refined counting formulas for pattern-avoiding permutations.

We study embeddings of factorizations of the $\lambda$-fold complete $h$-uniform hypergraph $\lambda K_m^h$ in factorizations of $\lambda K_n^h$, where $m<n$ and both the source and target degrees may vary by color. From every embedding one can obtain another that minimizes the number of components in every target color without increasing its multiplicity spread. This change also does not increase the sum of any convex function of the edge multiplicities, simultaneously in all colors. For $h=2,3$ we give exact existence criteria for every $m<n$. For $h\ge4$, the necessary divisibility and degree-sum conditions are sufficient once $n\ge(h-1)m$, improving the previously known threshold $n\ge hm$ for color-dependent degrees. In this range we also give exact criteria for connected, simple, and equimultiple target factors. The proofs use a system of integer counts recording the number of added edges of each type. Every system satisfying these equations gives an embedding with the minimum multiplicity spread allowed by

Let $W$ be an irreducible complex reflection group with reflection representation $V$. A $W$-stable, faithful homogeneous system of parameters $\Theta \subseteq \mathrm{Sym}(V^*)$ of common positive degree $p$ is called a posh hsop; $\Theta$ carries a $W$-representation $U$ if $\Theta \simeq U$ as ungraded $W$-modules. We classify the posh pairs $(p,U)$ for which a posh hsop of degree $p$ carrying $U$ exists. Every such $U$ is a Galois twist of $V^*$. Extending work of Ito and Okada, we deduce that the quotient $S/(\Theta)$ is a permutation module for $W$ if and only if $U \simeq V^*$.

In this paper, we study the behavior of biquandle-based invariants of virtual knotoids under their connected sum. We first show that the fundamental biquandle of the connected sum of two virtual knotoids is the pushout of a span in the category of biquandles. By applying the Hom functor to this pushout description, we obtain the correspondence between biquandle colorings of $K_1\# K_2$ and compatible pairs of colorings of summands. This provides a categorical explanation of a known matrix product formula for biquandle counting matrices under connected sum. We then study the behavior of biquandle virtual bracket invariants under connected sum. We show that, for each coloring of the connected sum $K_1\#K_2$ corresponding to a compatible pair of colorings of the summands $K_1$ and $K_2$, the normalized biquandle virtual bracket value factors as the product of the normalized values of the summands. Building on this, we obtain connected-sum formulas for the normalized multiset invariants defined by utilizing biquandle virtual brackets. When the coefficient ring is a number ring, the normalized bracket multisets can be encoded by polynomials and matrices with polynomial entries. We introduce a product $\star$ on monomials and an induced matrix product $\odot$. We then show that the normalized biquandle virtual bracket matrices satisfy \[ \widetilde{\mathcal{M}}_X^{\beta}(K_1\#K_2) = \widetilde{\mathcal{M}}_X^{\beta}(K_1) \odot \widetilde{\mathcal{M}}_X^{\beta}(K_2). \]

Kelly's conjecture asks whether every regular tournament admits a Hamilton cycle decomposition. Motivated by its symmetry-preserving extension, we study cyclic Hamilton decompositions of carousel tournaments. For an odd integer $n$, let \[ T_n=\Cay\left( \mathbb Z_n,\left\{1,2,\ldots,\frac{n-1}{2}\right\} \right) \] be the carousel tournament. We ask whether $T_n$ has a Hamilton decomposition invariant under translation by $1$. Although the answer is immediate when $n$ is prime, composite orders introduce a genuine obstruction: nonunit differences generate short cycles rather than Hamilton cycles. We resolve a general composite-order family by proving that, whenever $n=pq$ for primes $7\le p<q$, the tournament $T_n$ admits a cyclic Hamilton cycle decomposition. The proof combines Hamiltonian difference sequences over prime fields with a matching argument that constructs two base paths with disjoint difference sets in $\mathbb Z_{pq}$. Thus our result gives an infinite family supporting the cyclic, symmetry-preserving extension of the Hamilton decomposition problem for regular tournaments.

We prove that every nonconstant Kazhdan–Lusztig polynomial of a sparse paving matroid has only simple negative zeros. For each rank $d\ge5$, the Kazhdan–Lusztig polynomial of the uniform matroid of rank $d-2$ on $d$ elements strictly interlaces those of all sparse paving matroids of rank $d$ and corank at least two.

Let $V$ be an $n$-dimensional vector space over the finite field $\mathbb F_q$, where $n\ge 2$. It is classical that $q+1$ proper subspaces are necessary and sufficient to cover $V$. We study extremal refinements of this covering theorem. For $1\le m\le q+1$, we determine the maximum possible size of the union of $m$ proper subspaces of $V$, proving that $$ \max_{W_1,\ldots,W_m<V} \left|W_1\cup\cdots\cup W_m\right| = q^{n-2}\bigl(1+m(q-1)\bigr). $$ We also classify all equality cases: for $m\ge 2$, equality holds precisely when the subspaces are distinct hyperplanes containing a common codimension-two subspace. As consequences, we obtain a structural classification of minimum covers of $V$ by proper subspaces and a sharp defect estimate for unions of $q$ proper subspaces. We then introduce basis-blocking families, namely families of proper subspaces whose union meets every basis of $V$. We prove that the minimum size of such a family is $q$ and classify all extremal families of this size. Finally, we establish the affine analogue and give an elementary recognition criterion for extremal families. Together, these results provide a unified extremal-combinatorial description of coverings of finite vector spaces by proper subspaces.

Motivated by parallel developments in ordinary and $\ell$-degree Turán problems, we study the set of $(r-2)$-uniform Turán densities of possibly infinite families of $r$-uniform hypergraphs. We prove that, for all sufficiently large $r$, these densities exhibit a phase transition at $4r^{-r}$, from a countable set of algebraic values below this threshold to the full interval $[4r^{-r},1]$. For every $r\ge3$, the densities below the threshold are exactly the finite-palette Lagrangians in that range, and each is realized by a finite forbidden family. Adapting a method of Pikhurko, we show that, for every $r\ge3$, the set of uniform densities omits continuum many of its limit points below the threshold and is therefore not closed.

We give a self-contained pair-automaton proof of the exact compress-with-another threshold of the corrected Figure 3 family from a recent survey of open problems in synchronizing automata. For every $p \geq 3$, the automaton has $n = 3p$ states and $\mu(q_0) = 4p = 4n/3$. The word $(ba)^p(ab)^p$ attains this value. Two entrance potentials and an excluded region yield the lower bound, with the endpoint exception at $p = 3$ treated explicitly. A separate reset construction proves $\operatorname{rt}(A_p) \leq 3p^2 + 4p - 1$ for every parameter. Reproducible computations verify the transition and entrance identities; the all-parameter results follow from the explicit proofs.

Let $1\le k\le n$ and let $A$ be the adjacency matrix of a uniformly random $d$-regular directed graph on $n$ vertices. Suppose that $\lambda n\le d \le (1-\lambda)n$ for a fixed $0<\lambda\le 1/2$. We show that there exists $c_{\lambda}>0$ depending only on $\lambda$ such that $$ \mathbb{P}[\operatorname{rank}(A)\le n-k]\le 2e^{-c_{\lambda} kn}. $$ This gives a large corank extension of the exponential singularity bound of Jain, Sah, and Sawhney.

We study the dimension defect of finitely many subspaces over an arbitrary field. We derive a symmetric, nonrecursive Grassmann-type formula for the dimension of their sum. The formula expresses the total dimension loss through intersections of a distinguished subspace with partial sums of the remaining subspaces, with coefficients determined by the number of subspaces involved. We also show that the formula admits a Shapley-value interpretation for the associated representable polymatroid. Grouping the correction terms by the number of participating subspaces yields a nonnegative dimension-defect profile. We prove that this profile is monotone and identify its successive gaps with the discrete curvatures of the average-rank profile. These gaps give exact remainders in two-sided defect bounds. Equality in either bound holds precisely when the images of the subspaces in the quotient by their common intersection form an internal direct sum. We also give an exact geometric decomposition of the Kinser slack into nonnegative quotient dimensions and characterize equality. Averaging these slacks over permutations and contractions recovers every defect curvature except the final one; additional representability constraints remain in the individual ordered slacks. Weighted and dual formulas accompany the expansion, and entropy analogues express the defect levels and curvatures as averages of mutual and conditional mutual information, respectively.

For any Galois field $\mathbb{F}_q$ with $q$ elements and any positive integers $m$ and $n$, the directed graph $D(q;m,n)$ has vertex set $\mathbb{F}_q\times\mathbb{F}_q$, and there is an arc from vertex $(x_1,x_2)$ to vertex $(y_1,y_2)$ if and only if $x_2+y_2=x_1^my_1^n$. It was conjectured in earlier work that two digraphs $D(q;m_1,n_1)$ and $D(q;m_2,n_2)$ are isomorphic if and only if there exists an integer $k$ relatively prime to $q-1$ such that $m_2\equiv km_1$ and $n_2 \equiv kn_1$, where both congruences are modulo $q-1$. We prove this conjecture over prime fields and construct an infinite family of counterexamples over extension fields.

In this note, we prove a stronger version of the Kővári-Sós-Turán theorem for partition-wise $k$-stable $r$-hypergraphs. More precisely, we show that for every $k,r\in\mathbb{N}_{\geq 2}$ there is $\eta=\eta(r,k)>0$ such that if $H=(V;E)$ is a partition-wise $k$-stable $r$-uniform $K^{(r)}_{t,\ldots,t}$-free hypergraph with $|V|=n$, then $|E| = O_{r,k,t}(n^{r-\eta})$. Crucially, $\eta$ is independent of $t$. The proof follows the pseudofinite regime used by Chernikov and Starchenko to prove an analogous version of Erdős-Hajnal for stable hypergraphs.

We prove that the resonance of any hyperplane arrangement is separable. Using the main result from arXiv:2512.10160 this proves Suciu's conjecture on the fundamental group of every hyperplane arrangement, in its most effective form.

We prove counting formulae for the number of directed Hamiltonian paths and directed Hamiltonian cycles in any complete multipartite graph. The method is based on a collapsing technique relating general path graphs with coloured vertices to legally coloured path graphs.

We count maximal cylinders on zero holonomy $\mathbb{Z}$-covers of genus $2$ square-tiled surfaces, up to $\mathbb{Z}$-action, obtaining quadratic asymptotics. We also show that the leading term of the asymptotic, called the Siegel-Veech constant, can be recovered via a large-genus approximation by intermediate finite covers. Our work applies to the infinite staircases introduced by P. Hubert and G. Weitze-Schmithüsen. For many members of this family, we explicitly compute the associated Siegel-Veech constants. In particular, we exhibit the first infinite family of examples of zero holonomy $\mathbb{Z}$-cover in which the number of cylinders grows sub-quadratically.

Motivated by the Merino–Welsh conjecture, we consider the smallest $c\ge0$, denoted by $c_*$, for which the inequality $T_M(c,0)T_M(0,c)\ge T_M(1,1)^2$ holds for every loopless and coloopless finite matroid $M$. The counterexamples constructed by Beke, Csáji, Csikvári, and Pituk [Adv. Math. 446 (2024), 109674] give the lower bound $x_0$, where $x_0\approx2.22668$ is the largest real root of the polynomial $x^3-9(x-1)$. Later, Csikvári [European J. Combin. 137 (2026), 104402] improved the known upper bound for this constant to $2.35$ and then conjectured that the above inequality holds at $c=x_0$. This conjecture was recently proved by Liu (2026). We give an alternative direct inductive proof that $c_*=x_0$, without computer-assisted finite verification.

On the set $\mathbb{YF}_n$ of words in $1$ and $2$ with digit sum $n$, we consider the probability distribution $\mu_P$, corresponding to the Plancherel measure on paths in the Young–Fibonacci graph. We study the asymptotics as $n$ grows of the entropy of the distribution $\mu_P$ and of the minimum number of words on which $\mu_P$ is almost entirely concentrated.

The classical Murnaghan-Nakayama rule is a recursive formula for computing the values of complex irreducible characters of the symmetric group $S_n$. Alun Morris proved a recursive formula for evaluating the values of irreducible spin characters of $\widetilde{S}_n$, where $\widetilde{S}_n$ is one of the Schur covers of $S_n$ defined by $\widetilde{S}_n:=\langle t_1,t_2,\cdots,t_{n-1},z\ |\ z^2=1,\ t_i^2=z,\ (t_it_{i+1})^3=z, \ t_it_j=zt_jt_i\ \text{if}\ |i-j|>1\rangle$. A recursive formula for evaluating the values of complex irreducible characters of the wreath product $G\wr S_n$, where $G$ is a finite group, was proved by J. Stembridge. In this article, we state and prove a recursive formula to compute the values of the irreducible spin characters of the wreath product $G\wr \widetilde{S}_n$. For the convenience of implementing these recursive formulas, we extend the notion of 0-1 boundary sequence of a Young diagram to shifted Young diagrams.

Let $G$ be a finite and simple graph without isolated vertices. We investigate the projective dimension of the closed neighborhood hypergraph $\mathcal{N}[G]$ and its relationship with the Castelnuovo-Mumford regularity of the extended bipartite double cover $\mathfrak{B}_e(G)$ of $G$. We establish the general upper bound $\operatorname{prod-dim} (\mathcal{N}[G]) \leq \operatorname{reg}(\mathfrak{B}_e(G))$ for all graphs. Furthermore, we prove that the exact equalities $\operatorname{prod-dim} (\mathcal{N}[G]) = \operatorname{reg}(\mathfrak{B}_e(G)) =\alpha(G)$ hold when $G$ belongs to several prominent graph classes, including König-Egerváry (contains all bipartite graphs), cographs, co-chordal, chordal and comparability graphs, where $\alpha(G)$ denotes the independence number. Our method of proofs relies on connecting algebraic invariants to the underlying combinatorial structure of graphs through covering, domination and matching parameters, together with the use of homology tools.

Given a finite poset $\mathcal P$, its induced saturation number, $\text{sat}^*(n,\mathcal P)$ is the smallest size a family of subsets of $[n]$ can have such that it does not contain an induced copy of $\mathcal P$, but adding any other set to it creates one. The saturation numbers already show a sharp dichotomy – Freschi, Piga, Sharifzadeh and Treglown showed that for any given poset its saturation number is either bounded or at least $2\sqrt n$. The dominant conjecture is that in fact, the saturation numbers are either bounded, or exactly linear. In this paper we show that this dichotomy is true for all posets on at most 4 points. Most of these posets, most notably the butterfly and the diamond, had individually long resisted analysis, and the missing piece which this paper tackles is the poset comprised of a $\mathcal V$ and an isolated point, denoted by $\widehat{\mathcal V}$, for which we show linear saturation. The architecture of the proof uncovers the structure of an arbitrary $\widehat{\mathcal V}$- saturated family, namely an antichain with at most two chains above it, and an upside-down forest below it. Moreover, we anticipate that, at least partially, this structure is relevant to the wider class of posets that contain an isolated point.