Papers

For $r\geq 3$ we denote by $\mathcal{C}(D_r)$ the Cartan matrix of type $D_r$. Recently, Sun and Wang conjectured a Rogers–Ramanujan type identity for the Nahm sum associated with $\mathcal{C}(D_r)^{-1}$ and the zero vector. They further conjecture that there exist $r-1$ companion modular Nahm sums associated with nonzero vectors. We partially prove this conjecture by constructing $\lfloor (r+4)/2\rfloor$ modular Nahm sums for $\mathcal{C}(D_r)^{-1}$. To prove their modularity, we utilize the method of Bailey pairs to establish various Rogers–Ramanujan type identities. In particular, we confirm their conjectural identity.

The vertex arboricity $\mathrm{va}(G)$ of a multigraph $G$ is the minimum number $k$ for which $V(G)$ can be partitioned into $k$ subsets, each of which induces an acyclic subgraph of $G$. By definition, if $\mathrm{va}(G)= k$, then the chromatic number, $\chi(G)$, satisfies $k\leq \chi(G)\leq 2k$. Fundamental results by Borodin from 1976 and Bollobás and Manvel from 1979 imply an analog of Gallai's lower bound on the number of edges in a $(2k-1)$-critical graph. We consider a slight generalization of vertex arboricity in the setting of DP-coloring. Using this framework, we derive lower bounds on the number of edges in graphs critical for vertex arboricity and for list arboricity that are better than Gallai's bound, along with similar bounds in our DP-setting.

Let $\alpha(n)$ denote the length of the shortest non-trivial two-variable law for the symmetric group $S_n$. Buskin's quantitative subgroup-separability argument gives the classical lower bound $\alpha(n)\geq 2n-O(1)$. In this short note we give an improvement by proving that $\alpha(n)\geq \frac52 n-O(1)$.

We associate the Orlik–Solomon sheaf with a finite geometric lattice and compute its sheaf homology. We show that this homology concentrates in top degree, admitting a convolution-type decomposition into a principal ideal OS piece tensoring with a principal filter complement poset homology. Applications to uniform matroids provide interesting representations of symmetric groups.

We initiate the study of the multiplicity of negative one of independence polynomials of graphs. In this article, we simply refer to this as the multiplicity of a graph. As applications, we provide a graph-theoretic description of trees whose independence complexes are contractible, give a new sufficient condition for independence polynomials of graphs to be log-concave, and finally, determine possible pairs $(\operatorname{mult}_{-1}P_G, \alpha(G))$, where $P_G$ denotes the independence polynomial of $G$, and $\alpha(G)$ the independence number. The study of the pairs $(\operatorname{mult}_{-1}P_G, \alpha(G))$ is equivalent to finding all pairs of the numerator degree and denominator degree of the Hilbert series of the edge ideal of $G$. We also use spectral graph theory to obtain results on the multiplicity of line graphs of forests. Finally, we give some translations and applications in combinatorial commutative algebra.

Let $M_k$ denote a matching of size $k$. The classical Erdős matching conjecture asks for the maximum number of edges of an intersecting $r$-graph without $M_k$. The csae for $k=2$, which is known as intersecting $r$-graph, is established by Erdős, Ko and Rado. Hilton and Milner further determine the maximum number of edges of a non-trivial intersecting $r$-graph, where the intersecting $r$-graph $H$ is called non-trivial if $\cap_{e\in E(H)}e=\emptyset$. In this paper, we investigate the spectral analogues of the hpergraph matching problems and intersecting family problems. More precisely, for sufficiently large $n$, we determine respectively the maximum spectral radius of $M_{k+1}$-free and non-trivial intersecting $3$-graphs on $n$ vertices, and characterize the extremal hypergraphs.

We record an explicit counterexample to a refined form of Purdy's inequality for essential hyperplane arrangements in projective three-space. Let $\mathcal{A}$ be an arrangement of $n$ hyperplanes in $\mathbb{P}^3_{\mathbb{C}}$. Let $\ell$ be the number of distinct intersection lines of $\mathcal{A}$, and let $p$ be the number of intersection points, where an intersection point means a point at which at least three hyperplanes meet. The expected inequality is \[ p-\ell+n+2\geq 0. \] The classical obstruction is the rank $2+2$ product arrangement, or dually a configuration of points contained in two skew lines. We explain this obstruction first, and then show that it is not the only one. The reflection-arrangement search leads naturally to a subarrangement of the monomial reflection arrangement of type $G(3,3,4)$. Looking dually, this configuration is not contained in two skew lines, and has \[ f_0(S)=12,\qquad f_1(S)=58,\qquad f_2(S)=43. \] Therefore its dual arrangement has \[ n=12,\qquad \ell=58,\qquad p=43, \] and hence \[ p-\ell+n+2=-1. \] Thus the refined statement excluding only the two-skew-lines obstruction is false.

