Papers

The tournament isomorphism problem is one of the two fundamental bottlenecks to designing better algorithms for the graph isomorphism problem. Though the problem has been investigated for more than five decades, compared to graphs, there are only very few results on the isomorphism problem of tournaments. For most classes of tournaments neither hardness nor polynomial-time solvability is known. Tournaments of bounded VC dimension are such a class for which no results are available, even though the VC dimension is arguably one of the most robust and central notions of combinatorial tameness. Resolving an open problem of Neuen and Grohe, we show that the isomorphism problem for tournaments of VC dimension $d$ can be decided in time $n^{O(d\log d)}$. Consequently, automorphism groups of tournaments of bounded VC dimension can be computed in polynomial time. To this end, we develop a new method to isomorphism-invariantly decompose tournaments. To facilitate recursion, we introduce the notion of a patched tournament and analyze bounded VC dimension in patched tournaments. We design a recursive algorithm that balances the size of the decomposed pieces against their number and makes use of the structure of near twins. In an orthogonal direction, it is known that a hereditary class of tournaments has unbounded VC dimension if and only if it contains all 2-colorable tournaments. As a second result, we show that also this class does not form an obstruction towards polynomial-time isomorphism testing and indeed show that isomorphism of tournaments of bounded chromatic number is polynomial-time decidable.

