Papers

Given a polynomial ring quotient $R=\mathbb{C}[x_1,\ldots,x_n]/I$ with an action of the symmetric group induced by permuting the variables, a higher Specht basis is a collection of bases for each irreducible $\mathfrak{S}_n$-module in its decomposition that mimics the behavior of the classical Specht polynomial construction in the lowest degrees. Higher Specht bases have now been constructed for the coinvariant ring, the full polynomial ring, the rings $R_{n,k}$ appearing in the $t=0$ Delta conjecture, the hook shape Garsia-Haiman modules, and the two-row Garsia-Procesi modules, and more. We establish a general theory for determining when a higher Specht polynomial is nonzero, and give a proof of a conjectural higher Specht basis for all Garsia-Procesi modules in the cases of three row shapes and hook shapes.

We study a vertex-labeling analogue of the $1$-$2$-$3$ problem and its list version. For a labeling $\ell:V(G)\to\mathbb N$, let $S_\ell(v)=\sum_{w\in N(v)}\ell(w)$. The additive number $\eta(G)$ is the least $k$ for which there exists $\ell:V(G)\to[k]$ such that $S_\ell(u)\ne S_\ell(v)$ for every $uv\in E(G)$, while the list additive number $\eta_\ell(G)$ is the least $k$ such that the same condition can be satisfied from every assignment of $k$-element lists $L(v)\subset\mathbb N$ with $\ell(v)\in L(v)$. We show that for every $k\ge2$, there is a graph $G$ with $\eta(G)=1$ and $\eta_\ell(G)\ge k$. The separation persists at the minimum possible ordinary value for positive-degree regular graphs: there is a regular graph $H$ with $\eta(H)=2$ and $\eta_\ell(H)\ge k$. We also determine a sharp lower bound for $\eta(G)$ in terms of the order and minimum degree of $G$, and show that the unbounded list gap persists at asymptotically extremal density. Finally, for every fixed $k\ge2$, it is NP-hard to distinguish $\eta(G)=2$ from $\eta(G)>k$, even on asymptotically extremal dense graphs. Consequently, $\eta(G)$ admits no polynomial-time constant-factor approximation unless $\mathrm P=\mathrm{NP}$. Together, these results reveal a robust gap phenomenon: the separation between ordinary and list additive labeling persists at the smallest possible ordinary values and even under asymptotically extremal density, while the ordinary parameter itself remains hard to approximate.

We determine a sharp threshold for the adaptable 2-colorability of a random graph equipped with a uniformly random, not necessarily proper, red/blue coloring of the edges. To accomplish this, we characterize a family of subgraphs along with edge colorings whose inclusion or exclusion determines adaptable $2$-colorability. We further show that above the threshold, a long path with alternating edge colors is formed. We use this path to prove the existence of such a subgraph in the supercritical regime. We then provide and prove symmetric bounds on the critical window for $2$-adaptable colorability. Particularly, we prove bounds matching that of the critical windows for the giant component in the Erd$\H{o}$s-R$\'e$nyi random graph model as well as the satisfiability of a random $2$-SAT instance. Finally, we show that below the critical window, the solution space of adaptable $2$-colorings remains connected, that is one can travel from one adaptable $2$-coloring to another by a sequence of $2$-colorings which differ on $O(\log{n})$ many vertices.

Let $G$ be a graph. The circumference of $G$, denoted by $cir(G)$, is the length of a longest cycle in $G$, or zero if $G$ is acyclic. In 1993, Broersma, van den Heuvel, Jung, and Veldman conjectured that, for every $t>0$, there is a constant $A=A(t)>0$ such that every 2-connected $t$-tough graph of order $n$ has circumference at least $A\log n$; the conjecture is recorded as Conjecture~2 in the 2006 survey on toughness by Bauer, Broersma, and Schmeichel. In this note, we confirm the conjecture. More precisely, every 2-connected $t$-tough graph $G$ of order $n$ satisfies $cir(G)\ge \lceil \log_k((k-1)n+1)\rceil$, where $k=\lceil 1/t\rceil+2$. The proof combines Win's bounded-degree spanning tree theorem with the theorem of Briański, Joret, Majewski, Micek, Seweryn, and Sharma that the treedepth of a 2-connected graph is at most its circumference.

