Papers

We prove the lower bounds $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$, improving the bounds 134 and 343 listed in the April 2026 revision of Radziszowski's dynamic survey. We give explicit red/blue colorings of $K_{134}$ with no red $K_6$ or blue $K_8$, and of $K_{344}$ with no red $K_8$ or blue $K_{10}$, and verify them with two independently written exhaustive clique checkers. Starting from published colorings, we find these witnesses by adding vertices and repairing the resulting monochromatic cliques through local search. The search uses exact conflict counts, preparation moves aimed at making remaining cliques cheaper to break, and mutations followed by repair. A loss based on the largest monochromatic clique containing each edge yielded a useful intermediate state for the $\mathrm{R}(6,8)$ construction. Guided by the author, an AI coding agent wrote and ran the search code; we describe the methods and document the ancestry of the resulting colorings.

For a graph $G$, let $e(G)$ denote the number of edges of $G$, and let $c(G)$ be the number of distinct cycles in $G$. Morrison, Roberts and Scott asked whether, for every fixed graph $H$ and all large $n$, some $n$-vertex $H$-free graph maximizes both $e(G)$ and $c(G)$. In this paper, we show that the answer is no for every possible chromatic number. Let $T_{n,r}$ be the complete $r$-partite Turán graph on $n$ vertices. We find a constant $\gamma_r>0$ such that if $n$ is sufficiently large and $\mathcal{H}$ is a finite family with $\chi(\mathcal{H})=r+1$ satisfying \[ ex(n,\mathcal{H})<e(T_{n,r})+\gamma_r n, \] then every cycle-maximal $\mathcal{H}$-free graph is edge-extremal, and $\gamma_r$ is best possible.

We prove that for each $d \geq 2$, there exist infinitely many symmetric abstract $d$-rigidity matroids that are not the $d$-rigidity matroid, the $d$-hyperconnectivity matroid, or the $d$-cofactor matroid. When $d=2$, our constructed matroids are pathological, in the sense that they are not contained within any abstract 2-rigidity matroid family. Our construction additionally provides a counter-example to a conjecture of Tyomkyn.

We show that there exists $c > 0$ such that any subset of $\{1,\ldots,N\}$ having size $\gg N / \exp( (\log\log\log N)^c )$ contains a nontrivial pattern of the form $x,x+y,x+2y,x+y^3$. It is the first configuration of complexity strictly greater than $0$, other than refinements of arithmetic progressions, for which quantitative bounds over integers were obtained.

A set of vertices in a digraph is majority-stable if each of its vertices has at most half of its outneighbors in the set. A fractional majority coloring assigns nonnegative weights to such sets, covering each vertex to total weight at least one; its minimum total weight is the fractional majority coloring number. We prove that every finite loopless digraph has fractional majority coloring number at most \(523/140<3.736\), improving the bound \(3.9602\) of Anastos, Lamaison, Steiner and Szabó. Our construction uses exclusive sampling from pairs in random cycle matchings, followed by deletion and a correction on the acyclic remainder. The same approach yields bounds below \(3.430\) for digraphs with a directed cycle factor, \(3.287\) for those with an even cycle factor, and \(3.324\) for tournaments. As a consequence, for every fixed \(\varepsilon>0\), we obtain a randomized \((2.491+\varepsilon)\)-approximation algorithm producing an explicit fractional majority coloring in expected polynomial time. On the complexity side, we prove NP-completeness of deciding whether the fractional majority coloring number equals $3/2$, and establish a multiplicative inapproximability threshold of $72/71$ and an additive upper-estimation threshold of $3/142$. All three results hold for acyclic oriented digraphs with outdegrees zero or two in which every directed path has length at most two.

Let $p_i$ be the $i$th prime, and let $f(N)$ be the largest cardinality of a subset of \[ \left\{\prod_{i=1}^N p_i^{a_i}:0\le a_i<N,\ a_i\in\mathbb{Z}\right\} \] containing no two distinct legs of an integer right triangle. We prove \[ f(N) \ll N^N (\log\log N)^{-1/1296}. \]

It is shown that, as $n\to\infty$, the logarithm of the number of decompositions into cycles of the $n$-dimensional Boolean cube $E^n$ is \[ 2^n(\ln n-1+o(1)), \] and the logarithm of the number of Hamiltonian cycles in $E^n$ is at least \[ 2^{n-1}(\ln n-1+o(1)). \] It is proved that, in $E^n$, every perfect matching whose edges belong to at most $k$ directions can be extended to a Hamiltonian cycle for every $n\geq n_0(k)$.

