Papers

Assume $G$ is a graph and $k$ is a positive integer. Let $f:V(G)\to \mathbb{N}$ be defined as $f(v)=\min\{k,d_G(v)\}$. If $G$ is $f$-choosable, then we say $G$ is degree-truncated $k$-choosable. The degree-truncated choice number of $G$ is $\operatorname{ch}^{\text{\st{d}}}(G) = \min\{k: G \text{ is degree-truncated $k$-choosable}\}$. For a family $\mathcal{G}$ of graphs, $\operatorname{ch}^{\text{\st{d}}}(\mathcal{G}) = \max\{\operatorname{ch}^{\text{\st{d}}}(G):G \in \mathcal{G}\}$. Let $\mathcal{P}$ denote the family of 3-connected non-complete planar graphs. Richter asked in 2008 whether $ch^{\text{\st{d}}}(\mathcal{P}) \le 6$. In 2025, Zhou, Zhu and Zhu answered this question in negative and proved that $8 \le ch^{\text{\st{d}}}(\mathcal{P}) \le 16$. This result was improved by Jiang, Xu, Xu, and Zhu, who proved that $9 \le ch^{\text{\st{d}}}(\mathcal{P}) \le 12$. In this paper, we further improve the result and prove that $10 \le \operatorname{ch}^{\text{\st{d}}}(\mathcal{P}) \le 11$. We conjecture that $\operatorname{ch}^{\text{\st{d}}}(\mathcal{P}) =10$, and we confirm this conjecture for those planar graphs $G \in \mathcal{P}$ for which the subgraph induced by vertices of degree at least 11 is 4-choosable.

We study non-trivial intersection problems for multi-partite hypergraphs, excluding the usual extremal examples determined by fixed vertices or fixed coordinates. Our first result determines the exact value of the non-trivial $t$-intersection problem in the symmetric product $[n]^r$ for $1\le t\le r-2$ and all $n\ge2$. Frankl and Nie proved a two-candidate formula for sufficiently large $n$ and conjectured it for all $n\ge 2$; our formula shows that the conjectured expression must be enlarged, in small ranges of $n$, by additional ball-type terms arising from the Frankl families. Our second result concerns intersecting families in general products $X_1\times\cdots\times X_r$, where $|X_i|=n_i$, with no common vertex. Let $m_0(1,n_1,\ldots,n_r)$ denote the largest size of such a family. We show that this number is equal to the maximum of $\sum_{X\in \mathcal{D}}\prod_{i\in X}(n_i-1)$ over all downsets $\mathcal{D}\subseteq 2^{[r]}$ such that $\bigcup_{X\in \mathcal{D}}X=[r]$ and no two members of $\mathcal{D}$ have union $[r]$. This finite reduction separates the intersection obstruction from the part sizes and yields explicit fully asymmetric formulas for $r=4,5,6$.

For a finite graph $H$ and a positive integer $h$, the $h$-blowup $H^{(h)}$ of $H$ is the graph obtained by replacing each vertex of $H$ by a set of size $h$ and each edge by a complete bipartite graph between the corresponding sets. We prove that, for every $H$, there exists a constant $h_*(H)$ such that whenever $h\ge h_*(H)$ and $n$ is sufficiently large, every $n$-vertex graph maximizing the number of induced copies of $H^{(h)}$ is a blowup of $H$. This refines the asymptotic result of Hatami, Hirst and Norine and settles the question posed by Bollobás, Egawa, Harris and Jin in 1995.

The goal of this short note is to prove a unified abstract regularity lemma which recovers Szemerédi's graph regularity lemma, Green's arithmetic regularity lemma, and a regularity lemma for Boolean functions as direct corollaries.

Let $G$ be a graph. The spectral radius of $G$ is the largest eigenvalue of its adjacency matrix. A matching of $G$ is a set of disjoint edges of $G$. The matching number of $G$ is the size of a maximum matching (i.e., a matching with maximum edges). The graph $G$ is called maximum matching covered if each edge of $G$ is contained in a maximum matching. In this paper, we give a sharp spectral radius condition for graphs with bounded matching number to be maximum matching covered.

