Papers

We show that there are sets of $n$ points in the plane with $n$ arbitrarily large that contain more than $n^{1.014}$ pairs of points separated by a distance exactly $1$. This improves on very recent work of a team at OpenAI, who proved the same result with an inexplicit exponent greater than $1$, drastically improving on the best previous lower bound and disproving a conjecture of Erdős. The method is number-theoretic, relying on constructing algebraic number fields of large degree and small discriminant with many primes of small norm via a Golod-Shafarevich criterion argument.

If $\Gamma$ is a graph for which every edge is in exactly one clique of order $\omega$, then one can form a new graph with vertex set equal to these cliques. This is a generalization of the line graph of $\Gamma$. We discover many general results and classifications related to these clique graphs that will be useful to researchers studying graphs with this property. In particular, we find bounds on the spectrum of $\Gamma$ (with exact results when $\Gamma$ is $k$-regular) and some complete classifications when $\Gamma$ is strongly regular. We apply our results to derive novel information about the existence questions of certain strongly regular graphs. We also examine the critical group of graphs with this property and their associated transformations. Finally, we discuss examples of widely studied families of graphs that have this property, and provide some examples to make the results more concrete.

A signed graph is a pair $\Gs$ in which $G$ is a finite simple graph and $\sigma:\E(G)\to\{+1,-1\}$ is a signature. Following Máčajová–Raspaud- Škoviera and Jin–Kang–Steffen, a proper coloring of $\Gs$ is a map $c:\V(G)\to\Z$ with $c(u)\ne\sigma(uv)\,c(v)$ for every edge $uv$, and $\Gs$ is \emph{signed $k$-choosable} if such a coloring exists from any list assignment $L$ with $|L(v)|\ge k$. In a celebrated two-page note, Thomassen proved that every planar graph is $5$ choosable, and Jin, Kang, and Steffen subsequently extended this to signed planar graphs. Our principal contribution is a short, self-contained, and signature-blind proof of the latter: the inductive bookkeeping inserts one factor of $\sigma(\cdot)$ uniformly into every constraint, so that with $\sigma\equiv +1$ the argument reduces verbatim to Thomassen's original. From the strengthened extension statement (\cref{thm:main}) we deduce the main result (\cref{thm:JKS}: $\chs\Gs\le 5$ for every planar signed graph), the Máčajová–Raspaud–Škoviera signed Five-Color Theorem in the symmetric palette $\Ns{2}=\{-2,-1,0,1,2\}$, the Switching Invariance Lemma, $3$-choosability of outerplanar signed graphs, $1$-defective signed $4$-choosability of planar signed graphs, a sandwich inequality relating $\chs$ to the unsigned and positive” choice numbers, and a polynomial-time list-coloring algorithm. Voigt's planar non-$4$-choosable graph and Mirzakhani's smaller variant show the bound $5$ is best possible. We close with examples illustrating that negative edges genuinely refine unsigned phenomena, a comparison table situating our work in the literature, and several open problems.

Matrix $B=(b_{ij})$ with $b_{ij}=(2j+1)(2j+2i-1)$ was introduced in \cite{Shi2024} as an additive sieve for odd primes. In this paper we introduce the minimal-anchor function $\pmin(d)$, the least odd prime $p$ such that $p+d$ is prime (sequence A020483 of the OEIS at index $d/2$), whose finiteness for all even $d$ is exactly the weak Polignac (Maillet) conjecture, i.e.\ the statement that every row of $B$ contains a semiprime. We prove that for each fixed $z$ the set $\{d\ \text{even}:\pmin(d)\le z\}$ has density zero, with the asymptotic $(\pi(z)-1)X/\log X$; consequently no fixed finite set of anchor primes can cover a positive proportion of the rows. Density-one coverage of the rows nevertheless holds, by a classical theorem of Lavrik which we restate in the matrix-$B$ framework: almost every row contains the number of semiprimes predicted by the Hardy–Littlewood conjecture. We formulate quantitative conjectures on $\pmin$ and support them with numerical data. Every-row coverage (= weak Polignac) is explicitly left open. We prove unconditional lower bounds for $\pmin$: for every $\psi\to0$, $\pmin(d)>\psi(d)\log d\log\log d$ for almost all even $d$, which is the conjectured typical order; and $\max_{d\le X}\pmin(d)\ge(\frac12+o(1))\log X\log\log X$. The same counting gives the corresponding lower bounds for the least prime in a Goldbach partition.