We introduce a generator-matrix-based geometric approach to the covering radius of $\mathbb F_{q^m}$-linear rank-metric codes. Starting from the $q$-system associated with the code, we define the notion of covering lift and show that the covering radius can be recovered from the hyperplane weights of such lifts. This yields an exact criterion, in terms of the length and effective length of the code, for the covering radius to attain its largest possible value, together with the upper bound $\rho(\mathcal{C})\le \min\{m,n\}-1$ in all remaining cases. We then specialize our approach to $1$-dimensional codes, for which the effective length coincides with the minimum rank distance. In this setting, codes attaining $\rho(\mathcal{C})= \min\{m,n\}-1$ are related to covering lifts that are clubs. More generally, we characterize this case through linear maps into suitable quotient spaces, obtaining equivalent interpretations in terms of generalised evasive subspaces and auxiliary matrix rank-metric codes. These results determine the covering radius for several boundary values of the minimum distance and for all $1$-dimensional codes with extension degree $m\in\{3,4,5\}$. For $m=6$ and every $q$ we provide constructions and, for $q\in\{2,3\}$, computational results showing that $1$-dimensional rank-metric codes with the same length and minimum distance can have different covering radii.

The computation of the vertices of a polyhedron described by a system of linear inequalities is a central problem in polyhedral computation. It is a fundamental step in the conversion between H-representations, by linear inequalities, and V-representations, by vertices and extreme rays. This operation plays an important role both in the study of polyhedra and their combinatorics in mathematics and in applications to software and system verification. We present a certificate-based approach for formally verifying the computation of the vertices of a polyhedron. Given an informally computed list of vertices, our method allows to certify in the proof assistant Rocq that the list is complete, or even exact. The cornerstone of the method is a new completeness criterion based on an abstract simplicial complex that generalizes a triangulation of the normal fan of the polyhedron. A significant advantage over previous approaches is that the usually expensive numerical computations are essentially reduced to membership tests to the polyhedron, while the other steps are cheap combinatorial tests. We implement the certification method and prove its correctness in the proof assistant Rocq. We experiment with it on a variety of polyhedra, including Birkhoff polytopes, cross-polytopes, cubes, permutahedra, hypersimplices, and high-dimensional polytopes involved in the disproof of the Hirsch conjecture. Our experiments show that certification with the Rocq-to-OCaml extracted checker is typically 1.5x to over 5x faster than vertex enumeration by the state-of-the-art informal C implementation lrslib of the reverse search method.

We construct a family of scalar-closed, non-additive maximum sum-rank distance codes (MSRD) by switching norm components of a $\sigma$-rational normal curve and lifting the resulting point set through a linearized Reed–Solomon syndrome map. We characterize the admissible switches by a multiplicative stability condition on the norm classes. In particular, for $1 \leq n_i \leq m$, $N=n_1+\ldots+n_{\ell}$ and $2\leq\delta\leq N-1$, every partition of $\mathbb{F}_q^*$ satisfying a specific condition, referred to as Condition $(\diamond)$, yields a code in $\mathbb{F}_{q^m}^{N}$ of size $q^{m(N-\delta+1)}$ and minimum sum-rank distance $\delta$; the code is non-additive whenever a curve component is retained. For $\ell\geq2$ these appear to be the first non-additive MSRD codes in the literature, all previously known families with more than one block being $\mathbb{F}_q$-linear. Moreover, every code of the family has the same sum-rank weight distribution as an $\mathbb{F}_{q^m}$-linear MSRD code with the same parameters, although the geometry of the switched set distinguishes it from linearized Reed–Solomon codes. In the single-block case, an explicit rank isometry identifies the construction with the cone codes of Durante, Grimaldi and Longobardi.

We introduce an asymmetric variant of a classic problem by Roth about colourings of integers and midpoints. The new problem cannot be solved with the standard approach by Erdös-Sárközy-Sós which uses symmetry. We describe a Fourier Analytic approach which gives asymptotically tight bounds. In the $\mathbb{F}_3^n$ setting, the density increment we show is efficient and together with the Freiman-Ruzsa Theorem provides an affine subspace of near optimal codimension within the distinguished set. This approach adopted to the setting of the integers from $1$ to $N$ via Bohr sets and Bogolyubov-Ruzsa Lemma gives a progression of length being a power of $N$ which only depends on the number of colours. We then use Chang's Lemma and Balog-Szemerédi-Gowers Theorem to further improve the dependence on the number of colours.