Let $F:\mathbb{R}^3\to\mathbb{R}$ be a polynomial that is irreducible over $\mathbb{R}$ with $\text{deg} F\geq2$. We prove that, for any finite $X\subset Z(F)$ that does not concentrate on affine lines, \[ E(X)=\#\{(a,b,c,d)\in X^4: a+b=c+d\}\ll_{\text{deg} F,\,\epsilon}(\# X)^{2+\epsilon}. \] In particular, this answers a question of Bourgain and Demeter concerning finite subsets of the unit sphere.

We prove that $N$ points in $\mathbb{R}^3$ determine at least $N^{2/3-o(1)}$ distinct distances.

Let $(a_n)_{n\geqslant 0}$ be a sequence of integers. Its dual sequence $(a_n^*)_{n\geqslant 0}$ is defined by \begin{equation*} a_n^* := \sum_{k=0}^{n} \binom{n}{k}(-1)^k a_k. \end{equation*} Let $p>3$ be a prime. In this paper we mainly investigate congruences modulo $p^2$ involving central binomial coefficients and $p$-adic dual sequences. For example, we prove that for any sequence $(a_k)_{k\ge0}$ of $p$-adic integers, \begin{align*} \sum^{(p-1)/2}_{k=0}\binom{2k}{k}^2\frac{a_{2k}}{16^k}\equiv\left( \frac{-1}{p}\right) \sum_{k=0}^{p-1}\frac{\mathcal{P}_{k}}{16 ^{k}}a_{k}^*\pmod{p^2}, \end{align*} where $(\mathcal{P}_n)_{n\ge0}$ are the Catalan–Larcombe–French numbers given by \begin{equation*} \mathcal{P}_0=1,\quad \mathcal{P}_1=8, \quad n^2 \mathcal{P}_n = 8(3n^2-3n+1)\mathcal{P}_{n-1}-128(n-1)^2\mathcal{P}_{n-2} \quad (n\ge2). \end{equation*} We also establish a new formula for $\sum_{k=0}^{(p-1)/2}\binom{2k}{k}a_{2k}^*/4^k \pmod{p^2}$ and as a consequence we confirm some conjectures of Z.-W. Sun \cite{Sun2014CANT} on the generalized central trinomial coefficients $T_{2k}(b,c)$, i.e., the coefficient of $x^{2k}$ in $(x^2+bx+c)^{2k}$, where $b,c$ are integers.

We generalize intersection numbers for combinatorial designs to designs in finite meet-semilattices satisfying suitable regularity conditions. While designs in regular semilattices go back to Delsarte, our regularity assumptions are weaker than his and need not give rise to an association scheme. In this framework, we extend Mendelsohn's equations, prove a generalized Singleton bound with Steiner systems as equality cases, and determine the block intersection distribution at any block of a Steiner system. In particular, this distribution is independent of the chosen block. Specializing to several classical semilattice families, our results recover a number of well-known distributions in coding and design theory. In the Hamming and the $q$-Hamming (or bilinear forms) schemes, they give the local distance distributions of MDS and MRD codes, respectively. In the Johnson and $q$-Johnson (or Graßmann) schemes, they reproduce the block intersection distribution of classical and $q$-analog Steiner systems, equivalently the distance distribution of diameter-perfect constant-weight codes and diameter-perfect constant-dimension subspace codes. For the $q$-Johnson schemes, to the best of our knowledge, this result is new. As a further illustration, we apply our theory to designs of perfect matchings. Our approach provides a unified treatment of these cases in the strongest form known in the literature, determining the distribution relative to each individual block or codeword, without averaging and without linearity or additivity assumptions. Moreover, it identifies the natural double-counting objects underlying these distributions, leading to formulas in the regularity parameters of the semilattice and avoiding the more cumbersome expressions that arise in eigenvalue-based approaches via the ambient association scheme.

Kelly and Trotter conjectured that dim(P x Q) >= dim P + dim Q - 2 for all finite posets P and Q. We prove the conjecture when dim P = dim Q = 3. This also disproves Trotter's conjecture that, for every 1 <= m <= n, there exist finite posets P and Q with dim P = m, dim Q = n, and dim(P x Q) = n. We further prove that dim(C_k x P) = 4 for every finite poset P with dim P = 3 and every crown C_k with k >= 3. The proof uses the classification of 3-irreducible posets and graphs of critical pairs. For the six infinite noncrown families, we construct explicit non-3-colorable subgraphs. The ten fixed posets are handled by an exhaustive 3-coloring search.

Pavez-Signé [Combin. Probab. Comput. 33 (2024), 121–128] conjectured a Dirac-type condition for spanning $H$-subdivisions and asked whether the subdivision paths can additionally be required to have similar lengths. Lee [European J. Combin. 124 (2025), 104059] resolved the existence conjecture in the stronger setting of digraphs. We answer the length-control question in this stronger directed setting: for every $\varepsilon>0$, there exists a constant $C_0>0$ such that, for every digraph $H$ with $h$ arcs and no isolated vertices, every $n$-vertex digraph $D$ with $n\ge C_0h$ and $\delta^0(D)\ge(1/2+\varepsilon)n$ contains a spanning $H$-subdivision whose subdivision paths have lengths differing by at most one.

We study minimum degree conditions for tight Hamiltonian cycles in uniformly dense $3$-uniform hypergraphs. We prove that for every $d,\alpha>0$, every sufficiently large $(\rho,d)$-dense $3$-graph on $n$ vertices with minimum codegree at least $(1/3+\alpha)n$ contains a tight Hamiltonian cycle. This resolves a problem of Aigner-Horev and Levy in a stronger form, and the constant $1/3$ is asymptotically best possible. We also show that uniform density does not lower the asymptotic vertex-degree threshold: there are $(\rho,d)$-dense $3$-graphs with minimum vertex degree $(5/9-o(1))\binom{n}{2}$ and no tight Hamiltonian cycle. Finally, we construct $(\rho,2-\sqrt{3})$-dense examples with minimum codegree $(2-\sqrt{3}-o(1))n$ and no tight Hamiltonian cycle, answering negatively a question of Araújo, Piga and Schacht.

In this paper, we investigate the eigenvalues of character degree graphs, with particular emphasis on the arithmetic properties of their spectra. First, we study \((n-2)\)-regular character degree graphs of solvable groups and derive an explicit formula for their characteristic polynomials. We show that all their eigenvalues are rational and, consequently, that their splitting field is \(\mathbb{Q}\). We then consider supergraphs obtained by adding edges to these graphs and prove that the corresponding splitting field is a quadratic extension of \(\mathbb{Q}\). Next, using their structural decomposition, we examine a general class of Lewis graphs. For this class, we establish bounds on both the number of irrational eigenvalues and the degree of the associated splitting fields. Finally, we investigate prime character degree graphs of diameter \(3\), focusing on the arithmetic nature of their eigenvalues and the degree of their splitting fields.

As it is stated in "Unsolved problems in combinatorial games" as problem A13, Nim with pass is a difficult problem. Nim was one of the first combinatorial games to be solved but when we introduce a pass the game becomes far more complex. In this article we extend the use of the split sum introduced in "Investigations of Impartial Games With a Pass" and we find cases where the split sum act the same as an classical disjunctive sum. We also introduce generalization of Grundy value for the split sum and find that games of same Grundy values can give very different properties with a split sum.

We study the structure of large $t$-intersecting families. A family of $k$-subsets of an $n$-set is $t$-intersecting if every two of its members intersect in at least $t$ elements. A $t$-intersecting family is non-trivial if no $t$-subset is contained in all its members. We prove several stability results for the seminal Hilton–Milner–Frankl theorem. First, for any fixed $\eta,\varepsilon,\theta\in(0,1)$, we prove that if $k/t\geq1+\eta$ and $n=\Omega(tk^{1+\varepsilon})$, then every non-trivial $t$-intersecting family of size greater than $(1+\theta)|\mathcal{K}|$ is a subfamily of one of the two extremal families in the theorem, where $\mathcal{K}$ is an explicit large non-trivial $t$-intersecting family. The key ingredient in the proof is a removal lemma. We also obtain a classification of all $t$-intersecting families with size bounded below by $|\mathcal{K}|$ minus an explicit lower-order term, provided that $k\geq t+4\geq6$ and $n\geq t+6\cdot\max\{(t+2)^2, k(k-t)\}$. This strengthens results of Cao–Lv–Wang (2021) and Frankl (2025) for a broad range of $k$ and $t$ (for example, when $k-t\geq2\sqrt{t}$). As an application of this classification, we determine the largest $t$-intersecting families for each prescribed lower bound on $t$-diversity not exceeding $t(n-k)$, thereby obtaining $t$-intersection versions of results of Han and Kohayakawa (2017) and Kupavskii (2025). To establish these results, we develop techniques based on the spread approximation method and the $t$-cover method, which may be useful for other intersection problems.

We prove that, for all positive integers $h$ and $t$ and every graph $X$ with $\mathrm{td}(X) \leq h$, there exists a positive integer $c(X,t)$ such that every graph $G$ with $\mathrm{tw}(G) < t$ that excludes $X$ as a topological minor is isomorphic to a subgraph of $H \boxtimes K_{c(X,t)}$ for some graph $H$ with $\mathrm{tw}(H) < 2^{h+1}-1$. This extends a result by Ding and Oporowski (Journal of Graph Theory; 1995), which states that for all positive integers $\Delta$ and $t$, here exists a positive integer $f(\Delta,t)$ such that every graph $G$ with $\mathrm{tw}(G)<t$ and $\Delta(G)\leq\Delta$ is isomorphic to a subgraph of $T \boxtimes K_{f(\Delta,t)}$ for some tree $T$.

Kostant–Kumar modules $K(\lambda,w,\mu)$ are submodules of a tensor product $V(\lambda)\otimes V(\mu)$ of irreducible highest weight modules over a symmetrizable Kac–Moody algebra, indexed by Weyl group elements $w$; their decomposition numbers $c^\nu_{\lambda\mu}(w)$ refine ordinary tensor product multiplicities. We study them module-theoretically. We show that $c^\nu_{\lambda\mu}(w)$ is computed by a natural quotient of the Kostant–Parthasarathy–Ranga Rao–Varadarajan multiplicity space, via orthogonal projection onto a Demazure module. For $\mathfrak{g}$ finite-dimensional semisimple or symmetric Kac–Moody, we present $K(\lambda,w,\mu)$ by generators and relations, extending the presentation of Demazure modules due to Joseph, Polo and Mathieu. We apply the presentation to obtain upper bounds on $c^\nu_{\lambda\mu}(w)$ and to study Schur positivity.

We show that the order dimension of the poset of regions in a simplicial hyperplane arrangement can exceed its rank, answering a question of Reading and Segovia. Examples are Coxeter arrangements \(H_4\) and \(E_6\), with \( \dim W(H_4) \geq 5\) and \( \dim W(E_6) \geq 7\).

Let $n\geq 2$ and let $q$ be an odd prime power. The first aim of this paper is to prove that, for every $E\subset \mathbb{H}_n(\mathbb{F}_q)$ and every $\lambda>0$, the following sharp rich-direction estimate holds \[ \left| \left\{ \vartheta\in D_n: M^{\mathrm{rd}}_{\mathbb{H}_n}\mathbf{1}_E(\vartheta)\geq\lambda \right\} \right| \lesssim_n q^{2n-1}|E|\lambda^{-2n}. \] The second aim is to determine, for every $1\leq u,v\leq\infty$, the sharp exponent of $q$ in the corresponding $\ell^u\to\ell^v$ estimate. More precisely, we prove that \[ A_n^{\mathrm{rd}}(u,v) = \max\left\{ \frac{2n-1}{v},\ 1-\frac1u,\ \frac{2n}{v}-\frac1u,\ 1+\frac{2n}{v}-\frac{2n+1}{u} \right\}. \] The proof combines the polynomial method with multiplicities and a probabilistic covering argument based on the action of the affine symplectic group.

We prove the $p$-Frobenius problems proposed as Conjectures 7.1 and 7.5 developed by T. Komatsu and R. Pandey (Bull. Korean Math. Soc. 2025;62:1397–1409.) for two families of consecutive odd integers. For integers $r,L,n\ge0$, the bounded restricted partition function $p_{\le r}^{(\le L)}(\le n)$ counts partitions of $n$ into at most $r$ parts, each at most $L$. Thus the bounded restricted partition functions $p_{\le 3}^{(\le a)}(\le s)$and $p_{\le 3}^{(\le a+1)}(\le s)$ play central roles in the proofs. Their generating functions are Gaussian polynomials, whose symmetry and unimodality provide a common tool for treating both families.

We disprove Kusner's 1983 conjecture that every equilateral set in $\ell_p^n$ with $2<p<\infty$ has at most $n+1$ points: there exist $58$ points in $\mathbb{R}^{56}$ whose pairwise $\ell_5$ distances are all equal, so the maximum equilateral-set size satisfies $e(\ell_5^{56})\ge58>57$. This is the first equilateral set of more than $n+1$ points in $\ell_p^n$ for any finite $p\ge2$. The construction persists on an open interval of exponents around $5$; since Ge, Xu and Zhou recently proved the conjecture for $2\le p\le4$, the infimum of exponents at which it fails lies in $[4,5)$. The configuration is the unique solution of an explicit polynomial system with rational coefficients in a rational box, established in exact arithmetic.

For a graph $G$, denote by $a(G)$ the number of vertices in the largest induced forest in $G$. The Albertson-Berman conjecture, which had been open since 1979, states that $a(G) \geq \frac{n}{2}$ for every simple planar graph $G$ on $n$ vertices. Although the Albertson-Berman conjecture was recently resolved in the negative by constructing a counterexample with the help of AI, we independently found a counterexample to the Albertson-Berman conjecture without AI and present it in this article. Our counterexample is on $39$ vertices with $a(G)=19$. Finally, we indicate, without a full proof, a variant of this construction with a larger number of vertices, but with a slightly smaller ratio $\frac{a(G)}{n}=\frac{37}{76}$.

A graph $G$ is called Hamiltonian if it possesses a Hamiltonian cycle; and $G$ is called Hamiltonian-connected if it contains a Hamiltonian path between any two distinct vertices. The toughness of a non-complete graph is the minimum ratio of $|S|$ to the number of components of $G-S$ for any cutset $S$. For a given graph $H$, a graph $G$ is called $H$-free if $G$ does not contain $H$ as an induced subgraph. In this paper, for an integer $k\ge 2$, we prove that every $2k$-connected, $1$-tough and $(P_{3}\cup kP_{1})$-free graph is Hamiltonian and every $(2k+1)$-connected $(P_{3}\cup kP_{1})$-free graph with toughness greater than $1$ is Hamiltonian-connected.

Dorbec et al. [SIAM J. Discrete Math., 27 (2013)] conjectured that, for all integers $k\geq1$ and $r\geq3$, every connected $r$-regular graph $G$ of order $n$, other than $K_{r,r}$, satisfies $\gamma_{P,k}(G)\leq n/(r+1)$. After disproving this conjecture, Chen et al.[Graphs Combin., 38 (2022)] proposed a corresponding conjecture for claw-free regular graphs. In this paper, we prove this conjecture: for integers $k\geq\ell\geq1$, every connected claw-free $(k+\ell+1)$-regular graph $G$ of order $n$ satisfies $\gamma_{P,k}(G)\leq n/(k+\ell+2)$, and this bound is tight. Moreover, without the claw-free assumption, we show that, for each fixed integer $k\geq1$, the supremum of $\gamma_{P,k}(G)/\lvert V(G)\rvert$ over all connected $r$-regular graphs $G$ is asymptotic to $(\ln r)/r$ as $r\to\infty$.

We study the Ricci curvature introduced by Lin, Lu, and Yau. A graph is called Ricci-flat if every edge has curvature zero. Lei and Bai classified $5$-regular symmetric Ricci-flat graphs by proving that every such graph is isomorphic to a particular $72$-vertex graph $\RF$, and conjectured that every $5$-regular Ricci-flat graph is either isomorphic to $\RF$ or admits a nontrivial Cartesian product decomposition. In this paper, we disprove this conjecture by constructing an infinite family of connected $5$-regular Ricci-flat graphs, none of which is isomorphic to $\RF$ or admits a nontrivial Cartesian product decomposition. This shows that the conjectured extension of the classification from the symmetric setting to general $5$-regular Ricci-flat graphs fails and that the class of such graphs is substantially richer than previously conjectured. To establish these results, we use an optimal-assignment formulation of Lin–Lu–Yau curvature to verify the Ricci-flatness of the constructed graphs.

A binary constant-weight code is a set of binary words of length $n$ such that each word has exactly weight $w$ and is at least Hamming distance $d$ from every other word in the set. $A(n,d,w)$ denotes the maximum size of a binary constant-weight code with parameters $(n,d,w)$. Using seeded initialization with bit-swap tabu search, we found 124 new constructions that improve existing lower bounds for $A(n,d,w)$. As a corollary of stronger bounds on $A(n,8,8)$ for $n \in \{ 32,33,34,37 \}$, we also improve lower bounds on kissing numbers $\tau_{32}$, $\tau_{33}$, $\tau_{34}$, and $\tau_{37}$.

We prove that there is an absolute constant $c>0$ such that every graph of chromatic number at least $r$ and at most $cr^3\log^2 r$ edges contains at least $\binom r3$ triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any counterexample, an induced subgraph of order $O(r)$ and chromatic number at least $(1-\eta)r$. Second, we prove an order-uniform stability theorem: for every $\beta>0$ there is $\gamma>0$, independent of the constant in the linear order bound, such that every sufficiently large $s$-critical graph $J$ of order $O(s)$ with $\omega(J)\le (1-\beta)s$ has at least $\binom s3+\gamma s^3$ triangles. The proof combines the excess method and the modified-independent-set argument of Fox, Tidor, and Zhang. Third, we prove the exact bound when the graph contains a clique of order at least $(1-\delta)r$. This uses a new dense common-palette list analogue of Harris's edge–triangle estimate: if every list occupies a fixed positive proportion of a common palette, then the edge-triangle coloring bound survives up to a constant factor.

This note records a counterexample to Brenti's 1998 conjecture that the nonzero coefficients of $\widetilde{R}$-polynomials form a log-concave sequence.

With the help of a $_6\phi_5$ summation formula and Guo and Zudilin's method, we shall establish some Dwork-type $q$-supercongruences in this paper. When $q\to1$, these $q$-supercongruences are able to engender the corresponding supercongruences. One of them may be stated as follows: for any prime $p\geq5$ and any positive integer $s$, \begin{align*} &\sum_{k=0}^{p^s-1}(6k-1)\frac{(-\frac{1}{3})_k^3}{(1)_k^3} \equiv 0\pmod{p^{3s}}. \end{align*}

For a finite group $G$, let $\mathsf{d}(G)$ denote the maximum length of a sequence having no nonempty subsequence whose terms can be ordered to have product one. For an odd prime $p$, let $H_{p^3}=\operatorname{UT}*3(\mathbb{F}*p)$. Godara and Sarkar proved $\mathsf{d}(H*{27})=6$ and conjectured $\mathsf{d}(H*{p^3})=3p-3$; in a recent preprint, White proved the next case $\mathsf{d}(H_{125})=12$ and left $18\leq\mathsf{d}(H_{343})\leq24$. We prove $\mathsf{d}(H_{343})=18$. We adopt White's product-one criterion and spread framework and develop a $p=7$-specific direction stratification. An explicit product-one-free sequence gives the lower bound. For the upper bound, we stratify a hypothetical product-one-free sequence of length $19$ by the number of central terms and by the occupied projective directions of its quotient multiset. Supports on at most two directions are excluded by a theoretical argument whose finite auxiliary statements are exhaustively checked; the three-direction case and the case of five central terms are settled by exact finite computations. The remaining thirty strata are encoded by a counterexample-guided SAT procedure. A separately implemented checker verifies all $9{,}920{,}815$ seed cuts and all $27{,}207$ learned cuts, and each final unsatisfiable instance is accompanied by a checked LRAT certificate. A separate implementation-level audit verifies the master encoding, the proof archives, and the lower-bound witness.

For a fixed integer $t\geq 3$, consider families of $t$-mark Golomb rulers whose positive-difference sets are pairwise disjoint and contained in $[1,U]$. Let $P_t(U)$ be the largest number of integers covered by such a family. We determine the threshold for asymptotically complete coverage: \[ P_t(U)=U-o(U) \quad\Longleftrightarrow\quad 3\leq t\leq 5. \] The cases $t=3,4$ follow from the known existence spectra for perfect difference families. For $t=5$, Wild's product construction, in the form recorded by Mathon and applied to perfect families of orders $121$ and $161$, gives a multiplicative semigroup of exact-covering scales; an elementary density lemma on its logarithms then supplies a scale $(1-o(1))U$ below every sufficiently large $U$. For the converse, we give a self-contained one-frequency Fourier obstruction. If $x_0\in(\pi,3\pi/2)$ is the first positive solution of $\tan x=x$ and \[ \gamma_0=-\frac{2\sin x_0}{x_0}=0.4344672564\ldots, \] then, for every fixed $t\geq 6$, \[ \liminf_{U\to\infty}\left(1-\frac{P_t(U)}{U}\right) \geq \frac{(t-1)\gamma_0-2}{2(t-2)}. \] In particular, the forced gap for six-mark rulers is at least $2.1542035\%$. We also prove a discrete small-difference bound which yields a stronger obstruction for every $t\geq14$ and forces a gap of \[ \frac12-\frac1{\sqrt t}-\frac7{8t}+O(t^{-3/2}) \] as $t\to\infty$.

We prove a hitting-time analogue of cutoff for the star transposition shuffle on the symmetric group S_n. Let tau be the first time at which every non-top card has been selected. We show that the shuffle is asymptotically mixed at time tau: more precisely, the total variation distance between the law of Y_tau and the uniform distribution on S_n is at most exp(-(log n)^(1/2+o(1))). Our proof compares the star transposition shuffle with the random transposition shuffle using simultaneous diagonalization of the two transition kernels, and then adapts the hitting-time strategy of Jain and Sawhney. This introduces a technique that can be applied to card shuffles that are not necessarily conjugacy invariant.

Knutson and Tao's hives is a combinatorial model to compute Littlewood–Richardson coefficients. Similar to hives, Speyer introduced skeps and used them to prove a Schur log-concavity conjecture by Lam–Postnikov–Pylyavskyy. We first introduce skew hive and skew skep models, which specialize to both hives and skeps, and use this to prove a skew Schur log-concavity result generalizing Lam–Postnikov–Pylyavskyy conjecture. As a consequence, we obtain some log-concavity results concerning Newell–Littlewood numbers and shadow skew Schur functions. Finally, we explain bijections between (skew) hives, (skew) skeps, and peelable tableaux by Nguyen–Nguyen–Woodruff, answering Speyer's question.

A graph $G$ is perfectly weight divisible if, for every positive integral weight function on $V(G)$ and every induced subgraph $H$ of $G$ with at least one edge, the vertex set $V(H)$ can be partitioned into two sets $A$ and $B$ such that $H[A]$ is perfect and the maximum weight of a clique in $H[B]$ is smaller than the maximum weight of a clique in $H$. Perfect divisibility and its weighted form provide a natural approach to polynomial $\chi$-boundedness. A fork, also known as a chair, is the graph obtained from a claw by subdividing one of its edges once. In this paper, we prove that every fork-free graph is perfectly weight divisible. As a consequence, we confirm a conjecture of Sivaraman that every fork-free graph is perfectly divisible.