Sterboul and Deming gave classical matching-based characterizations of non-Kőnig–Egerváry graphs through flower–posy and blossom-pair configurations. We consider two classical configuration families, denoted \(T\) and \(S\), and introduce a new walk-based family \(J\), based on \(J\)-flowers and \(J\)-posies. Our main result proves that, for every graph \(G\), \[ \SD_T(G)=\SD_S(G)=\SD_J(G). \] Thus the additional flexibility of the \(J\)-framework preserves the set of vertices detected by the classical configurations. The proof is vertex-preserving and passes through strict-Hall structure in traces of \(J\)-posies. As a consequence, every prescribed vertex of a connected matchable strict-Hall graph lies in a rigid \(T\)-posy for a suitable perfect matching, linking the theory naturally with matching-covered graphs.

We introduce the curvature-distortion number, a scale-invariant parameter measuring the least multiplicative spread of positive edge weights required to make a weighted discrete curvature nonnegative everywhere. We develop the theory for Lin–Lu–Yau curvature when the transport distance is the fixed combinatorial graph distance. For trees, the invariant admits an explicit nonlinear fixed-point description, which produces a canonical optimal weight that is unique up to scaling. More importantly, the curvature-distortion number controls the branching topology of the tree: for every finite tree $T$, \[ |B(T)|\le \left\lceil \DN_{\LLY}(T)\right\rceil, \] where $B(T)$ is the set of branch vertices. Thus the amount of weight distortion required to achieve nonnegative curvature imposes a direct quantitative restriction on the topological complexity of the tree. For locally finite infinite trees, finite distortion is classified completely: it occurs precisely for the double ray and for one-ended trees obtained from a finite tree by attaching a single ray. This connection between curvature distortion and tree topology extends naturally to general connected graphs through the subgraph formed by edges lying in no cycle of length $3$, $4$, or $5$. Whenever the curvature-distortion number is finite, this tree-like part is a forest unless the whole graph is a cycle of length at least $6$, and each of its tree components inherits the corresponding distortion and topological bounds. In particular, the tree theory yields complete finite-distortion classifications for graphs of girth at least $6$.

We prove the Tratnik–Ye conjecture that every connected component of a resonance graph of perfect matchings on a closed surface is median whenever the allowed even faces form a proper subset of all faces. The embedding need not be cellular or strong, and the graph need not be bipartite. We also show that the quotient associated with each face is a tree and that these quotients give an isometric embedding of each component into a Cartesian product of trees. This yields a criterion for the facial parity embedding into a hypercube to be isometric.

Gray, Payne, Swisher, and Watson conjectured that, for fixed integers $j \geq 0$ and $k \geq 2$, the number $FD_{j,k}(n)$ of partitions of perimeter $n$ having exactly $j$ part sizes of multiplicity at least $k$ is eventually at least the number $FO_{j,k}(n)$ having exactly $j$ distinct occurring part sizes divisible by $k$. We derive bivariate generating functions for both statistics using the profile-word encoding of a partition. For $k \geq 3$, coefficient extraction shows that fixing $j$ changes the order of the dominant pole but not its location. The corresponding dominant singularities are positive real numbers $\rho_k$ and $\sigma_k$, where $\rho_k$ satisfies $\rho_k+\rho_k^2+\cdots+\rho_k^k=1$ and $\sigma_k$ satisfies $\sigma_k^k=(1-\sigma_k)^{k-1}$. We prove that $\rho_k<\sigma_k$ for every $k \geq 3$. Consequently, $FD_{j,k}(n)/FO_{j,k}(n) \to \infty$ as $n \to \infty$, proving the conjecture and yielding a strict eventual inequality for $k \geq 3$. The case $k=2$ recovers the known exact identity.