In this work, we propose a novel intrinsic approach to the approximation of ergodic SDEs on Riemannian manifolds, which include Riemannian Langevin dynamics. In opposition to the standard extrinsic approaches such as penalization methods and projection methods, our methodology does not use embeddings or coordinates and only relies on natural geometric operations: geodesics, parallel transport,... We give a criterion for high order of accuracy for the invariant measure, develop new intrinsic numerical methods designed solely for sampling the invariant measure, and derive high order conditions using a new algebraic operation on exotic Lie-Butcher series. In the spirit of the Leimkuhler-Matthews method, our approach prioritizes long time sampling efficiency over finite time accuracy, and outperforms the previous extrinsic and intrinsic approaches in terms of cost for a given accuracy, which we illustrate with several numerical experiments.

In this paper, we prove a generalization of a conjecture of Amdeberhan, Andrews, and Ballantine on double Lambert series. Motivated by a question raised by Cui, Kumar, and Singh concerning the existence of a generalization of this conjecture, we establish an identity in which the coefficients are given by the generalized divisor function $\sigma_k(n)$. As a special case, our result includes the original conjecture.

Let $pp (n)$ denote the number of ways to write $n$ as a sum of primes. In this paper, we show that $$ \log pp (n) \sim 2\pi\sqrt{\frac{n}{3\log n}}\;. $$ While sharper estimates are already known, they rely on highly involved and lengthy proofs. In sharp contrast, our approach uses a short, elementary recipe that easily adapts to yield similar asymptotic estimates for several related, extensively studied problems.

Let $a_L(n)$ be the maximum number of regions into which $n$ lollipops divide the plane. Paulsen introduced a second obstruction for this problem, based on pairs of circles meeting at obtuse angle, in addition to the stem-direction obstruction of Cutler-Karlsson-Sloane. We recast Paulsen's argument as a weighted problem for two graphs: a $K_4$-free graph $D$ of non-close stem pairs and a $K_5$-free graph $E$ of non-intriguing circle pairs. For the total number $C$ of pairwise crossings, $$ C\le 4\binom n2+|D|+|E|+|D\cap E|. $$ Paulsen bounds the final term by $|D|$. We keep the overlap term and analyze near-extremal configurations of $D$ and $E$. This closes all of Paulsen's remaining gaps up to $n=17$, and also closes $n=19$: $$ \begin{array}{c} a_L(0),a_L(1),\ldots,a_L(17)\\ =1,2,10,25,45,71,104,142,186,237,294,356,425,500,580,667,761,859, \end{array} $$ and $$ a_L(19)=1076. $$ The same method gives the one-region gaps $$ 964\le a_L(18)\le965,\qquad 1193\le a_L(20)\le1194. $$

We prove an Erdős-Ko-Rado type extremal result for tilings of a $1 \times n$ chessboard by tiles whose lengths belong to a set $\Lambda$. Two tilings are said to intersect if they contain a tile spanning the same set of squares. We prove that if $1\in\Lambda$, then the maximum size of an intersecting family of tilings is attained by the set of all tilings containing a fixed singleton tile at one of its ends. This result generalizes a theorem of Butler, Horn and Tressler, which is equivalent to the case $\Lambda=\{1,2\}$.

We study the topological zeta function of a loopless matroid $\mathsf{M}$ and its Möbius transform. We provide a novel and manifest description (a “Master Theorem”) for both functions and all of their coefficients, which can be used to give transparent solutions to several open questions and conjectures on topological zeta functions of matroids, even in greater generality than what was anticipated. As applications we solve conjectures of van der Veer (2019), Kutler (2023), and Mengesha, Miranda, and Sun (2026).

This paper considers geometric problems of the following type: given a point set $P \subset \mathbb R^2$, one seeks a large subset avoiding a prescribed geometric configuration. Our main result states that, for any $P \subset \mathbb R^2$, there exists a subset $P' \subset P$ with $|P'| \gg |P|^{1/3}$ such that all of the distances determined by $P'$ are distinct. This improves a result of Charalambides. We make heavy use of a result of Li and Postle concerning the independence number of hypergraphs which satisfy some edge distribution conditions, as well as tools from incidence geometry.