In this paper, we investigate the combinatorial structure and asymptotic distribution of the solution set of the equation $\sigma(n+1) = k\sigma(n)$ for a given integer $k>1$. From a combinatorial perspective, the solutions to this equation are closely related to the concept of $k$-layered numbers, which are a generalization of Zumkeller numbers. In the analytic section, which constitutes the core of this research, we employ the framework of probabilistic number theory and an extension of the classical Kubilius model to study the oscillatory and local behavior of the sum-of-divisors function. Utilizing the truncation technique for arithmetic functions and applying the Chinese Remainder Theorem, the problem is reduced to a synthetic measure space equipped with independent random variables. Subsequently, by applying the optimized version of the Kolmogorov-Rogozin anti-concentration inequality (Petrov's theorem) to the difference of additive variables and finely tuning the error parameters, we prove that the natural density of this set is zero. The main quantitative outcome of this approach is the derivation of the explicit upper bound $A_k(x) \ll_k \frac{x}{\sqrt{\log \log \log x}}$ for the counting function of the solutions. Finally, alongside the zero asymptotic density, relying on the framework of polynomials and Schinzel's H Hypothesis, we establish the conditional infinitude of the solution set for the case $k=2$ and formulate the existential results.

Cylindric Schur functions are a family of symmetric functions that generalize skew Schur functions. We give a short proof that skew cylindric Schur functions expand positively in terms of non-skew cylindric Schur functions. In particular, we show that the expansion coefficients are fusion coefficients.

Given balls and boxes both enumerated by the positive integers, we consider a sequential allocation of the balls into the boxes. We fix $\ell \ge 2$. Proceeding in increasing order of box labels, assign to each box the next $r$ smallest balls for some $ 1\leq r\leq\ell$. Given an integer $k\ge 3$, is there a natural number $N$ such that in any placement of $N$ balls into boxes, there exist $k$ balls whose labels and box labels each form a $k$-term arithmetic progression? We address this question by identifying abelian power-free fixed points of morphisms over a binary alphabet. We present sufficient conditions under which a morphism is abelian $k$-power-free. Our conditions extend Dekking's result over a binary alphabet and offer a weaker, yet more effective alternative to Carpi's. Combining Dekking's result with the template method of Currie and Rampersad, we develop a sieve technique that significantly reduces the number of parents that must be examined to establish abelian power-freeness. We then identify a binary morphism that is abelian 16-power free (but not abelian $15$-power free) with an abelian 14-power free fixed point, demonstrating the strength of our technique in verifying abelian power-freeness. Furthermore, we give a binary morphism which is not abelian power-free, yet has an abelian $5$-power free fixed point. These results offer novel examples of morphisms whose fixed points exhibit stronger abelian power-freeness than the corresponding morphisms.

We introduce the notion of $p$-adic asymptotics, or $p$-asymptotics, to the context of finite-index subgroup and subalgebra enumeration. For finitely generated groups and finite-dimensional algebras, we connect these asymptotics with the poles of their associated local zeta functions. Our two main results establish the smallest real pole for local zeta functions associated with residually nilpotent algebras, as well as its simplicity and residue whenever this algebra is graded. We thereby provide proof to parts of two conjectures raised by Rossmann and give a precise description of the $p$-asymptotic behaviour inside these algebras.

We define a matroid invariant called the three-cosystole that is related to higher notions of cogirth for weighted matroids, and we prove an optimal upper bound for it in the class of regular matroids of rank at most six. To accomplish this, we show that it is increasing under matroid extensions and then estimate it for each of the maximal simple regular matroids of rank at most six.

We introduce the dual affine Robinson-Schensted correspondence that gives a bijection between the extended affine symmetric group and tuples $(\bar{P},\bar{Q},\lambda,N)$, where $\bar{P}$ and $\bar{Q}$ are tabloids, $\lambda$ is a partition, and $N$ is an integer, subject to compatibility conditions. The construction generalizes Fomin's growth diagrams and Viennot's shadow lines for the classical Robinson-Schensted correspondence on the symmetric group, and is dual to the affine matrix ball construction as well as Shi's correspondence, in the sense that the $P$-tabloids are the same, and the $Q$-tabloids are related by affine evacuation. As a consequence, our construction also parametrizes Kazhdan-Lusztig cells in affine type $A$. We conjecture that the growth diagrams we construct admit a natural geometric realization in terms of relative positions of affine flags, similar to the interpretation given by Steinberg and van Leeuwen in the classical case.

In 1991 Bollobás and Frieze found the threshold for the emergence of a spanning triangulation of a triangle in the binomial random graph, up to a logarithmic factor. In this paper, we find the threshold probability for the emergence of a spanning triangulation of a $k$-gon for any $3\leq k\leq n$, up to a constant factor.

Optimization problems such as the NP-complete 3-SAT provide an important benchmark for the difficult task of finding ground-states in strongly correlated many-body systems with rugged energy landscapes. The study of random 3-SAT problems as Ising spin Hamiltonians in statistical physics has yielded major insights including the existence of a satisfiability phase transition, and the prediction of a critical parameter line of particularly hard instances. Yet, progress on solving those instances has been scarce for several decades. Here, introducing the Target-SAT (TSAT) algorithm, we roughly triple the tractable problem sizes in the hardest regime, with an even greater improvement in a vast range of neighboring regions. By leveraging statistical information hidden in the combinatorial constraints of the problem, TSAT is actively guided in its stochastic local search toward a target within the relevant parameter space. Our analysis also explains why established local search algorithms are limited to relatively small system sizes due to a vast low-energy trap. Furthermore, we characterize the aforementioned critical line in terms of a dominant additional complexity barrier, whose exponential scaling is quickly overcome by TSAT only in the surrounding parameter space. With TSAT, the lead in solving the hardest known random satisfiability problems returns to the realm of stochastic local search algorithms.

What is the maximum, over all 2-colourings of the edges of the $n$-dimensional hypercube $Q_n$, of the minimal number of times a path between a vertex $v$ and its antipode $\bar{v}$ changes colour? A conjecture of Norine, in a form due to Feder and Subi, states that this maximum should be 1. The previous best-known upper bound on the number of colour changes was $(\tfrac{5}{16} + o(1))n$ due to Kirchweger, Peitl, Subercaseaux, and Szeider. We improve this bound and answer a question of Leader and Long by finding a geodesic path with at most $(\tfrac{\pi}{2} + o(1))\sqrt{n}$ colour changes. In fact, we show that this is the expected number of colour changes for a uniformly random start vertex. This is optimal (up to the constant) when the start vertex is chosen uniformly at random.

For any connected complex reductive group $G$ and element $z$ of its Weyl group $W$, we use work of Lusztig and Abreu-Nigro to compute the graded $W$-character of the intersection cohomology of any closed Lusztig variety for $z$ over the regular semisimple locus of $G$. We relate the resulting formula to unipotent Lusztig varieties, giving a new geometric model for unicellular LLT polynomials. We then consider Laurent polynomials $\alpha_{\psi, G}^z$ indexed by irreducible characters $\psi$, encoding how our formula decomposes into ungraded characters arising from the Springer theory of $G$. From evidence in low rank, we conjecture that if $\psi$ is inflated from type $A$ in a particular way, then the nonzero coefficients of $\alpha_{\psi, G}^z$ are positive and unimodal. This offers an answer to a 1993 question of Haiman about generalizing a conjecture he posed for symmetric groups. We also prove that the matrix formed by the $\alpha_{\psi, G}^z$ is partially triangular, and that their positivity and unimodality properties are stable under inclusions of Levi subgroups.

We study $\ell$-colourings of $(v,k,\lambda)$-BIBDs (balanced incomplete block designs) where, within each block, one colour is absent and each of the $\ell-1$ other colours appears exactly $\frac{k}{\ell-1}$ times. We establish several necessary conditions for such colourings to exist. We also use these coloured BIBDs to provide new necessary conditions for the existence of Hadamard matrices, affine planes, and twin prime powers.

We present several short proofs that resolve open problems from the algebraic and enumerative combinatorics literature. First, we consider the echelonmotion operator on modular lattices. We resolve a conjecture of Defant, Jiang, Marczinzik, Segovia, Speyer, Thomas, and Williams and, consequently, obtain a new algebraic bijective proof of a classical result of Dilworth. Second, we consider statistics on parking functions studied by Stanley and Yin and by Hopkins. We prove some conjectures of Hopkins. Third, we consider centralizers in the plactic monoid. We settle two conjectures of Sagan and Wilson. All of these proofs were obtained autonomously by ChatGPT 5.4 Pro.

The set of tritangent planes to smooth tropical space sextic curves has 15 connected components, recording continuous displacements of planes preserving the tritangency condition. These 15 tritangent classes are polyhedral complexes in $\mathbf{R}^3$, and each of them contains the tropicalization of precisely eight tritangent planes to any smooth space sextic curve with the given tropicalization. Prior joint work of the authors with Len confirms that each tropical tritangent plane has 0, 1, 2, 4 or 8 lifts to classical tritangent planes defined over the algebraic closure of the field over which the original algebraic curve is defined. Our main theorem states that when the input classical curve is generic, then only six out of the ten possible partitions of 8 into powers of 2 arise from lifting multiplicities of tritangent classes. Furthermore, we show that these partitions are completely determined by the dimension of a suitable connected subcomplex of the class and the existence of a member with a tropical tangency of a predetermined combinatorial type.

We derive a recursive formula for the moments of the number of flips using a possibly biased coin to produce a prescribed finite binary string $S$ when $S$ is either a run of heads or a run of heads followed by a tails. Our recursive formula involve certain sums, which we simplify by using a one-parameter extension of the well-studied Eulerian number, which belongs to the two-parameter family of numbers introduced by Graham, Knuth, and Patashnik. We also use the Goulden–Jackson cluster method and Faà di Bruno's formula to establish a closed formula for the moments in a more general situation where a die having an arbitrary number of faces with possibly different probabilities is rolled repeatedly until a prescribed finite word occurs.

In 1994, Orlik and Terao introduced a commutative Artinian analog S/I(A) of the Orlik-Solomon algebra of a hyperplane arrangement A to answer a question of Aomoto. A central topic of investigation in the study of Artinian algebras is the Weak Lefschetz Property (WLP). We analyze WLP for the Artinian Orlik-Terao algebra of graphc arrangements. Even for chordal graphs (which give rise to Koszul algebras) WLP sometimes fails; conversely an analysis of the state polytope shows WLP can hold even when WLP fails for all possible initial ideals. More generally, for any algebra with a tensor product decomposition, we construct canonical elements in the kernel of the multiplication map, refining previous results in the literature.

Given a decorated planar graph $(G,\omega)$, where $G$ is a planar graph and $\omega\in H^1(|\mathcal{Q}G|,\mathbb{Z})$ with $\mathcal{Q}G$ the directed medial graph of $G$, we call some angular functions $\omega$-compatible and study two distinct but related directed graphs: $\mathcal{L}(G,\omega)$, which is the directed graph of such functions, and $BMS(G,\omega)$, the directed graph of BMS states which are some pairs of $\omega$-compatible functions plus additional data. We give sufficient conditions for $\mathcal{L}(G,\omega)$ to be a graded distributive lattice, recovering Kauffman's Clock Theorem when $G$ is a knot diagram. We also define a potential on $\mathcal{Q} G$ and associate a representation of the corresponding quiver with potential to every BMS state. Under suitable assumptions, this construction yields an isomorphism between $\mathcal{L}(G,\omega)$ and the lattice of subrepresentations of a maximal representation, generalizing a result of Bazier-Matte–Schiffler.

A linear code is said to be $\Delta$-divisible if the Hamming weights of all its codewords are divisible by $\Delta$. The $p$-adic valuation of a code is defined as the greatest integer $t$ such that the code is $p^t$-divisible. In this paper, we establish a divisibility criterion for trace codes. Specifically, this criterion provides a systematic method to determine the $p$-adic valuation of the associated trace code, thereby extending Ward's classical divisibility criterion from standard generating sets (or matrices) to generalized generator matrices over an extension field. Furthermore, we present two applications of our framework. The first application provides a concise proof of the celebrated divisibility results on semisimple Abelian codes established by Delsarte and McEliece. The second application establishes several explicit lower bounds on the $p$-adic valuation of the number of solutions over $\mathbb{F}_{q^m}$ (where $q = p^e$) to the Artin–Schreier type equation $ f(x_1,\ldots,x_k)=y^q-y $. In particular, under the coprime condition $\left(d,\frac{q^m-1}{q-1}\right)=1$, we determine the exact minimum $p$-adic valuation of the number of solutions when $f$ is restricted to homogeneous polynomials of degree $d$.

Let $F(G)$ be the number of spanning forests in a graph $G$ and $\mathcal{C}(n,d)$ be the set of all connected $d$-regular simple graphs of order $n$. Define $\widehat{f}_{d}=\liminf_{n\rightarrow \infty}\{F(G)^{1/n}:G\in \mathcal{C}(n,d)\}$. Let $n_i$ be the number of vertices of degree $i$ in $G$. In this paper we give two lower bounds for $F(G)$ in terms of $n_i$ in connected graphs whose vertex degrees belong to $\{2,3\}$ and $\{2,3,4\}$, respectively. Furthermore, we determine the exact values of $\widehat{f}_3$ and $\widehat{f}_4$.

In this paper, we develop a geometric framework for matrix rank-metric codes based on generator tensors and their slice spaces. To every nondegenerate matrix rank-metric code, we associate two systems, which translate metric properties of the code into geometric conditions involving intersections with hyperplanes. This leads to a correspondence between equivalence classes of nondegenerate matrix rank-metric codes and equivalence classes of systems, as well as to Delsarte-type incidence identities relating the rank distribution of a code over a finite field to those of its associated systems. As an application, we introduce generalized weights through the notion of evasive systems, study faithful and one-weight codes over finite fields, and recover known bounds and results from the theory of semifields. Finally, we use this framework to associate additive Hamming-metric codes with matrix rank-metric codes and show that several metric properties are preserved under this correspondence.

Skew partial difference sets (skew PDSs) are recently-introduced combinatorial objects closely related to partial difference sets (PDSs). To date, only one construction approach for non-trivial skew PDSs is known, using bent partitions: this produces examples of Latin square type. In this paper we show that these examples are not an isolated phenomenon; we present new constructions for families of skew PDSs using cyclotomy in finite fields. We provide the first constructions for skew PDSs of Paley type, and new constructions for Latin square type (with different parameters to those from bent partitions). Moreover, we show how skew PDSs relate to disjoint and external partial difference families (DPDFs/EPDFs), and provide new cyclotomic constructions of both standard and relative DPDFs and EPDFs.

Unconditional polytopes are convex polytopes that are symmetric with respect to all coordinate hyperplanes and arise naturally from anti-blocking polytopes by reflection. This paper investigates algebraic relations between an anti-blocking lattice polytope and its associated unconditional lattice polytope. We prove that the toric ring of an anti-blocking lattice polytope is normal if and only if the toric ring of the associated unconditional lattice polytope is normal. We also show that the toric ideal of an anti-blocking lattice polytope is generated by quadratic binomials if and only if the same holds for the associated unconditional lattice polytope. As an application, we obtain a graph-theoretic characterization of quadratic generation of symmetric stable set ideals.

Quantum graph homomorphisms, introduced by Mančinska and Roberson, form a natural quantum relaxation of classical graph homomorphisms. Since this relaxation may create new comparabilities, it could in principle collapse antichains and other order-theoretic configurations. We prove that this does not happen: the quantum homomorphism quasi-order of finite directed graphs is countably universal, and the quantum homomorphism quasi-order of finite planar graphs of maximum degree at most $7$ is also countably universal. Consequently, the same universality holds for finite undirected graphs and for the corresponding quotient partial orders. The result is constructive for finite patterns. Given any finite poset $P$, we explicitly construct finite planar graphs $G_p$, $p\in P$, with $\Delta(G_p)\le 7$, such that \[ p\le_P q \quad\Longleftrightarrow\quad G_p\toq G_q. \] For directed graphs, the proof uses disjoint unions of clockwise directed cycles, where quantum and classical homomorphisms coincide. For undirected graphs, the main ingredient is a finite ordered indicator whose terminals are quantum endpoint-forcing. This gives a quantum analogue of the classical ordered-indicator method: the classical endpoint-image condition is replaced by the projection-level vanishing condition \[ F_{a,p}F_{b,q}=0 \] for every illegal ordered terminal pair. The fixed indicator encodes directed-cycle constructions inside planar bounded-degree graphs without creating extra quantum homomorphisms.

Additive combinatorics asks for lower bounds on sumsets and restricted sumsets over finite fields. Central examples are the Cauchy-Davenport theorem and the Erdős-Heilbronn conjecture. In this note, we develop Das's linear algebraic method and give a new elementary proof of the Alon-Nathanson-Ruzsa theorem for restricted sumsets, which implies the Erdős-Heilbronn conjecture. Compared with the classical polynomial method via Combinatorial Nullstellensatz, our proof uses only basic linear algebra over finite fields, including Vandermonde matrices and solvability of linear systems.

A finite word $w$ is called closed if it has length at most 1 or it contains a proper factor that occurs both as a prefix and as a suffix but does not have internal occurrences in $w$. An infinite word $u$ is called closed-rich if the infimum of all possible ratios between the number of closed factors within any factor $w$ of $u$ and square of the length of $w$ exists and is positive. We define this infimum as the closed-rich constant $C_u$ of the infinite closed-rich word $u$. Puzynina and Parshina (2024) proved that infinite closed-rich words exist. In this paper, we study possible values of closed-rich constants of infinite closed-rich words. In particular, we estimate the supremum $C_{sup}$ of the closed-rich constants of infinite closed-rich words: we show that $C_{sup} \leq 0.165952$. Besides that, we study the closed-rich constant $C_f$ of the Fibonacci word $f$ and show that $ 0.09519 \leq C_f\leq 0.10893 $. In particular, this gives a lower bound for $C_{sup}$: $ 0.09519 \leq C_{sup}$.

In 1966, Kleitman determined the maximum size of a family of subsets of $[n]$ with bounded symmetric difference. Liao, Liu and Yan recently established a vector-space analogue in the cases $n=d+1$ and $n>2d$, and asked for the sharp bound in the remaining range. We resolve this problem completely by proving the exact vector-space analogue of Kleitman's theorem for every $n\ge d+1$, and we also determine all extremal configurations. We further develop a stability theory for the vector-space diameter problem. Unlike the Boolean cube, the lattice of subspaces has no translation symmetry, and this makes the stability theory substantially different from its classical counterpart. The geometry of subspace balls leads to two natural notions: canonical stability, which forbids containment only in the canonical extremal configurations, and global stability, which forbids containment in arbitrary balls or adjacent double balls of the corresponding radius. We determine sharp canonical stability in even diameter, sharp canonical and global stability in odd diameter, and prove a nontrivial general upper bound for global stability in even diameter. In particular, these two notions exhibit a sharp parity split: in odd diameter they collapse to the same problem, whereas in even diameter they lead to genuinely different extremal behavior.

Let $k$ be a positive integer. A graph is said to be $(P_2 \cup kP_1)$-free if it does not contain $P_2 \cup kP_1$ as an induced subgraph. Recently, Ota and the author asked whether every 1-tough and $k$-connected $(P_2 \cup kP_1)$-free graph is hamiltonian or the Petersen graph. Note that this problem is affirmative for $k \in \{1,2,3\}$ by the known results. In this paper, we show that for each integer $k \geq 4$, if $G$ is a $1$-tough and $(k-1)$-connected $(P_2 \cup kP_1)$-free graph with $|V(G)| \ge k^2+k+1$ and $\delta(G) \ge k$, then $G$ is hamiltonian. This result implies that the above question is affirmative for large graphs.