We answer in the negative the question of Thomas, recorded by Conley, Conley–Marks–Unger, and Conley–Tamuz, of whether every locally finite Borel graph admits a Borel unfriendly partition. Our counterexample has unbounded degree and is closed on a zero-dimensional Polish space; its connectedness relation is hyperfinite, and its components are bipartite and one-ended. Every unfriendly colouring is proper. Together with a parity obstruction, this rigidity rules out Baire measurable colourings that are unfriendly on a comeager set, and measurable colourings that are unfriendly almost everywhere for a quasi-invariant probability of finite average degree. In the positive direction, a Borel graph of maximum degree at most four admits a Borel unfriendly colouring whenever each component contains a cycle or a vertex of degree at most two. This reduces the Borel problem in maximum degree three to cubic forests and, with a theorem of Conley–Marks–Unger, gives Baire measurable unfriendly colourings for all Borel graphs of maximum degree at most four.

We provide a proof, free of ultrafilters and almost reduction, that every subset of a topological Ramsey space is Ramsey in the Solovay model.

For a vector of positive integers $\mathbf{b} = (b_1,\ldots,b_h)$ with $\gcd(b_1,\ldots,b_h) = 1$, we study sets $A \subseteq \mathbb{N}$ for which every sufficiently large integer has a bounded positive number of representations \[ n = b_1 x_1 + \cdots + b_h x_h \qquad (x_1,\ldots,x_h\in A). \] We prove that such a set exists for every binary vector $\mathbf{b} \neq (1,1)$, and for some general higher-dimensional families, including $\mathbf{b} = (u_1, p^d u_2, \ldots, p^{(h-1)d} u_h)$ where $p\nmid u_1\cdots u_h$.

Let $G$ be a graph and $w_k(G)$ denote the number of walks in $G$ of length $k$. For sequences $a_1, \cdots, a_n$ and $b_1, \cdots, b_n$ of non-negative integers such that $a_1 + \cdots + a_n = b_1 + \cdots + b_n$, we determine a simple necessary and sufficient condition on $a_1, \cdots, a_n, b_1, \cdots, b_n$ for the inequality \[ w_{a_1}(G) \cdots w_{a_n}(G) \geq w_{b_1}(G) \cdots w_{b_n}(G) \] to hold for any graph $G$.

The 1-2-3 Conjecture states that for every graph without isolated edges, there exists an edge-weighting from $\{1,2,3\}$ such that adjacent vertices receive distinct sums of weights on their incident edges. In the sequence variant, adjacent vertices are to be distinguished by the sequences of weights on their incident edges. In this paper, we investigate whether, for every graph without isolated edges and for a fixed proper edge colouring (where colours are interpreted as weights), there exists a global total order of the edges such that the resulting sequences of incident weights distinguish adjacent vertices. For connected graphs, we prove that such an order exists whenever there exist two adjacent vertices that have distinct sets of incident weights. This yields a positive answer for every proper edge colouring of a connected non-regular graph or a connected graph of class two. Moreover, a probabilistic argument gives the same conclusion for connected regular graphs of degree at least six.

Let $c\phi_k(n)$ denote the number of $k$-colored generalized Frobenius partitions of $n$. We prove that, for every $m\geq2$ and every $k\equiv2\pmod{2^m}$, \[ \sum_{n\geq0}c\phi_k(n)q^n\equiv\frac{\varphi(q)\,(q^2;q^2)_\infty}{(q;q)_\infty^2}\sum_{n\geq0}c\phi_{k/2}(n)q^{2n}\pmod{2^m}, \] where $\varphi(q)$ is the classical theta function. For $m=2$ this recovers a congruence of Chan, Wang, and Yang. Applied with $k=18$, we determine $c\phi_{18}(2n+1)$ modulo $16$ completely. In particular, we also prove \[ \sum_{n\geq0}c\phi_{18}(6n+1)q^n \equiv4\sum_{r\in\mathbb{Z}}q^{r(3r-1)/2}\pmod{16}, \] which proves the congruences $c\phi_{18}(30n+19)\equiv c\phi_{18}(30n+25)\equiv0\pmod{16}$ recently conjectured by Das, Nath, and Sarma (2026). It also yields further congruences modulo $16$ and a simple modulo-$8$ characterization that recovers and extends a recent congruence of those authors. As a second application we set $k=10$ and determine $c\phi_{10}(2n+1)$ modulo $8$.