The cycle space of a graph $G$, denoted $\mathcal{C}(G)$, is a vector space over ${\mathbb F}_2$, spanned by all incidence vectors of edge-sets of cycles of $G$. If $G$ has $n$ vertices, then $\mathcal{C}_n(G)$ denotes the subspace of $\mathcal{C}(G)$, spanned by the incidence vectors of Hamilton cycles of $G$. We consider several known sufficient conditions for Hamiltonicity and show that an appropriate and fairly mild strengthening of each such condition in fact ensures the stronger property $\mathcal{C}_n(G) = \mathcal{C}(G)$. In particular, we consider the classical Chvátal-Erdős criterion and prove that (under various additional restrictions) if $n$ is odd and $\kappa(G) \geq c \alpha(G)$, where $c$ is a sufficiently large absolute constant, then $\mathcal{C}_n(G) = \mathcal{C}(G)$. Moreover, considering the McDiarmid-Yolov criterion we prove that if $n$ is odd and $\delta(G) \geq \max \left\{2 \tilde{\alpha}(G) + 9, \tilde{\alpha}(G) + 18 \right\}$, where $\tilde{\alpha}(G)$ is the so-called bipartite independence number of $G$, then $\mathcal{C}_n(G) = \mathcal{C}(G)$. We also prove that if $n$ is odd and $G$ admits $16 \alpha(G) + 12$ pairwise disjoint connected dominating sets, $\mathcal{C}_n(G) = \mathcal{C}(G)$. Finally, we consider an effective Chvátal-Erdős type criterion for bipartite graphs and prove that if $G$ is a balanced bipartite graph on $2n$ vertices, satisfying $\alpha_{\emph{BIP}}(G) \leq 2 \delta(G) - 24$, then $\mathcal{C}_{2n}(G) = \mathcal{C}(G)$.

Demazure weaves are combinatorial representations of maps between Bott–Samelson cells and have been used to construct cluster structures on braid varieties. We show the compatibility of these maps and the resulting cluster structures with the standard Poisson structure on the Bott–Samelson variety. Adding frayed strands to Demazure weaves, we further construct Poisson compatible cluster structures on other affine charts of the Bott–Samelson variety in a manner that transition functions across charts become rational quasi-cluster. The mutation sequences we construct for these quasi-cluster morphisms are closely related to those of Ménard for open Richardson seeds.

Between April 1 and May 15, 2026, a group of 49 mathematicians compiled a dataset of research-level mathematics questions with known answers. Most of the work was done during the three-day workshop Benchmarks in Leipzig with 35 participants at the Max Planck Institute for Mathematics in the Sciences in Leipzig, Germany. We present the resulting collection of 100~questions. We evaluated these questions in three stages: a single attempt by five state-of-the-art LLMs and their predecessors, followed by a 20-runs-per-model evaluation with three of these models, and finally a 3-run attempt with two heavy-thinking models. After Stage 1, 41 questions remained completely unsolved; after Stage 2, this count dropped to 16; and we concluded Stage 3 with only 2 unsolved questions. This demonstrates that the mathematical reasoning capabilities of LLMs are becoming impressive. In September 2026, we added a fourth stage in which the next generation of models attempted all 100 questions once more, after which only 1 question remains unsolved.

We show that for any uncountable cardinal $\kappa$, there is a coloring $c: [\kappa]^2\to \omega$ such that $c''A \otimes B = \omega$ for any $A, B\subseteq \kappa$ of order type $\omega_1$ that are stationary in their common supremum. In particular, the stationary version of Erdős-Rado theorem and the higher dimensional Friedman's property are both inconsistent. We demonstrate that the theorem is optimal in various ways.

We prove that a finite, connected, singly connected, locally convex higher-rank tree whose $1$-skeleton is planar and which is non-degenerate, in the sense that every edge of each colour forms a commuting square with every other colour, has rank at most four. Under these hypotheses this establishes the planarity conjecture stated in \cite{Pask}. The obstruction side of the argument uses only the non-planarity of $K_5$; it makes no appeal to the four-colour theorem. The engine is a monotonicity property of the set of colours emitted at a vertex (“backward propagation”), which forces, in any finite singly connected non-degenerate $k$-graph, a single vertex emitting all $k$ colours; once $k\ge 5$, local convexity manufactures a subdivision of $K_5$ at such a vertex.

The classical problem of Erdős asks for the minimum number of empty convex $k$-gons determined by an $n$-element point set in the plane. The celebrated empty hexagon theorem, proved independently by Gerken and Nicolás, shows that every sufficiently large planar point set contains a $6$-hole, while Horton's famous construction shows the existence of arbitrarily large point sets with no $7$-hole. In this paper, we initiate the study of the maximum number of $k$-holes in planar point sets with no $(k+1)$-hole. More precisely, for each fixed $k\geq 6$, let $h_k(n)$ be the maximum number of $k$-holes determined by a planar point set in general position, of size at most $n$, and with no $(k+1)$-hole. We prove that there are absolute constants $c_1,c_2>0$ such that $(c_1/k)^{\lfloor k/3\rfloor} n^{\lfloor k/3\rfloor} \leq h_k(n)\leq (c_2/k)^{\lceil k/2\rceil} n^{\lceil k/2\rceil}$.