In this article, we show that the Sidon subsets of $[N]^d$ are Fourier uniform, and we prove a dense model lemma for Sidon sets. Using these results and a higher-dimensional version of Rado's theorem, we prove that given any partition regular linear equation in $s \geq 5$ variables with nonzero coefficients, and any finite partition of a sufficiently dense Sidon subset $S$ of $[N]^d$, the number of monochromatic solutions to this equation is $\gg |S|^s N^{-d}$ for all large $N$. As a corollary of the Fourier uniformity result, we show that dense Sidon subsets of $[N]^d$ are equidistributed in certain arithmetic and Bohr structures. Our proofs are motivated by the arguments of Ortega and Prendiville.

Let \(b(M)\), \(d(M)\), and \(r(M)\) denote the number of bases, the number of circuits, and the rank of a matroid \(M\), respectively. We prove that every nonempty simple binary matroid with no coloops satisfies \[ 2b(M)\ge(r(M)+1)d(M), \] with equality if and only if \(M\) is isomorphic to the Fano matroid. This confirms a conjecture recorded by Oxley in 1983. For the same class, we prove that deleting any element leaves at least as many bases as there are circuits in the original matroid: \(b(M\backslash e)\ge d(M)\) for every \(e\in E(M)\). We determine all equality cases and deduce a sharp linear lower bound for basis growth under successive series extensions. The main counting step is a joint estimate for the three largest possible circuit sizes, obtained from contraction-normalized fundamental-circuit counts and an exact folded-cube edge correspondence.

Given a pair of complementary subgroups $P$ and $N$ of a finite group $G$, we first discuss how the same type of functions $\mathbb E\colon P\times N\to \mathbb T$, which we call bi-$1$-cocycles, appear naturally in the study of projective representations of $G$ of Heisenberg type and second cohomology of $G$ and of its dual quantum group $\widehat G$. We show then that such representations are irreducible and the corresponding ordinary and dual $2$-cocycles are nondegenerate if and only if the matrix $(\mathbb E(p,n))_{p,n}$ is invertible, if and only if it is Hadamard. We illustrate the result with examples arising from symplectic nilpotent Lie algebras over finite fields with two complementary Lagrangian subalgebras.

For a $t$-graph $F$ and an integer $r\ge t$, the \emph{$r$-augmentation} $F(r)$ is the $r$-graph obtained by adding the same set of $r-t$ new vertices to every edge of $F$. We investigate the behaviour of the \emph{Turán density $\pi(F(r))$}, which is the asymptotically maximum edge density of a large $F(r)$-free $r$-graph, as a function of $r$. Let $H_k^r$ be the $r$-augmentation of the complete $(k-1)$-graph on $k$ vertices; equivalently, $H_k^r$ is the (unique up to isomorphism) $r$-graph with $r+1$ vertices and $k$ edges. This paper determines the Turán density of each $r$-graph $H_k^r$ within a constant factor and estimates the lower bounds on $\pi(H_k^r)$ coming from the circular construction of Sidorenko. In particular, it is shown that if $k/\log r\to\infty$ then $\pi(H_k^r)=(1+o(1))k/r$. Also, we consider augmentations of graphs (that is, the case $t=2$) and prove that $\pi(F(r))\ge(\log r)^{-1-o(1)}/r$ for every 3-chromatic graph $F$, which comes close to the known upper bound $1/r$. Note that, for all other graphs $F$, the function $\pi(F(r))$ is known to be either identically 0 or uniformly bounded away from 0.

We study the combinatorics of the intervals below quasi-Coxeter elements in the absolute order of finite Coxeter groups. In particular, we prove that these intervals are EL-shellable, except possibly for quasi-Coxeter elements of types $E_7$ and $E_8$, and we compute their zeta polynomials. We also show that a total order of the reflections yields an EL-labeling if it does so on all rank-two subintervals, which proves a conjecture of Williams for Coxeter elements. In order to obtain these results, we prove them for the infinite families, and we treat the exceptional types by computer. In addition, we study the related interval monoids, and we find a counterexample to cancellativity for every proper quasi-Coxeter element of type $D_n$ ($n\ge5$), $E_6$, $E_7$, $E_8$; in particular, these monoids do not embed in the corresponding interval groups. This gives a negative answer to a question posed by Baumeister, Holt, Neaime, and Rees.

Erdős and Sós conjectured that every $n$-vertex $3$-uniform hypergraph whose link graphs are all bipartite has at most $(1/4+o(1))\binom n3$ edges. We disprove this conjecture by constructing counterexamples with edge density at least $0.250000356>1/4$ for all sufficiently large $n$.