Let $\overline{\mathrm{OPT}}_m(n)$ denote the number of overpartition $m$-tuples of $n$ into odd parts. We prove that for every odd $m\ge1$ and every $i\ge3$, \[\sum_{n\ge0}\Bigl(\overline{\mathrm{OPT}}_m\bigl(2^in\bigr)-\overline{\mathrm{OPT}}_m\bigl(2^{i-1}n\bigr)\Bigr)q^n \equiv 2^{\,i+1}\sum_{k\ge0}q^{(2k+1)^2} \pmod{2^{\,i+2}} .\] Thus $\overline{\mathrm{OPT}}_m(2^in)\equiv \overline{\mathrm{OPT}}_m(2^{i-1}n)\pmod{2^{i+1}}$, with equality of $2$-adic valuations exactly at the odd squares. The proof is elementary and uniform in $m$: a single family of integer polynomials, given by a three-term recurrence, governs every $U$-operator identity involved, and a divisibility statement supplies one power of $2$ per iteration.

We prove that the uniform Turán density of $K_4^{(3)}$ is equal to $1/2$. Kielak, Král', Lamaison, Liu, Shu, and Wu have recently proved the same result using combinatorial methods, while our proof is Fourier-analytic. This result answers a question of Erdős and Sós from the founding 1982 paper on this topic.

We prove a generalized circular rearrangement inequality: among all circular arrangements of a finite collection of positive numbers, the greedy arrangement simultaneously maximizes the sums of products of $k$ consecutive entries for every $k$. This resolves a 2023 conjecture of Holmes-Holroyd-Ramírez and extends the classical circular rearrangement inequality for products of adjacent entries. As an application, we show that the greedy ordering minimizes the speed of a cyclic birth-and-death chain, resolving another conjecture of the same authors.

This paper paper concerns the study of forts, the sets that obstruct zero forcing. We show that every block graph on $n$ vertices has at least $n/3$ minimal forts, extending a recent bound for trees by Cameron and and Li (arXiv:2512.12874). The number of forts, and with it the number of compatible collections, grows exponentially for every tree, every connected non-star graph of bounded degree, and every connected graph of linear minimum degree, answering a question in the negative by Hicks et al. (INFORMS Journal on Computing 2022) for these graph classes. We finish by counting the minimal forts of a tree exactly, in linear time and space.

We prove a strengthening of Füredi's conjecture on strong Bollobás $t$-systems. For nonnegative integers $t$ and $s$, a family of $m\ge2$ pairs of finite sets $(A_i,B_i)$ satisfying $|A_i\cap B_i|\le t$ and $|A_i\cap B_j|>t+s$ for all $i\ne j$ satisfies \[ \sum_{i=1}^{m} \frac{\binom{|B_i|-t+s}{s}} {\binom{|A_i|+|B_i|-2t}{|A_i|-t}}\le1. \] When $s=0$, this is precisely Füredi's conjectured weighted inequality. The proof is based on a local growth inequality for graded exterior ideals, a basis-exchange construction, and a common-section reduction. The same method gives the corresponding inequality for subspaces over arbitrary fields. We also determine a best possible upper bound for the Füredi weight sum, construct equality examples with an arbitrary prescribed number of pairs, and derive further inequalities from two-sided basis exchanges.