Bowler et al. introduced the concept of torsoids that describes the 1-separations of a directed graph in a canonical way building on previous progress by Lovász. To fully understand the structure of directed graphs with respect to their 1-separations it remains to find a global structure along which the torsoids are arranged. In this paper, we start the investigation of this global structure for a specific class of directed graphs.

We present a short proof that the book Ramsey number $R(B_8,B_{10})$ equals 37. The lower bound $R(B_8,B_{10}) \ge 37$ is already available in the literature, so it is enough to rule out a 37-vertex graph containing neither a copy of $B_8$ nor a copy of $B_{10}$ in its complement. The problem as well as the proof were found with AutoMath, an AI-assisted mathematical discovery workflow developed by the first author. A Lean formalization of the upper-bound argument is available in the accompanying repository.

A subset of the vertex set of a graph is geodetically convex if it contains every vertex on any shortest path between two elements of the subset. The convex hull of a set of vertices is the smallest convex set containing the set. We study two games in which two players take turns selecting vertices of a graph until the convex hull of the jointly unselected vertices is too small. The last player to move is the winner. The achievement game ends when the convex hull of the jointly unselected vertices is not the vertex set. In the avoidance game, the convex hull of the jointly unselected vertices must always be the vertex set. We study the nim-values for several graph families, including cycle graphs, hypercube graphs, complete multipartite graphs, wheel graphs, generalized wheel graphs, and graphs with a unique minimal generating set.

A grand Motzkin path with air pockets is a non-empty lattice path in the first and fourth quadrant of $\mathbb{Z}^2$, starting at the origin $(0,0)$, ending on the $x$-axis, and consisting of up-steps $(1, 1)$, horizontal steps $(1, 0)$, down-steps $(1, -k)$ where $k \geq 1$, and with no consecutive down-steps. A {grand Dyck path with air pockets} is a grand Motzkin path with air pockets that uses no horizontal steps. We present the first known 2-Gray codes for grand Motzkin paths with air pockets. Setting the number of horizontal steps to zero in our algorithm yields the first known 2-Gray codes for grand Dyck paths with air pockets. Our three-stage algorithm generates each path in constant amortized time per string, using $O(n^2)$ memory. We also provide enumeration formulae for grand Motzkin paths and grand Dyck paths with air pockets.

There are $2^{n-1}$ ways to tile a $1 \times n$ rectangle with rectangular tiles (of any length, of course they all must have width $1$), but in how many ways can you tile a $100 \times 100$ checkerboard with such tiles? Neither humankind, nor computer-kind, will (most probably) ever know the exact number. But it is possible to compute these numbers for $m \times n$ rectangular grids, if $m$ is not too big, while $n$ can be as big as one wishes. This was initially done in 1988 by David Klarner and Spyros Magliveras, and beautifully extended, around 2006, by, at-the-time, first-year LSU undergraduate Joshua Smith, in collaboration with his faculty mentor, Helena Verrill. Here we extend this to weighted-counting, also keeping track of the number of tiles (that ranges from $1$ to $mn$), and the number of participating grid-edges (that range from $2m+2n$ to $2mn+m+n$). This quickly leads to statistical analyses (mean, variance, and higher moments) of these quantities. While we admire the clever approaches of Klarner-Magliveras and Smith-Verrill, we use two alternative approaches to the original problem, that are more amenable for deriving these generalizations. At the same time, we illustrate the power and beauty of experimental-yet-rigorous enumerative combinatorics.

This work establishes a bipartite generalization of the Harer-Zagier formula using non-Hermitian Random Matrix Theory. More specifically, we use a decomposition of powers of Ginibre eigenvalues as a superposition of independent point processes to identify all coefficients of the generating function of the genus of a surface obtained by a random bipartite pairing of the sides of one polygon with $kM$ sides and $k$ polygons with $M$ sides.