We give a direct information-theoretic proof of the Plünnecke–Ruzsa inequalities for finite subsets of abelian groups. The argument rests on an elementary coupling inequality proved by maximizing joint entropy, without tensor powers or asymptotic constructions. It also yields Ruzsa's sumset triangle inequality and an extension to non-abelian groups.

Linearized permutation polynomials over finite fields have important applications in coding theory, cryptography, and combinatorics. In this paper, we give an explicit description of the cycle structure of a general linearized permutation polynomial in terms of the Jordan blocks of its Dickson matrix, thereby providing a Dickson-matrix formulation of a question raised by Mullen and Vaughan in 1988. Building on the cycle structure, we establish a matrix-theoretic framework to characterize their parity. For finite fields of characteristic 2, we determine all odd linearized permutation polynomials explicitly. For fields of odd characteristic, we derive parity criteria in terms of the eigenvalue structure of the associated Dickson matrix. Based on the parity criteria, we then give an algorithm for deciding the parity of a given linearized permutation polynomial.

We prove that for every finite connected simple graph $G$ on $n$ vertices with minimum degree $k\geq 2$, there is a coupling of its uniform spanning tree and its random $1$-out subgraph under which the expected number of differing edges is $O(n\log (k)/\sqrt{k})$. More generally, we establish analogous couplings between a wide class of determinantal processes and their corresponding $1$-out processes, including Kalai's determinantal hypertrees, with expected symmetric difference negligible compared to the size of the determinantal set. While the graphical case admits a surprisingly short and elegant proof, the more general result requires establishing an asymptotic equipartition property for the determinantal measures in this class, from which we also derive exponential growth rates for the homology torsion of determinantal hyperforests in higher-dimensional regular high-degree complexes.

The Bermond–Thomassen Conjecture asserts that every digraph with minimum out-degree at least $2k-1$ contains $k$ disjoint directed cycles; it remains open in general. We asymptotically resolve it: there exist an absolute constant $K$ and a function $g(k)=o(k)$, independent of $n$, such that every $n$-vertex finite simple loopless digraph with minimum out-degree at least $2k+g(k)$ contains $k$ disjoint directed cycles for all integers $k\ge K$ and $n\ge1$. In fact we obtain the explicit error term $g(k)=O(k^{3/4}\sqrt{\log k})$.

We prove the sign-pattern and limiting-transition assertions of the Berkovich–Dhar conjecture modulo five, covering both the square and the cube of the finite Borwein product. In each power, the coefficients in residue class zero are strictly positive, while the sequences in residue classes three and four have exactly one positive-to-negative sign change after zero terms are omitted. We determine all four transition constants, correct the preliminary numerical estimates in the conjecture, and give their linear corrections with explicit bounded errors. A common four-arc expansion governs both powers. Near each vanishing amplitude, strict negativity of a weighted adjacent difference determines the transition. The cubic case also has two identically vanishing components in the infinite product; a shifted saddle expansion resolves the resulting finite-product boundary terms. Positive series identities, uniform remainder estimates, and an exact integer recurrence complete the proof for every positive integer.

The (global) average order of dominating sets of a graph is the average number of vertices of its dominating sets. Analogously, the local average order of dominating sets is the average number of vertices of its dominating sets containing a fixed vertex. In this paper, we show that the local average order of dominating sets of a graph with $n$ vertices is at least $\frac{n+1}{2}$, with equality if and only if the degree of the fixed vertex is $n-1$. Furthermore, for a graph on $n$ vertices without isolated vertices, we show that $\frac{5n-1}{6}$ is an upper bound for the local average order of dominating sets. Additionally, we give a proof of an exact formula for the local average order of dominating sets when the degree of the fixed vertex is $n-2$, and determine an upper bound for the local average order of dominating sets when the fixed vertex is an $l$-stem ($l \geq 2$).

The anti-Ramsey number $AR(n,F)$ is the maximum number of colors in an edge-coloring of the complete graph $K_n$ containing no rainbow copy of $F$. I prove that every spanning linear forest on an even number $n\ge6$ of vertices whose components have even orders and which has an isolated edge has the same anti-Ramsey number as a perfect matching on $n$ vertices. The orders of the longer path components may be different.