We generalise the recent two-ends Furstenberg inequality due to Wang and the second author from lines to a family of transversal curves, and give a much simplified proof. As an application, we present a result pertaining to the Fourier decay of fractal measures on convex curves.

Let $G=(V,E)$ be a simple graph of order $n$ and let $\lambda_1(G)\ge \cdots \ge \lambda_n(G)$ be the eigenvalues of its Laplacian matrix. Brouwer conjectured that for every $1\le k\le n$, $\sum_{i=1}^k\lambda_i(G)\le |E|+\binom{k+1}{2}$, which was recently confirmed by Kothari and Tudose. Before Brouwer's conjecture was proved, Lew (JCT-B, 2026) established a weaker form of Brouwer's Laplacian eigenvalue inequality and proposed two conjectures for upper bounds on the sum of the $k$ largest Laplacian eigenvalues, one in terms of the matching number and the other in terms of the vertex-cover number. Using Brouwer's Laplacian inequality, we prove both conjectures.

We provide highly accurate estimations of the 10th through 15th Dedekind Numbers, to a precision of 4 digits for $D(10)$, to 2 digits for $D(15)$. These estimates were obtained using three methods, including pair matching on large quantities of 9-dimensional monotone Boolean functions for $D(10)$, Reference Subsets for $D(10)$, $D(11)$, and $D(12)$. And our best method "Weight Layer Branching" which provided accurate estimates for all $D(10)$ through $D(15)$, strongly improving on the previous best known estimates by Korshunov and Tian-Shun Chen et al. arXiv:2606.09795

In this paper, we prove a conjecture of Andrews and El Bachraoui concerning the parity of certain two-color partitions. Precisely, we show that if the Fourier coefficient $t_o(n)$ of the corresponding $q$-series is odd, then $8n+9$ is represented by the binary quadratic form $x^2+2y^2$.