In this paper, we discuss a family of highly regular graphs, said to be distance-regular. We are particularly interested in the distance-regular graphs with valency three. It is known that there exist exactly 13 such graphs. Let $\Gamma$ denote a distance-regular graph with vertex set $X$. For any vertex $x \in X$, the corresponding Terwilliger algebra $T=T(x)$ is generated by the adjacency algebra $M$ of $\Gamma$ and the dual adjacency algebra $M^*=M^*(x)$ of $\Gamma$ with respect to $x$. It is known that the algebra $T$ is semisimple. By construction, the vector space $V=\mathbb{C}^X$ is a module for $T$, said to be standard. In this paper we have the following goal. For each of the 13 distance-regular graphs $\Gamma$ with valency three, we will decompose the standard module $V$ into a direct sum of irreducible $T$-modules. Using this information, we will work out the dimension of $T$.

We establish the first sharp thresholds for low-degree polynomial tests in planted-vs-planted settings, where the goal is to determine with vanishing error which of two structured planted mechanisms generated the observed data. We prove matching low-degree upper and lower bounds for counting communities in the planted submatrix and planted dense subgraph models. The resulting testing threshold coincides, down to the sharp constant, with the known low-degree recovery threshold. In contrast, the task of weak testing, where the goal is to outperform random guessing, does not have a sharp threshold but rather a smooth transition, which we identify. To prove our results, we develop a framework for planted-vs-planted testing that builds on a latent-variable expansion originating in low-degree recovery and employs new methods to identify and prune non-signal contributions.

A temporal graph is a graph in which every edge carries a non-empty set of time labels, and it is temporally connected if for every two vertices $u$ and $v$, there exists a $u$-$v$-path with non-decreasing time labels. A spanner is a subset of its edges preserving temporal connectivity. Unlike static graphs, temporally connected graphs need not admit sparse spanners; nonetheless, minimizing spanner size is a central and widely studied problem. A particularly intriguing question is whether temporal cliques admit spanners of linear size. Despite considerable effort over the past years, the best known upper bound remained $O(n \log n)$. We finally resolve this question, proving that every temporal clique on $n$ vertices admits a spanner of size $7n$. Moreover, such a spanner can be computed in polynomial time.

This paper is motivated by a broad question about AI-assisted mathematics: can an AI system help discover and certify an explicit bijection between two infinite sequences of complicated combinatorial sets already known to be equinumerous? The challenge is to find a reversible structure explaining that equality uniformly across the sequence. We give an affirmative test case in the setting of a partition problem. Andrews and Dhar introduced two partition families $\mathcal{C}_3(n)$ and $\mathcal{D}_3(n)$, and for "nonexceptional” $n$, they asked for a bijective proof of their equality \[ |\mathcal{C}_3(n)|=\frac{|\mathcal{D}_3(n)|}{3}. \] We prove a residue-class equidistribution theorehm for $\mathcal{D}_3(n)$ that identifies a "canonical third” subset $\mathcal{D}_3^{(0)}(n)\subseteq \mathcal{D}_3(n)$. Answering their question, we construct a bijection \[ \iota_n:\mathcal{C}_3(n)\longrightarrow \mathcal{D}_3^{(0)}(n) \] as a highly structured composition of four maps. AxiomProver autonomously produced and Lean-verified the equidistribution theorem. The bijection was found through human–AxiomProver collaboration, and the theorem was autoformalized and verified by the system.

In this paper, we extend localized Turán theorems to signed graphs and study the corresponding spectral Turán problems. Firstly, we establish a vertex-localized Turán-type inequality for signed graphs and characterize the extremal graphs reaching this bound. Secondly, we derive a sharp upper bound for the largest eigenvalue of a signed graph via localized Turán parameters, and identify the extremal graphs attaining equality. Finally, we generalize a walk-based local spectral Turán inequality to signed graphs. Our results generalize and improve several existing theorems for unsigned and signed graphs.

Using methods from spectral graph theory and semidefinite programming, we obtain sharp spectral bounds for several graph parameters related to distance colorings and packing, including the injective chromatic number, the open packing number, the injective chromatic index, and the strong chromatic index. The new spectral bounds improve several existing combinatorial bounds. Furthermore, we apply the obtained eigenvalue bounds on the first two parameters to estimate the code covering number and the open packing number of hypercubes, obtaining new exact values and strengthened bounds regarding the existing literature. The obtained results illustrate the power of combining spectral and semidefinite programming tools for tackling coloring and packing problems in graph theory and coding theory.