For a graph $G$ of order $n$, put $\sigma(G)=(\lambda_1(G)+\lambda_n(G))/n$. We determine the first three largest values of this invariant among nonbipartite distance-regular graphs of diameter three and odd girth at least seven. The unique maximizer is the folded $7$-cube, with value $1/32$; the unique second maximizer is the Odd graph $O_4$, with value $1/35$; and the unique third maximizer is $C_7$, with value $2(1-\cos(\pi/7))/7$. More precisely, every other graph in the class satisfies $\sigma(G)<1/36$. This answers Problem~11 of Abiad, Taranchuk and van Veluw in Electronic Journal of Combinatorics 33(2) (2026), P2.31. The proof combines established local multiplicity and odd-moment bounds: the condition $\sigma(G)\geq1/36$ forces the valency to be at most $182$. An exhaustive certificate using only integer and rational arithmetic then leaves three intersection arrays. The complete certificate is publicly available, and neither a classification of generalized odd graphs nor the $Q$-polynomial property is assumed. The odd-girth theorem gives the same extremal conclusions for connected $\{C_3,C_5\}$-free graphs with at most four distinct adjacency eigenvalues, without assuming regularity.

We make partial progress towards a proof of Conjecture 189 of Written on the Wall II by showing that a connected graph $G$ satisfying $\max\{\mathrm{dist_{even}}(v):v\in V(G)\}\le d_2+1$, where $\mathrm{dist_{even}}(v)$ is the number of vertices at an even distance from $v$ and $d_2$ is the second smallest degree of $G$, is traceable whenever at least one of four conditions holds. These conditions involve the vertex-connectivity, order, and diameter of $G$.

Let $W=W(B_n)$ act diagonally on $\mathfrak{h}\oplus\mathfrak{h}^*$, let $S=\mathbb{C}[\mathfrak{h}\oplus\mathfrak{h}^*]$, let $J\subset S$ be the ideal generated by the $W$-alternating polynomials and $\mathfrak{m}_S$ is the maximal ideal of the origin. For sufficiently large $m$ we compute $q,t$-Fuss-Catalan polynomial $Cat^{(m)}(B_n;q,t):=Hilb(\frac{J^m}{\mathfrak{m}_S J^m})_{det-part}$ and imply $Cat^{(m)}(B_n;1,1)=\binom{n(m+1)}{n}$. For proofs, we work with the $\Gamma$-equivariant Hilbert scheme $Y_n=n\Gamma$-$Hilb(\mathbb{C}^2)$, $\Gamma=\mu_2$ and Haiman-type Koszul complex that defines the punctual locus of $Y_n$. Our formula for $Cat^{(m)}(B_n;q,t)$ is derived from a localization computaion for the Haiman-type Koszul complex.

Identifiability of tensor decompositions is often established through linear-algebraic conditions on the factor families. For nonnegative decompositions, however, positivity provides additional information that is not captured by dimension and independence alone: nonnegative terms cannot cancel, and their supports constrain competing decompositions. We introduce a positive scattering term that quantifies this additional source of identifiability and combine it with the dimension budget underlying the Lovitz–Petrov generalization of Kruskal's theorem. For every subset of components, we obtain two sufficient conditions: a threshold of $2|S|-2$ guarantees minimality and nonnegative rank, while the stronger threshold $2|S|-1$ guarantees uniqueness among nonnegative decompositions of the same length. The key result is a positive splitting inequality for irreducible exchanges of nonnegative rank-one tensors, which combines the dimension constraint with support-induced geometric rigidity. Although the scattering term is defined through an optimization over intermediate factor spaces, we show that its mode costs are exactly $0$, $1$, or $+\infty$, yielding an exact activation characterization in terms of graph connectivity. The resulting criterion can strictly certify sparse nonnegative tensor decompositions beyond the reach of Kruskal and Lovitz–Petrov conditions, including examples for which those conditions fail even after reshaping. In the matrix case, the two criteria reduce respectively to full-rank factorization and two-sided separability.