We study the quantized $K$-theoretic Coulomb branches of framed star-shaped quivers with central gauge dimension $n\geq2$, $r-1$ one-dimensional outer gauge vertices, and a one-dimensional framing at the central vertex. For $n=2$ and arbitrary $r\geq1$, and for every $n\geq2$ with $1\leq r\leq5$, we prove that the loop-graded Koszul-perverse heart is a monoidal categorification of the associated quantum cluster algebra over $\mathbb{Z}[v^{\pm1}]$. This quantum cluster algebra coincides with its upper quantum cluster algebra. For all $n\geq2$ and $r\geq1$, we construct an explicit initial seed and identify the associated upper quantum cluster algebra with the Grothendieck ring of this heart. Every mutation is realized by a short exact sequence, and every quantum cluster monomial is represented by a simple object.

Addario-Berry, Reed, Scott, and Wood (JoCG 2026) proved that the $n$-dimensional associahedron has chromatic number at most $22500\cdot\log_3 n+O(1)$. We present a much simpler proof that the chromatic number of the $n-1$-dimensional associahedron is at most $6 \log_2 n + 18$. Since this paper's appearance as a preliminary abstract in the Japan Conference on Discrete and Computational Geometry, Graphs, and Games held from September 7-10, 2026, the bound has been improved to $O(\log \log n)$ by Oum and Wood (arXiv September 30, 2026). It is hoped that the simple method here could give insights to further improvements.

For a graph $F$ with at least one edge, a $k$-uniform hypergraph is Berge-$F$-saturated if it contains no Berge-$F$, but adding any missing hyperedge creates a Berge-$F$. The saturation number $\text{sat}_k(n,\text{Berge-}F)$ is the minimum number of edges in such a hypergraph on $n$ vertices. English, Gordon, Graber, Methuku and Sullivan conjectured a linear upper bound for every fixed finite family of forbidden graphs. We prove the single-graph case: $\text{sat}_k(n,\text{Berge-}F)=O_{F,k}(n)$ for every fixed integer $k\ge2$ and every fixed finite simple graph $F$ with at least one edge. The proof combines a sparse construction with degree and matching arguments.

For a graph $G$ and a set $B\subseteq V(G)$, the spread $\mathrm{sp}(B)$ of $B$ is the difference between the largest and the smallest degree in $G$ of a vertex of $B$, and for an integer $k\geq 0$ the parameter $\mathrm{sp}(G,k)$ is the largest cardinality of a set $B$ with $\mathrm{sp}(B)\leq k$. Caro, Lauri and Zarb asked for the minimum of $\mathrm{sp}(G,k)$ over the maximal planar graphs of order $n$; we write $\mathrm{MP}(n,\delta ,k)$ for this minimum over the maximal planar graphs of order $n$ and minimum degree $\delta \in \{3,4,5\}$. This manuscript is intended as an exposition of the subject of spread in the degree sequence of a graph $G$, with emphasis on maximal planar graphs. We apply the general lower bound of the companion paper \cite{P1} to this class, together with further ideas, some based on Caro–West and Caro–Lauri–Zarb and some new. In particular we asymptotically determine the values of $\mathrm{MP}(n,\delta ,k)$ for every pair $(\delta ,k)$ with $\delta \in \{3,4,5\}$ and $k\geq 0$. This solution recovers the case $\mathrm{MP}(n,\delta ,0)$, which is the repetition number $\mathrm{rep}(G)$ introduced by Caro and West.

Let $\mathcal{P}_n$ denote the set of distinct permutations of length $n$ that arise from the flattening process applied to the partitions of $[n]=\{1,\ldots,n\}$. In this paper, we consider the problem of avoidance of a single classical pattern of length four by members of $\mathcal{P}_n$. Let $p_n(\tau)$ denote the number of members of $\mathcal{P}_n$ that avoid the pattern $\tau$. We show that $p_n(\tau)=C_{n-1}$ for all $n \geq 1$ for seven patterns of length four yielding new combinatorial interpretations of the Catalan number sequence. Further, we show that $p_n(\tau)$ corresponds to the binomial transform of Catalan numbers for three other patterns. To establish our results, we suitably refine the counting sequence $p_n(\tau)$ in each case so as to obtain a system of functional equations satisfied by the corresponding generating functions. These functional equations may then be solved explicitly leading to a determination of $p_n(\tau)$ in each case.

We prove that the domination number of the $2$-token graph of the path $P_n$ is $\gamma(F_2(P_n))=d(n)$ for every $n\ge 13$, where $d(n)=\frac1{10}(n^2+5n+c)$ and $c$ is an explicit constant that depends on $n \bmod 5$. This settles a conjecture by Leaños and the authors, who previously proved the upper bound. The lower bound is computer-assisted and follows the method used by Gonçalves, Pinlou, Rao and Thomassé for grid graphs.