Fix n >= 2. A set A = {a_0 < a_1 < ... < a_{n-1}} of n residues in Z_N is "valid mod N" if the all-ones multiset is the only size-n multiset drawn from A whose sum is p := sum_i a_i (mod N). For the super-increasing set A = {2^k - 1 : 0 <= k <= n-1} we determine the least valid modulus exactly: N_min(n) = 2^n - 2^floor(log_2 n) for all n >= 2. Both directions of the proof are elementary, resting on a sharp minimal-digit-sum estimate for representations by binary coins, and the full theorem has been machine-checked in Lean 4/Mathlib for all n (https://github.com/jarfo/min-modulus). We conjecture that no size-n residue set admits a smaller valid modulus. This validity condition is exactly what makes the permanent of an n x n matrix equal to a single coefficient of a row-product polynomial modulo x^N - 1, extractable by a size-N discrete Fourier (or number-theoretic) transform; the theorem thus identifies the smallest transform, N ~ 2^n, for which this evaluation is exact. That application – and the resulting common framework for the classical formulas of Ryser and Glynn and this transform – is developed in a companion paper (arXiv:2607.09949).

The Roman Domination Problem (RDP) on a simple, finite, undirected graph \(G=(V,E)\) asks for a labeling function \(f:V\rightarrow\{0,1,2\}\) such that every vertex assigned value \(0\) is adjacent to at least one vertex assigned value \(2\). The objective is to minimize the total weight \(\sum_{v\in V} f(v)\), and this minimum value is called the Roman domination number of \(G\), denoted by \(\gamma_R(G)\). Since the RDP is NP-complete for bipartite graphs, a natural direction is to study its complexity on restricted subclasses of bipartite graphs. The problem remains NP-complete even under strong structural restrictions, such as star-convex and comb-convex bipartite graphs. Therefore, identifying the borderline subclasses where the problem changes from NP-complete to polynomial-time solvable remains an important challenge. In this paper, we investigate the RDP on convex bipartite graphs and on their superclass, chordal bipartite graphs. First, we present a dynamic programming algorithm for convex bipartite graphs. The algorithm uses the interval ordering of one bipartition class and keeps a compact boundary state, which is sufficient to control the domination requirements of both processed and future vertices. This gives an \(O(n^3)\)-time algorithm for computing \(\gamma_R(G)\) on an \(n\) vertex convex bipartite graph. In contrast, we prove that the decision version of the RDP is NP-complete on chordal bipartite graphs by a polynomial reduction from Dominating Set on chordal bipartite graphs. Thus, our results show a clear separation between the tractability of convex bipartite graphs and the hardness of the larger chordal bipartite class.

In this article we study complement ideals, and the dual concept of supplement ideals, in nearrings, both of which are generalizations of the concept of complement in a bounded modular lattice. We prove fundamental properties of complements and supplements in arbitrary nearrings. We then establish Galois connections between the ideal lattices of a nearring and of its matrix nearrings, yielding one-to-one correspondences between their respective complement and supplement ideals. We also define graphs associated with complement and supplement ideals of nearrings and study some of their combinatorial properties such as girth and clique number.

For any $n\in\mathbb{N}=\{0,1,2,\ldots\}$ and $b,c\in\mathbb{C}$, the $n$-th generalized central trinomial coefficient is defined as the constant term in the Laurent expansion of $(b+x+cx^{-1})^n$. In this paper, utilizing the constant term method and generating functions, we prove several congruences concerning generalized central trinomial coefficients. First, we establish a parametric congruence modulo $p^2$, from which several conjectural congruences of Z.-W. Sun follow as special cases. We also prove a Catalan-type congruence modulo $p^2$ and a congruence involving $\binom{3k}{k}T_{3k}(6,1)$ modulo $p$, thereby confirming another two conjectural congruences of Z.-W. Sun.

For a sequence $\mathbf a=(a_0,a_1,\dots)$ we define its dilated Hankel determinant $\ddot{H}_n(\mathbf a)=\det(a_{2i+j})_{0\le i,j\le n-1}$, the minor of the infinite Hankel matrix $(a_{i+j})$ formed from the even-indexed rows and the first $n$ columns. We prove that, for a broad class of sequences, $\ddot{H}_n$ admits a remarkably simple product evaluation. This mirrors the behaviour of the classical Hankel determinant $H_n$, but with two key distinctions: the class of sequences for which such formulas are known is far larger in the classical case; and, whereas $H_n$ enjoys a single universal evaluation – the Heilermann formula via the Jacobi continued fraction – no analogous general method exists for the dilated determinant, which is therefore considerably more challenging. Our evaluations instead rest on six methods developed here, four of general scope and two of a more specialised nature. The cases treated include the factorial numbers, the Catalan and central binomial coefficients; the Euler numbers and a one-parameter secant family; the involution numbers; the Springer numbers along with elliptic and derivative deformations; the reciprocal-sine function, whose evaluation rests on a new Catalan determinant proved by condensation; a Bessel analogue of the Euler numbers; and a multiplicative Bessel family. As an application, we settle a conjecture of Chapoton and the author on the roots of the Poupard and Kreweras polynomials.

We prove that for every Cayley graph $\mathcal{G}$ over any finite abelian group $G$, there is a weighted Cayley graph with $O(\log |G|)$ generators that is a spectral sparsifier for $\mathcal{G}$. This bound is optimal. Applying our bound to the group $G = \mathbb{F}_2^n$, yields, as a corollary, $O(n/\varepsilon^2)$-sized code sparsifiers for $\mathbb{F}_2$-linear codes, improving on the work of Khanna, Putterman and Sudan (SODA'24) who obtained a similar result with an additional $\mathrm{polylog}(n)$ loss. Our proof is strongly inspired by a recent work of Reis and Rothvoss for the construction of $\ell_1$-sparsifiers. Following their work, the abelian Cayley sparsification problem can be reduced to establishing a lower bound for the volume of a certain natural convex body. This volume bound follows from a short, elementary argument that relies on character symmetry.

Ferrers diagram rank-metric codes are rank-metric codes with prescribed support, and their dimension is bounded from above by the Etzion–Silberstein bound. In this paper, we study this problem for block Ferrers diagrams, namely Ferrers diagrams whose dots are grouped into square blocks of a fixed size. Motivated by the diagonal construction for MDS-constructible Ferrers diagrams, we introduce the notion of MSRD-constructibility, where MDS codes on diagonals are replaced by maximum sum-rank distance (MSRD) codes on block diagonals. We show that MSRD-constructible pairs yield optimal Ferrers diagram rank-metric codes over sufficiently large finite fields. We then relate MSRD-constructibility of a block Ferrers diagram to MDS-constructibility of its contraction, proving an equivalence when the distance is compatible with the block size and giving lifting criteria in the general case. As a consequence, we obtain MSRD-constructibility for strictly block-monotone and initially block-convex diagrams. Finally, we prove a reduction to block triangular diagrams and use it to obtain new arbitrary-field cases of the Etzion–Silberstein conjecture for MSRD-constructible block Ferrers diagrams.

We introduce a categorical analogue of weak hypercube representations of finite posets by means of faithful embeddings into categories of subwords of finite words. For finite acyclic categories, we characterize those admitting such a weak subword representation: they are precisely the monic categories whose hom-sets carry a left-compatible local total order. The proof is constructive and gives an explicit word representation. We also introduce a query game for categories, generalizing a Boolean query game for posets, and show how winning sets produce explicit word representations and hence upper bounds for the weak word dimension.

We prove local asymptotics for near-central complex $(p,q)$-binomial coefficient moduli ratios allowing an imaginary parameter perturbation of order $n^{-3/4}$ at a $\sqrt{n}$ length scale from the centre. Moreover, we obtain ratio asymptotics for a smaller imaginary perturbation of order $n^{-5/4}$ at the length scale $n^{3/4}$. These results were obtained by reducing the two-parameter coefficients to just one parameter, giving a branch-free logarithmic representation of the second-order ratio and, hence, uniform complex curvature asymptotes for near-central ratios.

Special sets of the Hermitian surface $\mathsf{H}(3,q^2)$, $q$ odd, were introduced by Shult and Thas (1995) in order to construct new finite generalised quadrangles, yet only one example is known to exist and it gives rise to a classical generalised quadrangle. We show that there can be no other special sets of the Hermitian surface.

The classical notion of metric dimension has led to a wide range of extensions, such as the local, strong, fractional, and k-metric dimensions. This naturally raises the question of whether analogous variants can be formulated and studied within the multiset framework. While some progress has been made, particularly on the local multiset dimension, outer multiset dimension, local outer multiset dimension, and edge multiset dimension, however, the area remains far from fully explored. In this paper, we survey the existing variants and consolidate the results currently available in the literature. Furthermore, we identify several directions for future work.

We define the dual lattice function of a rational polytope $P$ via the discrete Laplace transform of the exponential of its support function. This definition is a discrete analogue of the dual volume function of a polytope that the authors studied in previous work. We show that the dual lattice function is valuative, and by multiplying with the torus form, it becomes the canonical form of the exponential polytope $\mathrm{exp}(P)$ as a positive geometry. This result suggests the study of the class of toric polytopes, which are certain semialgebraic subsets of projective toric varieties. Our work is a first step towards discretization of positive geometries in the simplest case of polytopes.

In 1962, Erdős characterized the maximum size of nonhamiltonian graphs of order $n$ with minimum degree at least $k$. Later, Ning and Peng [Combin. Probab. Comput. 29 (2020) 128-136] extended Erdős's results to the clique condition and provided the maximum clique number for nonhamiltonian graphs of order $n$ with minimum degree at least $k$. Recently, Zhang [European J. Combin. 112 (2023) 103728] determined the maximum number of $s$-cliques in nonhamiltonian graphs with prescribed order and minimum degree. A natural extension is to characterize the maximum number of $s$-cliques under other graph properties. Notably, disjoint path cover problems are closely related to Hamiltonicity. In this paper, we generalize results on Hamiltonicity and establish sufficient conditions for a graph to possess one-to-one, one-to-many and many-to-many $t$-disjoint path covers in terms of the number of cliques and the $\alpha$-spectral radius, respectively. Furthermore, we characterize the extremal graphs that attain these bounds respectively.

The hat guessing number $HG(G)$ of a graph is defined by the following game: each player is placed on a vertex and assigned a hat with one of $k$ colors. Each vertex can see only the hat color of the other vertices it is connected to in $G$. All vertices guess, simultaneously, the color of their own hat. The hat guessing number $HG(G)$ is the largest $k$ such that the players can guarantee that at least one of them guesses correctly. In this paper, we show a general bound on the hat guessing number of a graph $G$ as a function of its order $n$ and its maximum degree $\Delta$. This is the first nontrivial upper bound on $HG(G)$ as a function of $\Delta$ and $n$ when $\Delta \geq \frac{n}{e}$. From this result we also obtain that the hat guessing number of the random graph $G_{n,1/2}$ is at most asymptotically $cn$ for $c\sim 0.809$, and that graphs with maximum degrees of $ (1-\varepsilon )n$ for fixed $\varepsilon>0$ cannot have $HG(G)=(1-o(1))n$.

A subset $S$ of a group $G$ is said to be sum-free (resp. $\Delta$-free) if there are no solutions to $a+b=c$ (resp. $a+b+c=0$) with $a,b,c\in S$. For a convex region $R\subset\mathbb{R}^d$, let $\sigma(R)$ denote the maximal proportion of the volume of $R$ that a sum-free subset of $R$ can occupy. We prove that $\sigma([-1,1]^d)=1/2$. Our proof employs a careful application of the Brunn-Minkowski inequality. Moreover, for the $d$-dimensional Euclidean ball $\mathbb{B}^d(0,1)$, we show that $\sigma(\mathbb{B}^d(0,1))\leq 1/2+o_d(1)$. We present two arguments for this. The first combines some routine harmonic analysis on the sphere with known bounds on values of the ultraspherical polynomials. The second more elementary argument proceeds by establishing that the maximal $\Delta$-free subset of the unit sphere $\mathbb{S}^{d-1}$ occupies $1/2+O(d^{-1})$ of the sphere's surface measure. This answers a question raised by Bukh.

We investigate the minimum size of finite abelian Cayley graphs that admit an isometric embedding of a finite connected graph. While every connected graph on n vertices embeds isometrically into a binary Cayley graph of dimension at most n-1, the smallest possible abelian host has remained largely unexplored. We establish fundamental lower bounds showing that every binary host has dimension at least max(diam(G), floor(log2 n)), whereas every finite abelian host has order at least max(n, 2^diam(G)). Moreover, we prove that the minimum host order equals n if and only if G is itself an abelian Cayley graph. Exact binary dimensions are obtained for several important graph families. Hypercubes, complete graphs of order 2^k, and even cycles attain the lower bound. For stars we prove k_min(K1,q)=floor(log2 q)+1 using maximum sum-free sets, yielding an exponential improvement over the naive and isometric dimensions. For odd cycles we prove k_min(Cm)=m-1 for all m<17 and reduce the general case to a cyclic-interval lemma, showing that the universal upper bound is tight. Our computational contribution is a certified exhaustive census of all 995 connected graphs with 2<=n<=7 vertices under general abelian compactifications. The data reveal an "abelian dividend": 569 graphs (57 percent) admit a strictly smaller abelian host than the best binary host, 707 (71 percent) admit an optimal host containing a cyclic factor Zm with m>2, and only 17 graphs attain the theoretical order floor max(n,2^diam(G)). These results demonstrate that compact non-binary abelian hosts are typical rather than exceptional, while binary hosts remain the universal worst-case construction. 2020 MSC:05C12, 05C25, 05C30, 11B75, 20K01

A set \(\mathcal{G}\) of integers is a \(g\)-Golomb ruler if each positive difference appears at most \(g\) times between any 2 elements of the set, and \(G(g,n)\) denotes the minimum diameter of such a ruler with \(n\) marks. We prove a general lemma for passing from certain modular constructions to ordinary \(g\)-Golomb rulers. The key point is that, in a modular \(g\)-Golomb ruler, no cyclic gap length can occur more than \(g\) times. This gives a larger guaranteed cut than the previous average gap argument. We apply this lemma to cyclic relative difference sets, Singer sets, Ruzsa–Spence rulers, and Paley quadratic residues to provide many competing constructions for \(g\)-Golomb Rulers. A computation on the grid \(1\le g\le500\), \(n=g+b\), \(2\le b\le500\), compares the four resulting construction families.

We study when, and how compactly, a finite connected graph (G) embeds isometrically into a Cayley graph of a finite abelian group. The classical theory of partial cubes answers this for isometric subgraphs of hypercubes through the Djokovic-Winkler relation (\theta); we extend the question to the full family of abelian Cayley graphs, whose hosts may carry composite generators and cyclic factors of any order. We introduce an involutive edge relation (\varphi), defined by two simultaneous distance equalities, which coincides with (\theta) exactly on partial cubes and remains informative beyond them, together with an oriented relation (\Phi) for non-involutive hosts, where generator classes are constrained to be partial permutations rather than matchings.The central result is a quotient labeling theorem: for any partition of the edge set into candidate generator classes, the most generic consistent vertex labeling is the quotient of the free module on the classes by the lattice of signed cycle-class incidences, computed by the Smith normal form; the binary case is its reduction modulo two. We prove that the finest partition always yields an isometric labeling, that compactifying the resulting universal group is itself an instance of the same quotient construction, and that the whole construction is algorithmic and certifiable. Worked examples include the triangle, the Petersen graph (embedding into the Clebsch graph of order 16), the Pappus graph (a 1024-fold compaction), and the diamond (a non-diagonal fold). Sharp dimension bounds and an exhaustive census of small graphs are developed in a companion paper. 2020 MSC: 05C12, 05C25, 20K01, 05C50

We use linear programming to prove a separable version of Ky Fan's majorization relation for a sum of two operators that are each a tensor product of $n$ positive semidefinite operators. We give an example showing that such a relation does not hold in general for sums of three or more tensor products of three or more positive semidefinite operators.