A rotation system on $n$ elements assigns to each element a cyclic order of the other $n-1$ elements. A four-element subset is non-planar if its induced rotation system cannot be realized by a crossing-free drawing of $K_4$. As a combinatorial strengthening of Hill's conjecture on the crossing number of the complete graph, Archdeacon conjectured that every rotation system on $n$ elements has at least $H(n)=\frac{1}{4} \lfloor\frac {n}{2}\rfloor \lfloor\frac{n-1}{2}\rfloor \lfloor\frac{n-2}{2}\rfloor \lfloor\frac{n-3}{2}\rfloor$ non-planar four-element subsets. We computationally verify Archdeacon's conjecture for $n\leq 10$ and show that every extremal rotation system in these orders is realizable by a simple drawing. With computer assistance, we prove that every rotation system on $n$ elements has at least $(8/9 - o(1)) H(n)$ non-planar four-element subsets. We also present a proof by hand for a weaker lower bound of $(2/3-o(1)) H(n)$. Finally, extending recent work of Felsner on antipodal pairs in drawings, we show that Archdeacon's conjecture holds for antipodally shellable rotation systems.

For a nonzero real polynomial $p$, let $\W(p)$ denote the numerator of its ordinary generating function. We prove that if the coefficients of both $\W(p)$ and $\W(q)$ are nonnegative and log-concave with no internal zeros, then so are the coefficients of $\W(pq)$. This provides an affirmative answer to a question of Brändén, Ferroni, and Jochemko. As applications, we derive corresponding results for finite products and for Cartesian products of lattice polytopes, answering a question of Ferroni and Higashitani.

Let $G$ be a graph and $S\subseteq V(G)$ be a subset of vertices. An $S$-Steiner tree $T$ of $G$ is a tree of $G$ which contains $S$ in its vertex set $V(T)$. Kriesell conjectured that for every $2k$-edge-connected subset $S\subseteq V(G)$ in a finite connected graph $G$, there exist $k$ pairwise edge-disjoint $S$-Steiner trees. This conjecture is false for infinite graphs. We present a version of Kriesell's conjecture with topological $S$-Steiner trees for countable finitely edge-separable graphs and a version with $F$-limits of trees for rayless graphs. We show that if Kriesell's conjecture holds for finite graphs, then it holds for every connected, rayless and finitely edge-separable graph. We also show that every $2k$-edge-connected rayless and finitely edge-separable graph contains $k$ pairwise edge-disjoint spanning trees.

A graph $G$ with 243 vertices is shown having $\gamma(G) = \gamma^{\infty}(G) < \theta(G)$, disproving the Gamma-Theta conjecture for eternal dominating sets.

Let $G$ be a graph with minimum degree $\delta(G)\ge|V(G)|/2$. Can we color the edges of $G$ with red and blue so that every pair of non-adjacent vertices is connected by a path consisting of exactly one red edge and one blue edge? We provide an affirmative answer to this question for a class of graphs that are “close” to a complete balanced bipartite graph or the disjoint union of two cliques of the same order. Surprisingly, our methods extend to a much broader class of graphs with minimum degree slightly above $|V(G)|/2$. Furthermore, we answer an asymptotic version of this question in full, proving that every graph $G$ satisfying $\delta(G)\ge(|V(G)|-1)/2$ has a $2$-edge-coloring such that almost all pairs of vertices are connected by a rainbow path. In addition, we propose a number of related open problems.

The undirected edge geography is a two-player combinatorial game on an undirected graph. The players start at the root vertex and alternately move the root along an incident edge to its other endpoint and then delete that edge. The first player who has no remaining move is the loser. For positive integers $m$ and $n$ where $m\geq 3$, the stacked prism graph is $SP(m,n)=C_m\square P_n$. In this paper, we completely determine the winner of the game on $SP(2m,n)$ for $m\geq 2$ and $SP(m,2)$ for $m\geq 3$, and provide a winning strategy for the winner.

For every $n\geq 3$ and $s\geq 2$, we construct a homogeneous polynomial of degree $n(n+1)/2$ whose Milnor fiber is exactly $2s$-connected and whose rational cohomology contains a strictly defined nontrivial $n$-fold Massey product on classes of degree $2s+1$, implying that the Milnor fiber is non-formal, while attaining the Kato–Matsumoto connectivity bound. Our construction is based on the simplicial multiwedges of the nerve complexes of simple polytopes introduced by Limonchenko, combined with Suciu's realization of weighted homogeneous Milnor fibers. We thereby answer two problems posed by Suciu.