arXane › Mathematics › Mathematics
Wednesday, 4 November 2026: 32 new papers, 23 cross-lists and 29 replacements in Combinatorics (math.CO), in arXiv's order, with full abstracts. The same papers as arXiv's own listing, set as a newspaper; every title links to arXiv.
A $d$-graph is a complete graph whose edges are colored with colors from $[d]$. It is Gallai if it contains no triangle whose three edges have distinct colors. We prove that every Gallai $d$-circulant is an iterated lexicographic product of circulants using at most two colors. The proof uses the compatibility of the known canonical modular decomposition with the cyclic action. For $d$-graphs avoiding both a rainbow triangle $\Delta$ and the two-colored four-vertex graph $\Pi$ whose chromatic components are paths, we give a more explicit classification. Color-preserving vertex transitivity is equivalent to circular symmetry and to a reduced positional game tree whose branching numbers and labels depend only on depth. The edge colors in the given cyclic labeling are determined by a chain of divisors of the order. This description yields a complete isomorphism invariant and a linear-time recognition procedure in the difference-word representation. The characterization of CIS $d$-circulants reduces to CIS two-colored factors. Finally, we extend the numerical CIS criterion to $d$-graphs whose chromatic components are vertex-transitive.
Jaeger conjectured that, for every positive integer $p$, every $4p$-edge-connected graph admits an orientation with congruent indegree and outdegree modulo $2p+1$. We prove a stronger probabilistic counterpart: a uniformly random simple $(4p+1)$-regular graph has a strongly connected orientation with all outdegrees in $\{p,3p+1\}$ with probability tending to one as its even order grows. More generally, for every fixed odd $d\ge9$, there is $\varepsilon_d>0$ such that its circular flow number is less than $2+4/(d-1)-\varepsilon_d$ with probability tending to one. We give explicit margins at the small degrees and prove the bound $91/33$ at degree seven, answering a fixed-upper-bound question of Li and Li. Gaps below $3$ at degree five and below $8/3$ at degree seven remain open. A uniform estimate for dense bisections also gives short intervals above the Li--Li maximum-bisection lower bound. Finally, we prove the one-unit bisection-gap conjecture of Greenhill, Isaev and Lewis: at every fixed degree $d\ge3$, the typical minimum parameter for orientations with outdegrees in $\{p,d-p\}$ exceeds the threshold forced by the maximum bisection by at most one.
Transitivity in social and other complex networks describes the tendency for two nodes with a common neighbor to become adjacent. We propose a new model for complex networks based on transitivity, called the Iterated Local Transitivity Model for Oriented Graphs (ILTO). The model generalizes the Iterated Local Model for Tournaments (ILMT). As in ILMT, oriented graphs are generated iteratively by cloning nodes and their adjacencies, with arcs between clones oriented either as the corresponding arcs between their parents or in the reverse direction. This process produces dense oriented graphs and, under suitable conditions, graphs with high connectivity and small diameter. We analyze the universality properties of ILTO, showing that, for generating sequences with infinite support, the base oriented graph determines which oriented graphs appear as induced subgraphs, unlike in ILMT. We study motifs in ILTO and show that when the base graph is a tournament and the generating sequence has infinite support, the model generates quasirandom tournament sequences. Finally, we study domination numbers, the cop number, and the dichromatic number. We bound the cop number in terms of the independence number of the base graph and show that, for each fixed base graph, the dichromatic number is $\Theta(2^t)$ after $2t$ consecutive 0-steps.
In this paper we study a relatively new Ramsey type graph parameter introduced by my Bachelor's thesis supervisor N\'ora Alm\'asi, and her Master's thesis supervisor Maria Axenovich. The parameter $\xi(G)$ denotes the largest natural number $n$, such that there is a red-blue-green edge coloring of $K_n$, such that in the edge coloring all copies of $G$ represent all three colors. After a brief recap on Ramsey numbers, we precisely define $\xi(G)$, and take a look at its relations to the Ramsey numbers. In the third chapter we establish lower bounds on $\xi(G)$, in the cases $G=K_5$ and $G=K_6$, namely $\xi(K_5)\ge 19$ and $\xi(K_6)\ge 31$.
The corpus of Elie Duhamel and Tristan Cazenave~\cite{dc} contains $305{,}755$ automatically generated conjectures relating spectral and metric invariants of connected graphs. A pipeline generated with Claude Code (numerical refutation, proof by the SMT solver \textsf{z3} from a library of lemmas, discovery of new lemmas, formalisation in \lean~4/Mathlib) refuted $162{,}964$ conjectures and proved $117{,}390$ without any unproved hypothesis, of which $79{,}505$ are verified end to end in \lean{} for every connected graph. This document collects, with proofs written for mathematicians, the most interesting lemmas that were discovered and proved, the ten most useful lemmas, the ten hardest theorems, simpler proofs of known results (Bollob\'as--Erd\H{o}s, Yang--Lu), and the unrefuted conjectures that we find most interesting. All the proofs are gathered in an archive
We study graphs whose powers are well-covered, with an emphasis on Cartesian products and Cayley graphs. We first establish necessary conditions and sufficient criteria for Cartesian products, provide examples showing that a factor need not be well-covered and that two noncomplete factors can have the well-covered powers property, and classify several structured product families. In particular, we construct graphs satisfying the well-covered powers property for arbitrarily large diameters. We then show that the Cartesian square of a connected abelian Cayley graph is well-covered exactly when the graph is complete. We classify the well-covered-power graphs among connected circulant graphs of degree at most four. For Cartesian products of any number of complete graphs, we also prove that the recursive alphabet-size inequalities in the final conjecture are sufficient for all powers to be well-covered, prove partial converses for arbitrarily many factors, and give explicit obstructions for every binary prefix followed by one complete factor.
We encode certain sets of partitions by regular languages of boundary words, so that their generating functions become rational series in the quantum plane $RU=qUR$. An equality between two partition counts is certified by writing the difference of their series as $(1-U)a+b(1-R)$, with $a,b$ converging $q$-adically. We show that $a,b$ may be chosen as solutions of finite holonomic systems of $q$-difference equations computed from the automata, and describe finite certificates of their convergence, together with bounded searches for such certificates; the searches need not succeed, but a false identity is always detected. As an application, we prove the three-row, level-two case of Primc's conjecture, which equates counts of coloured partitions subject to local multiplicity conditions with counts of coloured partitions whose parts lie in prescribed residue classes modulo eight.
For a permutation pi in Sk, a pi-wave is an increasing sequence of integers whose consecutive gaps have relative order pi. Let g(pi, n) be the maximum cardinality of a pi-wave-free subset of [n], and let P(pi, r) be the least integer N such that every r-coloring of [N] contains a monochromatic pi-wave. We determine the asymptotic orders of both functions for every permutation of length at most five. Existing upper bounds and weak-wave constructions provide sharp bounds for all but eight length-five patterns in S_5. For these eight exceptional alternating patterns, we establish g(pi, n) = Theta((log n)squared) and P(pi, r) = Theta(r(log r)squared).
We study fractional coloring with local demands, a framework introduced by Kelly and Postle in which one seeks a probability distribution on the independent sets of a graph such that each vertex $v$ is included with probability at least a prescribed target $\phi(v)$. For $K_r$-free graphs, Kelly and Postle conjectured that such a distribution exists provided $\phi(v)\le c_r\frac{\log d(v)}{d(v)}$ for a fixed \(c_r>0\), where $d(v)$ is the degree of $v$, and they established this up to a factor of $(\log\log d(v))^2$. In this paper, we prove their conjecture, showing that \[ \phi(v)\le\frac{c}{r}\frac{\log(d(v)+2)}{d(v)+1} \] suffices for an absolute constant $c>0$. As a corollary, we obtain a lower bound on the independence number of $K_r$-free graphs in terms of their degree sequence. This strengthens the bound that OpenAI proved in resolving the Ajtai-Erd\H{o}s-Koml\'os-Szemer\'edi conjecture. Moreover, our argument yields a deterministic algorithm that produces the desired probability distribution in time $2^{O(r^2)}n^{O(1)}$, where \(n\) is the number of vertices and the implied constants are absolute.
Qualitative independence is a property associated with the column vectors of well-known combinatorial designs known as covering arrays and qualitative independence hypergraphs characterize the existence of covering arrays on hypergraphs. The core of a hypergraph $H$ is an interesting structural characteristic to study, as it is the unique (up to isomorphism), minimal subhypergraph $H^\bullet \subseteq H$ which is homomorphically equivalent to $H$. We use the vertex transitivity and strong independence number of almost-uniform $3$-qualitative independence hypergraphs, $3\text{-}AUQI(2n+1,2)$, to show that $3\text{-}AUQI(2n+1,2)$ are cores for infinitely many $n$. Consequently, we establish that $3\text{-}QI(9,2)$ is a core and also obtain a lower bound on the strong chromatic number of $3$-qualitative independence hypergraphs $3\text{-}QI(2n+1,2)$.
The maximum size of a t-intersecting code in the set of words of length n over an alphabet of size m, a problem posed by Frankl and F\"uredi, was determined independently by Ahlswede and Khachatrian and by Frankl and Tokushige. Extending this result to the forbidden-intersection setting, Keevash, Lifshitz, Long and Minzer proved that, for m greater than two and n sufficiently large in terms of t, (t minus one)-avoiding codes have the same maximum size and the same extremal ball constructions as t-intersecting codes. They also raised the binary case. Here, t-intersecting requires every two distinct words to agree in at least t coordinates, while (t minus one)-avoiding forbids agreement in exactly t minus one coordinates. We solve the binary case for all t at least three and n at least the square of the sum of t and one. If the forbidden Hamming distance n minus t plus one is odd, the maximum size of a (t minus one)-avoiding code strictly exceeds the maximum t-intersecting size. If it is even, the two maxima coincide, but their extremal families differ: some maximum (t minus one)-avoiding codes are not t-intersecting. We also determine all maximum avoiding codes in the even case. For odd forbidden distances, weight parity and a fixed-point-free pairing determine the maximum, while the diameter theorem gives the comparison with t-intersecting codes. For even forbidden distances, parity splitting and coordinate deletion reduce the problem to avoiding two consecutive distances. Connected components, disjoint neighbourhoods, and Harper's vertex-isoperimetric theorem yield the upper bound, which is attained by a t-intersecting construction. The diameter theorem then determines the extremal structure, and elementary binomial estimates give the stated parameter range.
For $n\ge2$, a good slope of a permutation $f$ of $\mathbb{Z}_n=\mathbb{Z}/n\mathbb{Z}$ is an element $m\in\mathbb{Z}_n$ for which $x\mapsto f(x)+mx$ is a permutation. We call $f$ congruence-preserving if it preserves congruences modulo every divisor of $n$. For odd prime powers $n$, we classify all permutations with more than $n/2$ good slopes. Among permutations that are not congruence-preserving, we determine the maximum number of good slopes for $n=3^e$ with $e\ge2$, and for $n=25$, $125$ and $625$. Every permutation of $\mathbb{Z}_n$ has at most $\varphi(n)$ good slopes, where $\varphi$ is Euler's totient function. For several families of moduli with at least two distinct prime divisors, we prove a sharp upper bound for the number of good slopes of the permutations with fewer than $\varphi(n)$ good slopes. These families include $9q$ and $3q^e$ for every prime $q\ge5$ and every $e\ge1$. Together with a companion paper, this settles the bound for every odd composite modulus below $105$.
For every \(c>1\) sufficiently close to \(1\), we prove that there is \(\kappa>0\) such that every sufficiently large \(A\subset[N]\) of density at least \((\log N)^{-\kappa}\) contains \[ x,\ x+(p-1),\ x+(p-1)^2,\ldots,\ x+(p-1)^k, \qquad p=\lfloor n^c\rfloor\in\mathbb P. \] We also prove pointwise almost-everywhere convergence of the corresponding multiple ergodic averages.
In the hat guessing game on a graph $G$, each vertex is occupied by a player wearing a hat whose color is chosen from a set of $q$ colors. Each player knows the graph and their position in it and sees only the hat colors of their neighbors. The players may agree on a strategy beforehand but must simultaneously try to guess their own hat colors without communicating. They win if at least one player guesses their own hat color correctly. The hat guessing number of $G$, denoted by $\textrm{HG}(G)$, is the largest integer $q$ for which the players have a strategy that guarantees a win for every assignment of hat colors. A direct application of the symmetric Lov\'asz Local Lemma shows that $\textrm{HG}(G) < e\Delta$ for every graph $G$ of maximum degree at most $\Delta \ge 1$. We prove that this bound is asymptotically sharp: for every $\varepsilon > 0$ and every sufficiently large $\Delta$, there exists a graph $G$ of maximum degree at most $\Delta$ with $\textrm{HG}(G) \ge (e - \varepsilon)\Delta$. This answers a question of Alon et al., disproves the conjecture $\textrm{HG}(G) \le 2\Delta(G)$ of Bosek et al., and improves on the construction of Latyshev and Kokhas, which achieves $\textrm{HG}(G) = 4\Delta(G)/3$. The hat guessing number thus provides a natural combinatorial problem in which the Lov\'asz Local Lemma is asymptotically tight.
Let $d \in \mathbb{N}$ and let $A \subseteq \mathbb{R}^d$ be a finite, non-empty set not contained in any translate of a hyperplane. We show that there exists a subset $S \subseteq A$ such that $d \ll |S| \ll d$ and \[E(A,S) := |\{(a_1,a_2,s_1,s_2)\in A\times A\times S\times S:a_1+s_1=a_2+s_2\}|\ll\lvert A\rvert\lvert S\rvert.\] This can be interpreted as a robust, analytic generalisation of the classical Freiman's lemma, and recovers Freiman's lemma up to a constant multiplicative factor. In the process of proving this result, we also show that for any integer $1 \leq m \leq d$ and any set $A \subset \mathbb{R}^d$ with $|A| \leq \binom{d}{m}$, one has \[ E(A, B) \leq 4(m + 1/m) |A||B|,\] where $B$ is the canonical basis of $\mathbb{Z}^d$. This gives new estimates for multiplicative energies between finite sets of primes and arbitrary subsets of positive integers, improving a previous result of Shkredov. Using related ideas, we also prove new bounds for an edge-isoperimetric problem for certain graphs on the boolean cube, improving an earlier result of Kirshner and Samorodnitsky. We give two different proofs of the first result described in this abstract and three different proofs of the second one.
Tree decompositions describe large graphs as gluings of smaller component parts. Here we study their categorical duals, tree co-decompositions, which construct large graphs via fibered products of small constituent parts. Co-decompositions are compressed representations of graphs or relational structures: the decomposed object can be exponentially larger than the space required to specify the co-decomposition. Our main contribution is an algorithmic meta-theorem for first order logic: given only a co-decomposition of a $\sigma$-structure $G$ with $b$ bags, each of size at most $w$ and an FO sentence $\phi$, there is an algorithm which, without ever constructing or inspecting $G$, operates on the co-decomposition and determines whether $G \models \phi$ in time $f_\sigma(w,|\varphi|)\cdot b$. We pair this algorithm with structural results on tree co-width, including its relationship to tree-width and a separation from twin-width. Furthermore, we characterize bounded path co-width using a graph grammar. In contrast to our logical meta-theorem, we prove that $(s,t)$-Path becomes NP-hard on co-decomposition inputs. These results demonstrate how categorical constructions can enable efficient computation on exponentially compressed structures.
For every $n\ge4$, arbitrary trees of orders $n,n-1,n-2$ can be packed into $K_n$ online, in decreasing order of size: each tree must be embedded before the next is revealed, and earlier embeddings cannot be changed. This strengthens the classical three-tree packing theorem of Hobbs, Bourgeois and Kasiraj (1987). In particular, the second tree is embedded without knowing the third, and the resulting pair of copies can be extended to accommodate every possible third tree. Our strategy is to embed the first two trees so that their union is $2$-degenerate. We prove that the complement of every $2$-degenerate graph on $n$ vertices contains every tree of order $n-2$, which guarantees the final move. The main ingredient is an embedding lemma for spiders whose center must occupy a prescribed vertex having degree at most two in the forbidden graph. We then extend this lemma to arbitrary trees by induction.
Stein conjectured that for every positive integer $k$, every oriented graph with minimum semi-degree greater than $k/2$ contains every oriented path of length $k$ [Springer Optim.Appl. 165 (2020), 459--486]. For directed paths this is a classical result of Jackson (1981). The two-block case of the conjecture was established by Chen, Hou and Zhou (2025). In this paper we prove the two-block analogue of Jackson's theorem. For all positive integers $s$ and $r$, let $P(s,r)$ be the oriented path consisting of two directed paths of lengths $s$ and $r$ with a common terminal vertex, and let $Q(s,r)$ be its reverse. We show that for all $K\ge3$ and all $s,r\ge1$ with $s+r\le K$, every oriented graph $D$ with $\delta(D)\ge K$ and $d_D^+(u)+d_D^-(v)\ge K-1$ for every ordered pair of distinct vertices $(u,v)\notin A(D)$ contains both $P(s,r)$ and $Q(s,r)$. Our result is the two-block analogue of Jackson's theorem, and it extends the two-block result of Chen, Hou and Zhou. The proof iterates a shift of the terminal vertex of a longest path.
We study structural defects in fixed points of block substitutions, building on arXiv:2604.12637 and providing its technical supplement. We develop an automata-based framework to characterize their occurrence and derive verifiable combinatorial criteria. We also introduce simplifications for the construction and analysis of these automata, including tensor-product decompositions, that clarify the mechanisms underlying structural defects and their emergence.
A \emph{rainbow cycle} in a list-edge-colored graph is a cycle where no color appears more than once. We give a short and simple proof of a result of [ABSZZ] showing that a properly edge-colored $n$-vertex graph with average degree $\Omega(\log n\log\log n)$ always contains a rainbow cycle, and generalize it to weighted graphs with edges list colored with list size at most $\ell$ and where the total weight of all edges containing a given color $i$ incident to a vertex is at most $\Delta$, showing that $\Omega_\ell(\Delta\log n\log\log n)$ average degree guarantees a rainbow cycle. Using the reduction of [AG26] and the new generalized rainbow cycle theorem, we prove that for $r\geq 3$, every binary linear $r$-query locally correctable code $E:\mathbb{F}_2^k\rightarrow \mathbb{F}_2^n$ satisfies $k\leq \tilde{O}(n^{1-2/(r-1)})$ by showing a rainbow analogue of the odd $r$-LDC lower bounds of [BHKL25,JM25], closing the gap between the best known lower bounds for odd- and even-query binary linear $r$-LCCs.
The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees $k$ edge-disjoint spanning trees, each of diameter $O(n/\delta)$ and with $O((n/\delta)\log(\delta+1))$ internal vertices, where $n$ is the number of vertices and $\delta$ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of $k$, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time $\tilde{O}(n^5)$. We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.
The second Zagreb matrix of a graph $G$ is $Z(G)=D(G)A(G)D(G)$, where $D(G)$ and $A(G)$ are the degree matrix and the adjacency matrix of $G$. For many degree-based weighted adjacency matrices, the trees, unicyclic graphs and bicyclic graphs with the largest spectral radius have a vertex adjacent to all others, and Mei et al. conjectured this for every such matrix on unicyclic graphs. Jiang et al. showed that $Z(G)$ is a counterexample. We prove that, for $q\in\{0,1,2\}$ and every $n\ge4$, the connected graph of order $n$ and cyclomatic number $q$ maximizing the spectral radius of $Z(G)$ is unique, and is obtained from two adjacent vertices with $q$ common neighbours by attaching $n-q-2$ pendent vertices to them as evenly as possible. The only exceptions are the star for $q=0$ and $n\le7$, and the triangle with one pendent vertex at each vertex for $q=1$ and $n=6$. This confirms a conjecture of Jiang et al.\ and all three parts of a conjecture of Shen and Shan for this matrix, with best possible thresholds on $n$. For $n\ge8$, the maximum value is $\lfloor (n+q)^2/4\rfloor+(n+q)/2+7q-2+O(1/n)$, whereas the star gives only $(n-1)^{3/2}$. A key tool is a determinant criterion that reduces spectral comparisons to sign conditions on explicit polynomials.
Erd\H{o}s and Gy\'arf\'as conjectured that every graph with minimum degree at least three contains a power-of-two-length cycle. We prove every Cayley graph of odd order satisfies the conjecture. As a corollary, we find that Cayley graphs of finite nilpotent groups satisfy the conjecture as well.
We introduce the face polynomial of a ribbon graph, a generating function for face numbers under the ribbon group action. It addresses the face-count case of the Ellis--Monaghan--Moffatt question on twisted duality. We derive deletion--contraction recursions and prove that this polynomial coincides with the vertex polynomial for \(\langle\delta\rangle\), \(\langle\delta\tau\rangle\), and \(\langle\delta,\tau\rangle\). We characterize monomial cases and obtain formulas and recursions for Euler-genus partial-twuality polynomials. For orientable graphs, we show that the partial-dual face polynomial has both parities whenever an edge exists, so the partial-dual Euler-genus polynomial has only even exponents.
Two distinct $r$-element sets are adjacent if their intersection has size $r-1$. The Kleitman-West problem, equivalently formulated as the edge-isoperimetric problem on the Johnson graph $J(n,r)$, asks for the maximum number $M_r(n,m)$ of unordered adjacent pairs in a family of $m$ $r$-element subsets of an $n$-element set, and for the families attaining this maximum. For every fixed integer $r\ge2$, we determine this maximum asymptotically as $n\to\infty$, uniformly over the entire range of family sizes. Specifically, for each integer $1\le j\le r$, define $F_j(p)=\max\{p^{1+1/j},\,2p-1+(1-p)^{1+1/j}\}$ for $0\le p\le1$, and $G_j(x)=\lfloor x\rfloor+F_j(x-\lfloor x\rfloor)$ for $x\ge0$. With \[ P_r(n,m)=\sum_{j=1}^r\frac{n^{j+1}}{2(j-1)!}G_j\!\left(\frac{j!m}{n^j}\right)-\frac{r(r-1)}4mn-\frac m2, \] we prove that \[ \lim_{n\to\infty}\max_{2\le m\le\binom nr}\left|\frac{M_r(n,m)}{P_r(n,m)}-1\right|=0. \] The remaining cases satisfy $M_r(n,0)=M_r(n,1)=0$. The proof first establishes the asymptotic formula for dense families using a sharp inequality for bounded random variables, with equality attained by a random variable taking at most two values. To extend the result uniformly to all family sizes, we extract groups of sets sharing a fixed subset, apply the dense estimates after deleting that subset, and control the adjacent pairs not contained in any one group.
For a graph $G$ with nonnegative edge weights, let $\operatorname{mc}(G,w)$ denote the maximum total weight of a cut and let $w(G)$ denote the total edge weight. We prove that every edge-weighted triangle-free subcubic graph satisfies $\operatorname{mc}(G,w)\geq \frac{15}{19}w(G)$, improving the bound of $\frac{8}{11}$ due to Gutin and Yeo. For subcubic graphs of odd girth at least seven and nine, we strengthen this bound to $\frac{47}{59}w(G)$ and $\frac45w(G)$, respectively, establishing the conjecture of Gutin and Yeo for graphs of odd girth at least nine. Our proofs combine structural properties of vertex partitions with randomized cut constructions and convex combinations of the resulting bounds.
We give an example of a tiling of the $m=4$ amplituhedron that has fewer cells than that of the magic number conjecture. The tiling uses an injective degree two cell.
The concept of the Friends and Strangers graph $FS(G,H)$ associated with two graphs $G$ and $H$ was recently introduced by Defant and Kravitz and has generated significant interest. In a companion article, joint with Alon, they consider the behaviour of $FS(G,H)$ in the case where $G$ and $H$ are Erd\H{o}s-R\'enyi random graphs, and prove that the threshold for connectivity is of the form $n^{-1/2+o(1)}$. In this paper we prove that the threshold is $n^{-1/2}\sqrt{\log{n}}$, up to a multiplicative constant, answering a question from Alon, Defant and Kravitz.
Let $f_3(n,e+3,e)$ denote the maximum number of edges in an $n$-vertex $3$-uniform hypergraph containing no $e$ distinct edges spanning at most $e+3$ vertices. It has long been conjectured that $f_3(n,e+3,e)\ge n^{2-o(1)}$ for every fixed $e\ge3$. We prove that $f_3(n,9,6)\ge n^2\exp(-O((\log n)^{2/3}))$, settling the first unsolved case of the conjecture.
Let $\mathcal{T}(n,d)$ denote the set of subsets of $[n]^d$ that tile $\mathbb Z^d$ by translations, and write $T(n,d)=|\mathcal{T}(n,d)|$. We show that almost every tile in $\mathcal{T}(n,1)$ tiles $\mathbb{Z}$ by an arithmetic progression, thus determining $T(n,1)$ asymptotically. In higher dimensions, we prove that $T(n,d)=O_d\!\left(n^{C_d}3^{n^d/3}\right)$, confirming a conjecture of Benjamini, Kozma and Tzalik. In the other direction, we prove that $T(n,d)\geq (1-o(1))n^{\binom d2}3^{n^d/3}$ when $3\mid n$. This shows one cannot take $C_d=d-1$ for $d\geq 3$, answering a question due to the same authors negatively. Finally, we also obtain nearly tight bounds in dimension two. Our upper bounds rely on a new observation realising tiles as maximal independent sets in truncated Cayley graphs.
We present a proper 12-colouring for all associahedra. This gives the first constant upper bound on chromatic number for this family, and disproves a conjecture of Fabila-Monroy et al. from 2009.
The Weisfeiler-Leman algorithms WL(k) for $k\ge1$ form a hierarchy of increasingly powerful tests for graph isomorphism. We study how the equivalence relations they induce on graphs transfer through a graph operation $\Phi$: for a given $k$, what level of WL-equivalence between graphs $H_1$ and $H_2$ guarantees WL(k)-equivalence of graphs $\Phi(H_1)$ and $\Phi(H_2)$? We call the least such level the transfer parameter $\tau_\Phi(k)$ and determine it exactly for the line graph operation $\Phi = L$: $\tau_L(k)=2k+1$ for $k\ge2$, while $\tau_L(1)=1$. We also extend these results to the $(r,S)$-line graphs, which generalize the line graph from edges to $r$-cliques by connecting two cliques when their intersection size lies in a prescribed set $S$. For these operations we prove that $\tau_{r,S}(1)=r-1$ for every $S$ and, for certain choices of $S$, that $\tau_{r,S}(k)=rk+r-1$ for $k\ge r$, and we bound the transfer parameter in the remaining range. Our upper bounds on transfer parameters follow from a treewidth analysis of diagrammatic expansions of homomorphism counts into $\Phi(H)$ as linear combinations of homomorphism counts into $H$. The matching lower bounds combine explicit constructions of witness graphs with the homomorphism-distinguishing closedness of graphs of bounded treewidth.
We characterize bipartite graphs whose edge rings are almost Gorenstein. Using this characterization, we recover known results for two families of graphs. In addition, we show that if the edge ring of a bipartite graph is almost Gorenstein and its $h$-polynomial has degree at least two, then the $h$-polynomial is palindromic except possibly for the linear and next-to-leading coefficients. Moreover, we construct two bipartite graphs whose edge rings have the same $h$-vector, although only one of the rings is almost Gorenstein.
We show that the kissing numbers in dimensions 32, 33, 34, 35, 37, 38 and 39 are at least 352320, 370240, 390980, 415308, 499816, 605322 and 768916, improving the previous bounds 347584, 364736, 384836, 409676, 498024, 591900 and 763668. Except in dimension 38, the configurations are those of Edel, Rains and Sloane with new binary constant-weight codes of weight 8 and minimum distance 8 in the middle layer; each additional word adds 128 points. In dimension 38 we add 6855 antipodal pairs of vectors of the second shell of the Leech lattice to the empty equator of Kravatskiy's 591612-point configuration, where 144 pairs were known; this is an independent set problem in a regular graph of degree 11178 on 8386560 vertices. The codes and lines were found by local search, and all configurations were checked pair by pair in exact integer arithmetic.
A planar crescent configuration consists of $n$ points, no three collinear and no four concyclic, whose distinct distances have multiplicities $1,2,\ldots,n-1$. We prove by exact computation that no such configuration exists for $n=9$. The three pairs carrying the two least frequent distances yield a six-point subset with at most six distances. Rational linear algebra on quartic polynomials separates the possible six-point distance patterns into those with certified finite lists of normalized distance tuples and a residual family. Compatibility of overlapping subsets forces at least one core into the first family, without classifying the residual realizations. The remaining three points are then obtained by rational constructions over the field of the squared core distances. The multiplication matrices used to enumerate the core distances have order at most twelve. Exhaustive label assignments and exact algebraic comparisons exclude all remaining extensions.
Let ${\mathcal L}$ be an arrangement of $d$ lines in the complex projective plane and let $Z={\operatorname{Sing}}({\mathcal L})$. A question of Pokora asks whether the multipoint Seshadri constant of ${\mathcal O}_{\mathbb{P}^2}(1)$ at $Z$ is always computed by a line of the arrangement containing the largest number of points of $Z$. We prove that the answer is affirmative for every arrangement of at most twelve lines. The proof uses a B\'ezout-type covering criterion, elementary restrictions on the intersection lattice, and a detailed analysis of the two extremal combinatorial types that can occur for twelve lines. One type is the Hesse arrangement; it is handled using a net of quartics through its twelve double points. The other type would yield a uniquely determined incidence structure on thirteen lines. We show that this incidence structure is not realizable over any field.
A tournament is an orientation of a complete graph. A vertex $v$ controls a vertex $u\neq v$ if there is a directed path of length at most two from $v$ to $u$, and a $\delta$-king is one that controls at least $\delta(n-1)$ vertices. In the query complexity model, each query reveals the orientation of an edge. Shen, Sheng and Wu [SICOMP'03] established an $\Omega(n^{4/3})$ lower bound on the deterministic query complexity of finding a $1$-king, and a non-matching upper bound of $O(n^{3/2})$. Neither bound has been improved in over two decades, despite substantial progress on variants of the problem. For $\delta$-kings with $\delta < 1$, Biswas, Jayapaul, Raman and Satti [Discrete Applied Mathematics'22] showed that $O(n^{4/3})$ queries suffice to find a $\frac12$-king. Lachish, Reidl and Trehan [FSTTCS'22] improved this guarantee to $\frac12+\frac{2}{17}$ using $\widetilde{O}(n^{4/3})$ queries, and asked whether a larger fraction could be achieved within the same query bound. We answer this question affirmatively for every fixed fraction below one: for every fixed $\varepsilon\in(0,1)$, we give a deterministic algorithm that finds a $(1-\varepsilon)$-king using $O(n^{4/3})$ queries. The design of our algorithm is informed by a structural analysis combining a sparse regularity lemma due to Allen, Kohayakawa, Mota and Parente [Electronic Journal of Combinatorics'14] with a new sampling argument based on a reachability theorem of Afek, Gafni and Linial [arXiv'19].
We study min-plus Bruhat cells $B_{trop}^{(n)} \odot p\odot B_{trop}^{(n)}$, where $B_{trop}^{(n)}$ denotes the set of all upper-triangular matrices over $\RR \cup \{\infty\}$, and $p$ is a permutation. It is proved that $\dim (B_{trop}^{(n)} \odot p \odot B_{trop}^{(n)})= \frac{n(n+1)}{2} + l(p)$, where $l(p)$ is the length of $p$ in Coxeter generators. Also we provide an explicit description of the cell $B_{trop}^{(n)}(\RR) \odot p_0\odot B_{trop}^{(n)}(\RR)$ (up to a subset of dimension less than $n^2$) for the highest in Bruhat order permutation $p_0$. Finally, it is shown that for a tropically non-singular matrix $A$ for at most one permutation $p_A$ it can hold $A\in B_{trop}^{(n)}\odot p_A\odot B_{trop}^{(n)}$.
A proper conflict-free coloring is a proper vertex coloring in which every non-isolated vertex has a neighbor whose color appears exactly once in its open neighborhood. We study this coloring on chordal and ordered bipartite graph classes. For well-partitioned chordal graphs, we prove the tight bound $\omega(G)\leq\pcf(G)\leq\omega(G)+1$ and give an $O(n^2)$ construction from a partition tree. Every assignment of lists of at least $\omega(G)+1$ colors also admits a PCF coloring that respects the lists. Deciding whether $\omega(G)$ colors suffice is NP-complete, even when the partition tree is a star. This also proves NP-completeness on chordal graphs when the number of colors is part of the input. For interval graphs, we prove that lists of size $\omega(G)+1$ always suffice, improving the previous ordinary-coloring bound of $\omega(G)+2$. We use matchings to characterize when $\omega(G)$ colors suffice and give an endpoint algorithm taking $2^{O(\omega(G)^2)}n^{O(1)}$ time. We also characterize the exact value when the clique number is at most three and give a linear-time algorithm from sorted interval endpoints. For biconvex graphs, we prove a tight five-color bound and give a direct exact algorithm taking $O(n^{33})$ time. For bipartite permutation graphs, a smaller dynamic program gives an exact $O(n^{17})$ algorithm. Finally, if a bipartite graph is convex over an ordered shore $X$, we prove the sharp bound $\pcf(G)\leq\lceil\log_2(|X|+1)\rceil+3$ and construct a coloring in linear time from the order.
A magic square exemplifies balance in inequality: its $n^2$ entries $\{1,\dots,n^2\}$ are distinct, yet every row, column, and main diagonal sums to $\mu_n=n(n^2+1)/2$. Lifting centred grid cells into $\mathbb{R}^3$ as radial vectors $\mathbf{p}_{ij}(\lambda)=(x_j,y_i,\lambda z_{ij})$ and taking their convex hull---the Magic Gem $\mathcal{G}_\lambda(S)$---asks: when does line-sum equality suffice for equilibrium in 3D, and when a nonlinear realization breaks balance, how can an opposing inequality restore it? We test this across all $880$ order-$4$ magic squares in four regimes. For radial spokes from $O$, natural lengths balance identically, while unit spokes break equilibrium on all $832$ non-associative squares in 3D and on all squares in 2D, where the ring-radius ratio $r_2/r_1=\sqrt{5}$ bounds the resultant below by the Pell convergent $9/4\approx\sqrt{5}$. By length--weight duality, balance is restored via tip weights $\mathbf{w}^*>\mathbf{0}$ on $S^2$ or power-law spoke scaling ($r^{\alpha^*}$ in 2D and $(\mathbf{V}_3)_z=0$ in 3D). In 3D rotation, equal point masses make every semi-magic square an axisymmetric top with spherical-top transition $\lambda_{\mathrm{iso}}=(n^2+1)^{-1/2}$, whereas entry masses $m_{ij}=s_{ij}$ expose the quadrupole $Q_{xy}=\sum z_{ij}x_jy_i$, triggering $180^\circ$ Dzhanibekov flips on $824$ squares. Passing to the uniform solid hull $\mathcal{G}_0(S)$ shifts the centroid off $O$ on $829$ squares; re-engaging the opposing core $\mathcal{G}_1(S)$ restores balance via two-density inclusions, nested wireframes, or the $K_{n^2}$ strut network, while all $880$ hulls unfold into non-overlapping nets with $f_0-1$ glue tabs. Finally, $\lambda=1/5$ stabilizes $74.5\%$ of facets on a table, and alternating $\mathcal{G}_\lambda(S)$ with its mirror twin $\mathcal{G}_\lambda(r^2\overline{S})=-\mathcal{G}_\lambda(S)$ locks chiral blocks into a vertical tower.
A tester decides whether a graph has a property or is far from having it. A distance estimator asks for more: it must approximately determine how many edges need to be changed. A property is said to be testable if there is a tester with a number of queries bounded independently of the graph's order for each conceivable distance. Similarly, if a property admits an estimator with a number of queries bounded independently of the graph's order, it is said to be estimable. Fischer and Newman proved that, in the dense graph model, every testable property is also estimable. We show that the passage from testing to estimation requires only a polynomial increase in query complexity. This resolves a long-standing open problem in property testing, previously tackled by Fiat and Ron, by Hoppen, Kohayakawa, Lang, Lefmann, and Stagni, and by Gishboliner, Kushnir, and Shapira.
An ordered deck of $n$ cards is subjected to $k$ independent Gilbert--Shannon--Reeds riffle shuffles. A player then guesses each card without feedback, with repeated guesses allowed. For every fixed $k\ge1$, we prove that, once $n$ is sufficiently large, an optimal guess at position $i$ in the top half of the deck is $\lfloor i/2^k\rfloor+1$; the bottom-half strategy is obtained by reflection. We also show that the optimal expected number of correct guesses is $2\sqrt{n/((2^k-1)\pi)}+O_k(1)$. Our starting point is the result of our earlier work that the label at each position is distributed as an equally weighted mixture of $2^k$ components, each a shifted sum of two independent binomial random variables (a Poisson-binomial distribution). The proof of the optimal strategy combines three ingredients: a uniform concentration estimate that separates the mixture components, exact binomial inequalities that control the gaps between competing peaks, and a coefficient comparison that resolves modal ties. The expected-score asymptotic is proved independently of the strategy, using only the peak heights of the mixture components.
Given a finitely aligned higher-rank $k$-graph $\Lambda$, Farthing, Muhly and Yeend (Semigroup Forum 2005) constructed an inverse semigroup $S_\Lambda$ to provide a groupoid model for the $C^*$-algebra of $\Lambda$. In this paper, we extend some of the existing results related to the semigroup structure of a graph inverse semigroup to the more general setting of the inverse semigroup $S_\Lambda$. We obtain geometric descriptions of the Green's relations on $S_\Lambda$, which effectively generalize the existing characterization of Green's relations on a graph inverse semigroup. We provide a simple and useful description of the Cuntz-Krieger ideal of the Booleanization of $S_\Lambda$ and, based on this, identify a certain $X$-to-join Booleanization of $S_\Lambda$, where the abstract and concrete Cuntz-Krieger relations agree. Besides the natural partial order, $S_\Lambda$ is also ordered by set-inclusion. This helps us to realize $S_\Lambda$ as a semigroup \emph{graded-ordered} by $\mathbb{Z}^k$ and, subsequently, gives rise to a full inverse subsemigroup $S_\Lambda^h$ of $S_\Lambda$, which is graded by $\mathbb{Z}^k$ in the usual sense. We show that the Kumjian-Pask algebra of $\Lambda$ is graded isomorphic to the quotient of the contracted semigroup algebra of $S_\Lambda^h$ by the tight ideal. In the final part of the paper, we show that a $k$-graph morphism $p:\Lambda_1\longrightarrow \Lambda_2$ that is injective and satisfies a certain path lifting property induces, in a natural way, an injective $0$-preserving semigroup homomorphism from $S_{\Lambda_1}$ to $S_{\Lambda_2}$. In view of this, we build a suitable categorical setup to conclude that the isomorphism established between the Kumjian-Pask algebra of $\Lambda$ and the tight ideal quotient of the semigroup algebra of $S_\Lambda^h$ is natural.
A Kelmans transformation increases or preserves the largest eigenvalue of a symmetric nonnegative matrix. We determine when this comparison holds for Hermitian block extensions with a fixed coupling and an arbitrary common complementary block. An orthogonal change of basis and Schur complementation give an exact formula for the compressed resolvent difference as a difference of two rank-one matrices. This formula characterizes admissible coupling subspaces by proportionality of projected resolvent vectors. Polynomial coefficient kernels describe all such subspaces, and cyclic subspaces give dimension bounds and a maximum-dimension result for a two-block family. We also prove a general block comparison theorem and give monotonicity and equality criteria for nonnegative rank-one couplings. Applications concern graph joins, complex attachments, and Hermitian adjacency matrices.
We show that for every $\gamma>0$ and every sufficiently large $\Delta$, the Glauber dynamics for proper $q$-colorings of any $n$-vertex graph of maximum degree $\Delta$ has spectral gap $\Omega_\gamma(1/n)$, and hence mixing time $O_\gamma(n^2\log q)$, whenever $q\ge(1+1/\mathrm{e}+\gamma)\Delta$. Our proof establishes a Bochner-type inequality by exploiting the spectral gaps of hard-core models hidden in the color classes. The constant $1+1/\mathrm{e}\approx1.368$ comes from the uniqueness threshold $\approx\mathrm{e}/\Delta$ of the hard-core model on the infinite $\Delta$-regular tree.
We prove Douglas' conjecture for $m$-Kronecker quivers for each $m \geq 3$ on the normalized logarithms of Euler characteristics of moduli spaces. Also, we state a log-concavity conjecture on Euler characteristics near slope one for the 3-Kronecker quiver.
In a recent paper of the same title, we considered nondistinct partitions of integers over the Fibonacci sequence and related linearly recurrent sequences. In this paper, continuing this story, we apply the same method, but consider distinct partitions. In particular, let $q_F(m)$ denote the number of ways of writing $m$ as the sum of distinct Fibonacci numbers. It is well-known that, while $q_F(m)$ behaves wildly, its partial sums behave in a more structured way. In particular, Kempton showed that the function $N^{-\log 2/\log\varphi}\sum_{m\leqslant N}q_F(m)$ is asymptotically logarithmically-periodic. In this paper, we improve on this result by providing an explicit error term. Additionally, we prove the analogous result for a class of more general linear recurrent sequences.
In our previous article CMP 407 (2026) 131, we explored the rich algebraic structures arising from a specific quantum many-body Hamiltonian quartic in the bosonic creation-annihilation operators. This Hamiltonian originated from the works of G\'erard and Grellier on classical turbulent energy transfer in a Lax-integrable setting, and its quantum version respects hierarchies of polynomial conservation laws all of which possess purely integer spectra, as does the Hamiltonian itself. The latter feature, known from numerical studies, has previously remained unproved. Here, we present an elementary solution of the quantum G\'erard-Grellier Hamiltonian. The eigenstates are labelled by partitions and the corresponding eigenvalues admit simple explicit expressions in terms of the principal hook lengths. The key ingredient in this construction is a specific basis we introduce, inspired by the classical multisoliton coherent states, in which the Hamiltonian is upper-triangular. The expressions for the eigenvalues then immediately follow, while the full eigenbasis can be recovered via a Gram-Schmidt procedure.
Intersecting codes are codes in which any two nonzero codewords share a common nonzero coordinate, and they have been extensively studied due to their applications in communication theory, cryptography, and combinatorics. Recently, geometric interpretations have provided new insights into intersecting codes, both in the Hamming metric and, more recently, in the rank metric for linear codes. In this paper, we introduce and study matrix rank-metric intersecting codes. By defining the support of a matrix as its row space, we extend the notion of intersecting codes to the matrix rank-metric setting. Using the slice space associated with the generator tensor of a rank-metric code, we derive a geometric characterization that is equivalent to the intersecting property. This characterization generalizes the known results for linear rank-metric intersecting codes and highlights both analogies and differences with the linear case. In particular, it yields bounds on the parameters of intersecting codes, one of which is sharp and differs from the one in the linear case, together with first constructions. We then consider codes that are closed under multiplication, i.e. matrix algebras. In this setting, the intersecting property can be read off from the algebraic structure, namely the Jacobson radical and the socle. This provides a simple and flexible way to construct many intersecting codes, including codes that do not satisfy the classical sufficient condition on the minimum distance.
Using the bisection bound of Monien and Preis, Fomin and H{\o}ie proved in 2006 that every graph of maximum degree 3 on $n$ vertices has pathwidth at most $n/6+o(n)$. We prove that the pathwidth, bisection width and cutwidth of these graphs are at most $c_3 n+o(n)$, where $c_3=\frac{3}{4\pi}\arccos\frac56\approx0.1398$. For bisection width this improves the bound $n/6+o(n)$ of Monien and Preis (2006) and extends to all such graphs the bound that Lichev and Mitsche (2023) obtained for random cubic graphs. For maximum degree 4, we prove that bisection width and cutwidth are at most $n/3+o(n)$, improving the bound $2n/5+o(n)$ of Monien and Preis for 4-regular graphs, and that pathwidth is at most $0.2458n$, improving the bound $n/3$ of Fomin, Gaspers, Saurabh and Stepanov (2009). We show that every graph with $m$ edges has pathwidth at most $7m/48+o(n)$, improving the bound $13m/75$ of Scott and Sorkin (2007), and we give further bounds of the form $\sum_{d\ge3}a_d n_d+o(n)$ with $a_d<1$, where $n_d$ is the number of vertices of degree $d$. The path decompositions, and linear orderings of the stated cutwidth, can be computed in polynomial time. Instead of deriving pathwidth bounds from bisection width, we give each vertex a Gaussian label, a weighted sum of independent standard normal variables over a ball around it, and sweep a threshold through the labels; the bags are frontiers, the vertices above the threshold with a neighbor below it. We bound the probability that a vertex lies in a frontier by comparison with an explicit Gaussian model of a vertex and its neighbors. Faster exact algorithms follow: for feedback vertex set and the traveling salesperson problem on graphs of bounded maximum or average degree, and on general graphs for minimum weight dominating set (by branching until the instance is sparse), Max 2-CSP and counting subgraphs with $k$ edges (by the bound in $m$).
Andrews and El Bachraoui (\textit{RACSAM} \textbf{119}, \textit{Article Number 4 (2025)}) established identities relating $4$-regular partitions to partitions with distinct even parts whose largest part is odd. As an extension to their work, in this paper we define partitions of a positive integer $n$ with bounded multiplicity restriction on even parts and whose largest part is odd. We prove some identities relating our partition functions and $2r$-regular partition function, and show that identities due to Andrews and El Bachraoui follow as particular cases.
Let $\mu$ be a probability distribution on a spin system with $n$ sites and possibly infinite spin spaces. We prove local-to-global spectral-gap bounds for block Glauber dynamics. Given a symmetric, entrywise nonnegative matrix $A$ with zero diagonal and $\lambda_{\max}(A)<1$ encoding local spectral bounds for a spin system, we derive global spectral-gap bounds for block dynamics on its marginal distributions. These bounds are sharp: the Gaussian system with covariance $(I-A)^{-1}$ attains equality for every choice of disjoint blocks. Our proof extends the Bochner method through an abstract inequality for orthogonal projections on Hilbert spaces. As an application, we prove that Glauber dynamics for the $O(N)$ model, with $N\geq 2$, arbitrary external fields, and couplings of either sign, has spectral gap at least $(1-\|J_{\mathrm{abs}}\|_{\mathrm{op}}/N)/n$, where $J$ is the interaction matrix and $J_{\mathrm{abs}}=(|J_{ij}|)$. We also obtain spectral bounds for swap walks and local spectral expansion of partite simplicial complexes. For complexes formed from disjoint groups of ranks in random flags of subspaces over $\mathbb F_q$, we obtain a one-sided local spectral expansion bound of $2\sqrt q/(q+1)$. This bound is independent of the number and sizes of each group, and is nontrivial for every prime power $q$. Finally, for random forests $F$ of any finite graph with arbitrary positive edge weights, we prove that \[ \Pr(e,f\in F)\le \frac{4}{3} \Pr(e\in F)\Pr(f\in F) \] for distinct edges $e,f$, improving the factor 2 supplied by general log-concavity bounds for matroid independent sets. The argument combines our extended Bochner method with the analysis of an auxiliary real stable polynomial.
We prove a power-saving form of the van der Corput property for cubes. As a consequence, we obtain a power-saving bound $|A|\ll_\varepsilon N^{59/60+\varepsilon}$ for sets $A\subseteq\{1,\ldots,N\}$ with no nonzero cube differences.
We continue the study of bond percolation on finite graphs induced by the level-sets of the zero-average Gaussian free field on the associated metric graph. In our previous work Goswami and Pal (2026), we analyzed the critical and near-critical behavior of this model on uniform expanders, focusing on the volume of the largest cluster. In the present paper, we investigate the size of the second largest cluster in the supercritical regime --- the phase where one expects a unique giant component. We prove that the second largest cluster is at most of logarithmic order with high probability. The estimates hold uniformly over deterministic graphs with a bounded maximum degree and a spectral gap bounded away from zero. In particular, we do not require any assumption regarding regularity, girth or local geometry. This picture is substantially different from Bernoulli percolation, where the second largest supercritical cluster can have polynomial volume under identical hypotheses. The proof relies on expansion properties of the underlying graph and the Dirichlet martingale framework developed in Goswami and Pal (2026).
We study the problem of reconfiguring plane, straight-line spanning trees on point sets in the plane. A flip is a reconfiguration step in which one edge of a tree is replaced with another, yielding again a plane spanning tree. For a given point set $P$, the flip graph has a vertex for each plane spanning tree on $P$, and an edge between any two trees that differ by a single flip. The folklore happy edge conjecture suggests that any edge shared by both the initial and the target tree (a happy edge) is never flipped in a shortest flip sequence. This conjecture was computationally verified for up to 10 points in convex position. In this paper, we disprove this conjecture both on general point sets and on point sets in convex position by providing two counterexamples on $16$ and $30$ points, respectively. The counterexample for point sets in general position also holds for compatible flips, while the happy edge property holds for compatible flips in convex point sets as shown by Aichholzer, Dorfer, and Vogtenhuber [GD 2025].