Papers

Let $a$ and $b$ be distinct real weights. An $\{a,b\}$-edge-weighting of a tree assigns one of these weights to each edge and is proper if adjacent vertices have different sums of incident edge weights. For every such pair, we give an explicit structural characterization of the trees that do not admit a proper $\{a,b\}$-edge-weighting. If $ab(a+b)\neq0$, then $K_2$ is the only tree without such a weighting. If $a+b=0$, then a tree has no proper $\{a,b\}$-edge-weighting exactly when every vertex has degree $1$ or $3$ and the subgraph induced by the degree-$3$ vertices has a perfect matching. For the remaining case $ab=0$, form the spanning forest consisting of the edges whose deletion leaves two odd-order components. A tree $T$ has no proper $\{a,b\}$-edge-weighting exactly when both bipartition classes have odd order and every component of this forest satisfies two conditions. First, every component satisfies the preceding degree-and-matching condition. Second, within each component, the degree of a vertex $v$ in the forest plus twice the number of incident edges $e$ outside the forest for which the component of $T-e$ not containing $v$ has an odd number of vertices from each bipartition class is independent of $v$. For every fixed pair of distinct real weights, the proofs yield a linear-time algorithm that decides whether a proper $\{a,b\}$-edge-weighting exists and constructs one when it does.

DeLeo, Henderschedt, and Wells introduced a finite-horizon version of the classical de Bruijn–Erdos interval discrepancy problem. Starting from the unit interval, one repeatedly splits an existing interval into two until $n$ intervals are present, and one minimizes the largest ratio between the longest and shortest intervals over all intermediate partitions. They constructed the lex-merge strategy, whose discrepancy is $2^{1-1/\lceil n/2\rceil}$, and conjectured that this value is optimal for every $n$. We prove the conjecture. More generally, we establish a sharp lower bound for arbitrary binary refinement processes of positive masses: any process that starts with one positive mass, repeatedly replaces one mass by two positive masses with the same total, and terminates with $n$ masses must at some stage have largest-to-smallest ratio at least $2^{1-1/\lceil n/2\rceil}$. The proof tracks the minimum mass under refinement and uses the forced survival of a piece near the midpoint of the process. We also record the corresponding universal lower bound for $r$-ary refinements.

We investigate the analyticity of the free energy of the Ising model in the presence of a non-zero external magnetic field, at high temperature, and at low temperature. Using the Fernandez–Procacci convergence criterion for cluster expansions, together with generating-function techniques and graph-theoretical methods, we derive improved convergence conditions in all three regimes. In particular, the generating-function approach yields sharper estimates for polymers and contours in the strong-field and low-temperature regimes, while a new high-temperature expansion based on Veblen's theorem provides a substantially larger analyticity region than the classical results in the literature.

The proof of Proposition 1 in the paper [J. Math. 2022, (2022) #7783128] contains a gap, but its statement is correct. Here, we fix this gap.

We establish a Kneser-based anticoncentration estimate for uniform subset sums in composite cyclic groups. The estimate contains a periodic loss and is weaker than its prime-modulus counterpart. Nevertheless, together with known small- and large-set results, it proves that, for every fixed $t\geq2$ such that $\mathbb{Z}_t$ is strongly sequenceable and every sufficiently large prime $p$, every subset of $\mathbb{Z}_{tp}\setminus\{0\}$ has a valid ordering, thus establishing the analogue of Graham's rearrangement conjecture for this family of composite cyclic groups. We then identify the structural source of this loss. An inverse theorem shows that failure of the stabilizer-free growth underlying prime-type anticoncentration forces almost all of the set into a proper subgroup or one of its cosets. We exploit this structure by reverse absorption. Iterating the resulting dichotomy between non-periodic anticoncentration and structured concentration proves that every subset of \[ \mathbb{Z}_k\setminus\{0\}, \qquad k=\prod_{i=1}^{s}p_i^{e_i}, \qquad \sum_{i=1}^{s}e_i\leq L, \qquad p_1<\cdots<p_s\leq\gamma p_1, \] admits a valid ordering whenever $L$ and $\gamma$ are fixed and the primes $p_i$ are sufficiently large.

We give an explicit simple bridgeless cubic graph on 112 vertices with no Petersen coloring, and hence no normal 5-edge-coloring. The graph is identified by the SHA-256 digest in Theorem 1.1. It is assembled from three copies of a four-pole L and a claw six-pole C; in turn, L is assembled from four copies of a four-pole F and one copy of C, where F is obtained from the Petersen graph by deleting the endpoints of one edge. We give direct SAT formulations for Petersen colorings and normal 5-edge-colorings. CaDiCaL 3.0.1 returned UNSAT for both formulas, and drat-trim verified the resulting DRAT proofs. The ancillary archive contains the construction, an explicit relabeling, the encoders, certificates, hashes, and verification programs. Combined with a theorem of Ma, Mattiolo, Steffen, and Wolf, the counterexample also implies that infinitely many connected simple bridgeless cubic graphs have no Petersen coloring. We also give a separately verified, nonisomorphic $D_3$-symmetric 112-vertex counterexample. We do not address whether 112 is minimum.

We prove a colorful volume Helly theorem for convex sets in $\mathbb R^2$: There is a constant $V>0$ such that if $\mathfrak F_1,\mathfrak F_2,\mathfrak F_3,\mathfrak F_4$ are finite families of convex sets in $\mathbb R^2$ and if $|\bigcap_1^4F_i|\ge V$ for every transversal $F_i\in \mathfrak F_i,\; (i=1,\ldots,4)$, then $|\bigcap \mathfrak{F}_i|\ge 1$ for some $i$. Here $|A|$ is the Lebesgue measure of $A\subset \mathbb R^d$. The main ingredient is the following theorem. Let $Q_1,\ldots,Q_4\subset\mathbb R^2$ be convex quadrilaterals of area at most $1$, where of course each $Q_i$ is the intersection of 4 halfplanes. Then for every $Q_i$ there is one of these halfplanes $H_i$, say, such that $|\bigcap_1^4 H_i| \le 4096$.

We prove that, up to row and column permutations and complement operations, the only complement minimally non-totally unimodular matrices are the cycle matrices $C_3$ and $C_5$. This settles a conjecture of Chervet, Grappe, and Vallée. As a consequence, every simplicial cone generated by the rows of a totally equimodular matrix admits a regular unimodular Hilbert triangulation.

When a variety $V_\varphi$ equals the image of a polynomial map $\varphi$ whose coordinate functions are combinatorial generating polynomials (i.e.~polynomials enumerating combinatorial objects), the geometry of $V_\varphi$ reflects identities satisfied by the generating polynomials. The resulting interplay between combinatorics and algebraic geometry can be used to answer questions about $V_\varphi$. A recent technique proposes to do so using a partially ordered set (poset) $P_\varphi$ defined via the coefficient vectors of the polynomials defining $\varphi$. This paper characterizes the poset $P_\varphi$ when the generating polynomials defining $\varphi$ enumerate subgraphs of a directed tree known as treks. The characterization is used to compute the linear span of $V_\varphi$, prove it is toric and deduce a basis for its vanishing ideal. It is also shown that this poset of trek polynomials for a directed tree is a so-called $\pi$-system if and only if the tree satisfies a property characterized via Stanley's P-partitions. As an additional consequence, it is shown that the varieties for two distinct directed trees intersect in a strictly lower-dimensional variety. This solves an instance of the structural identifiability problem in the graphical models program from statistics.

Bulgarian solitaire is a well-studied, no-choice, no-loss, one-player game involving stacks of cards. More formally, it is a self-map on the set of partitions of a fixed integer $n.$ As a finite dynamical system, its long-term behavior is well understood. Every trajectory ends in a cycle. The partitions that are in a cycle are parameterized by binary vectors, and the cycles by binary necklaces. Call a partition separated if distinct part sizes differ by at least two. The vast majority of partitions belonging to a cycle are not separated. Motivated by this fact, we consider a variant where the player has choices, but is restricted to separated partitions and, if unable to make a legal move, may lose. We prove that for $n>73$, there are cycles, and hence winning initial positions. We analyze the game for small values of $n$ and describe computations which, together with our main result, show that there are cycles for $n \in \{2,6,8,11,14,16,18,21\}$ and for $n \ge 23$, but for no other $n.$

We show that, up to isomorphism, the number of $Q$-points is either finite, $2^{\mathfrak{d}}$ or $2^{\mathfrak{c}}$. This answers a question asked by Borodulin-Nadzieja, Martínez-Celis, Morawski and Świerczyńska, and by Halbeisen and the authors. We also show that under mild hypotheses, the existence of infinitely many $Q$-points implies the existence of non-atomic $Q$-measures, and of $2^{\mathfrak{c}}$-many Tukey-top $Q$-points, strengthening results of Raghavan and of Borodulin-Nadzieja et al..

We show that isoclasses of iterated tilted algebras in type $A_n$ are in bijection with non-crossing spanning trees up to rotation on a convex n+1-gon. This is done by constructing a relationship between iterated tilted algebras up to isomorphism and exceptional sets up to isomorphic Hom-Ext quiver.

The coefficients that determine the Hilbert series of the superspace coinvariant ring are indexed by hook-shaped partitions. We give a manifestly positive combinatorial interpretation of these coefficients, together with several generating functions for them. Specializing this Hilbert series at $u=-q^2$, we show that its coefficients are differences of binomial coefficients. Consequently, this proves a conjecture of Sagan–Swanson (2024) that these coefficients are palindromic up to sign. More generally, for every $m \geq 1$ we obtain closed-form expressions for the $u = -q^m$ specialization.

For a graph G let F(G) denote the largest order of a regular induced subgraph of G, and let f(n) = min{F(G) : |V(G)| = n}. A problem of Erdos, Fajtlowicz and Staton asks whether f(n)/log n -> infinity. Dyson and McKay have recently proved f(n) <= (sqrt(2e)+o(1)) sqrt(n) via a type-based random model (arXiv:2604.08215). This paper concerns the opposite direction within the type-based family. We conjecture that every model of the family satisfies F(G) >= (sqrt(2e)-o(1)) sqrt(n) asymptotically almost surely, so that sqrt(2e) is the optimal constant obtainable from the family, and we prove the corresponding statement at exponent level – F(G) >= n^{1/2-eps} – conditionally on two explicitly stated hypotheses: a local limit lower bound for inhomogeneous degree sequences, and a correlation estimate at sublinear overlaps. The complementary overlap range, including full overlap, requires no correlation hypothesis. We further record the exact-curvature first-moment computation that independently identifies sqrt(2e), including a uniform trace bound on its determinant correction, and certified exact computations at orders up to 48 consistent with the predicted crossover F ~ min(n^{2/3}, sqrt(n/L)). This version substantially revises v1; see the note in Section 1.

The Zarankiewicz number Z(m,n,s,t) is the maximum number of edges in a bipartite graph with parts of orders m and n containing no copy of Ks,t. We give one combined, certificate-based computer-assisted proof for two finite slices and a corrected neighboring frontier: Z(12,n,3,3) = 6n (18 <= n <= 22), Z(13,22,3,3) = 137, Z(13, 18, 3, 3) = 116, Z(14, 18, 3, 3) = 124, Z(15,18,3,3) = 132, Z(14, 17, 3, 3) = 118, Z(15, 17, 3, 3) = 126, 132 <= Z(16,17,3,3) <= 133. The load-bearing new upper bounds are the exact 12 x 18 and 13 x 18 certificate packages. Their orbit certificates exclude every hypothetical matrix at the next edge count. Deletion lemmas and explicit witnesses close four neighboring cells, while the 16 x 17 entry is deliberately reported as an interval because only its 132-edge lower witness and the published 133 upper bound are certified here. Separately, the 13 x 22 proof excludes 138 ones by reducing to 83 degree profiles, rationally separating 77 of them, and eliminating the remaining six by marked-row congruences, leave enumeration, modular Gram tests, and exact Farkas certificates. All accepted claims are replayed by standard-library Python and exact integer/rational arithmetic; floating-point optimization is used only to discover certificates.

There are several methods for searching for graphs with prescribed properties, such as SAT solvers and specialized generators. These methods return the result as raw data: an adjacency matrix or a string encoding. The raw data certifies that the graph exists, but it does not reveal any structural properties of the graph. We ask whether one can automatically discover a short algebraic description if only this raw data is provided. We look for a description such as a Cayley graph $\mathrm{Cay}(\Gamma, S)$ or a lexicographic product $C_5[K_3]$. We address this question with a neurosymbolic approach. We propose an agent that runs on a general-purpose large language model with no fine-tuning or per-target training. The model interleaves reasoning with calls to the computer algebra system SageMath: it analyzes the target graph, proposes and tests candidate constructions, and revises them until the output matches the target. The agent communicates with SageMath through a Model Context Protocol (MCP) server, which we release as a general-purpose bridge. Whether a construction matches the target is checked by a single exact isomorphism test, and therefore rests on the symbolic side and not on the model. We test the approach on a benchmark of 100 highly symmetric graphs, namely two-orbit graphs on up to 25 vertices; the benchmark was fixed in advance. Our agent could find verified algebraic constructions for all of them, without falling back to raw encodings. A strong template-enumeration baseline reaches only about $20\%$, and a catalog lookup could not identify any of these graphs. However, construction quality declines when symmetry is removed. As a concrete application, we identify the smallest known counterexample to the Bernhart-Kainen dispersability conjecture, a $16$-vertex graph that enumeration found as raw data. For this graph, our agent found an explicit algebraic construction.

It is a well known result by Singmaster that any integer $d$ divides almost all binomial coefficients. The study of the structure and the size of the exceptional set has been of interest for many decades. In the case where $d$ is a prime power, these sets are well understood and their size is known. However, if $d$ has at least two distinct prime factors, no non-trivial bounds are known. In this paper, we will provide the first non trivial bound on the number of binomial coefficients coprime to 6.

A convex polygon is called small if its diameter is at most one. Reinhardt proved the universal perimeter bound $\operatorname{perim}(P)\le U_n:=2n\sin(\pi/(2n))$, and the bound is attained whenever $n$ has a nontrivial odd divisor. The remaining power-of-two cases have resisted exact solution beyond $n=8$. We give computer-assisted proofs of the first three cases, $n=16,32,64$, and in each case prove uniqueness of the maximizing congruence class. The proof architecture is common to all three cases: pass to the difference body $P-P$; encode its reconstruction by a sign code; prove that every global maximizer is saturated, so all difference-body vertices lie on the unit circle; localize every competitive configuration near the regular angle vector; exhaustively screen the sign codes using exact arithmetic; eliminate all nonwinning dihedral orbits; and prove uniqueness inside the winning code by strong convexity and a quantitative KKT argument. The exact certificates cover $2^{15}$ normalized codes for $n=16$, $2^{31}$ normalized codes for $n=32$, and all $2^{64}$ half-codes for $n=64$, leaving respectively $16$, $96$, and $896$ survivors before orbit elimination. The accompanying source package contains the verifiers, recorded outputs, hashes, and separate computational cross-checks.

We analyse topology of random simplicial complexes in the medial regime. We show that these complexes are highly connected and have homotopy type of iterated suspensions. One of our main tools is a new combinatorial criterion for high connectivity of simplicial complexes, which is more flexible than conicity. We show that topological complexity of random simplical complexes in the medial regime is bounded above by 2 and it equals 2 for a class of homogenous medial regime random simplicial complexes, a.a.s.

We study per-colour independent (k)-rainbow domination and its connection with independent domination in generalized prisms. Building on the known prism identity and the trivial regime above the maximum degree, we focus on the boundary case where the number of colours equals the maximum degree. For every fixed (k\ge 3), we prove that the decision problem remains NP-complete even on a highly restricted class of graphs: (C_4)-free, bipartite, ((k,2))-biregular subdivision graphs arising from simple (k)-regular graphs. The reduction gives an exact correspondence between optimal rainbow-independent dominating functions on the subdivision graph and proper (k)-edge-colourings of the original graph. We also introduce an excess parameter measuring how far the domination number lies above its natural lower bound. For cubic graphs, this excess coincides with the classical edge-colouring degree and therefore with standard resistance parameters for subcubic graphs. These results reveal a sharp one-unit threshold: above the maximum degree the problem becomes trivial for every graph, while at the boundary NP-hard instances already occur within a very narrow structural family.

Let $A$ be the smallest set of positive integers containing $2$ and $3$ such that $ab-1\in A$ whenever $a,b\in A$ are distinct. We prove that $A$ has positive lower density, answering a problem of Erdős attributed to Hofstadter.

For $d\ge 1$, let $L(d)\in\mathbb N\cup\{\infty\}$ be the supremum of the lengths of paths in $\mathbb Z^d$ whose steps are standard basis vectors and whose vertex sets contain no collinear triple. We prove that \[ \log_2\log_2 L(d)\ge \frac{2}{5}d-O(1) \] for all sufficiently large $d$.

The subtree polynomial of a tree is the generating function that enumerates its subtrees according to their orders. Brown and Mol conjectured that every subtree root of a tree of order $n\ge 2$ lies in the disk \[ \left\{z\in\mathbb C: |z|\le 1+\sqrt[n-1]{n-1} \right\}. \] We prove this conjecture by introducing a recursive comparison method based on an extremal problem over integer compositions. We further characterize the equality case: the upper bound is attained if and only if $n$ is even and the tree is the star; in this case the unique boundary root is $-1-\sqrt[n-1]{n-1}$. We also show that every nonzero subtree root $z$ satisfies \[ |z|>\sqrt[n-1]{n-1}-1. \] The lower bound is asymptotically sharp as $n\to\infty$. For odd $n$, although the upper bound is not attained, it is asymptotically sharp as $n\to\infty$.

For a prime $p$ and $k\in\mathbb{F}_p$, the generalized Markoff graph $G_{p,k}$ is an undirected graph whose vertices are the solutions over the finite field $\mathbb{F}_p$ of the normalized Markoff equation \[ x_1^2+x_2^2+x_3^2=x_1x_2x_3+k, \] where two vertices are adjacent if they differ by a Vieta involution. The Markoff graph $G_p$ is obtained from $G_{p,0}$ by removing the origin. The structure of $G_p$ has been the subject of extensive study; in particular, a major breakthrough of Bourgain, Gamburd, and Sarnak established that $G_p$ contains a giant connected component. Combined with Chen's remarkable divisibility theorem, this implies that $G_p$ is connected for all sufficiently large primes $p$. In the same paper, Bourgain, Gamburd, and Sarnak further asked whether the family $\{G_p\colon \text{primes }p\geq 5\}$ forms an expander family. This motivates us to investigate the robustness of connectivity in the Markoff graphs. The main result of this paper is proved in the general setting: for every prime $p\geq5$ and every $k\in\mathbb{F}_p\setminus\{4\}$, each connected component $C$ of $G_{p,k}$ with $|V(C)|\geq 3$ is $2$-connected. Reducing to the case $k=0$, we conclude that if the Markoff graph $G_p$ is connected, then it is in fact $2$-connected. Consequently, the Markoff graph $G_p$ is $2$-connected for all sufficiently large primes $p$. This is sharp in the sense that $G_p$ is not $3$-connected for any prime $p\geq 7$.

The factorisation of graph polynomials often reflects combinatorial decomposition. For a nonempty loopless graph $G$, we first prove that the two-variable interlace polynomial $q(G;x,y)$, introduced by Arratia, Bollobás and Sorkin, is irreducible over $\mathbb{C}[x,y]$ if and only if $G$ is connected, exactly paralleling the classical irreducibility theorem for the Tutte polynomial. The loopless hypothesis is essential: we construct an infinite family of connected looped graphs whose two-variable interlace polynomials are reducible. For a nonempty graph $G$, we prove that Courcelle's multivariate interlace polynomial $C_G(u,v;\mathbf{x},\mathbf{y})$ is irreducible over $\mathbb{C}[u,v,x_a,y_a:a\in V(G)]$ if and only if $G$ is connected.

A subset $S \subseteq V(G)$ is called a dual-server dominating set if there exists a partition $\pi_S=\{R,B\}$ of $S$ such that every vertex in $V(G)\setminus S$ has at least one neighbour in $R$ and at least one neighbour in $B.$ The minimum cardinality of a DS-dominating set of $G$ is called the dual-server domination number, denoted by $\gamma_{ds}(G)$. In this paper, we investigate the dual-server domination number of several graph operations. We establish exact values for the dual-server domination number of the join, Cartesian product, and corona of graphs. We also determine the dual-server domination number of the splitting graphs of paths, cycles, and complete bipartite graphs. These results extend the study of dual-server domination and provide further insight into its behaviour under graph operations.

For any $n$, there exists finite simple graphs $G$ and $H$ such that $\chi(G),\chi(H) > n$ and $\chi(G \times H) = 4$.

We develop a symbolic elimination theory for finite systems of recursive containment inequalities whose unknowns are convex subsets of a finite-dimensional real vector space. The right-hand sides are formal expressions generated from variables and parameters by convex linear combinations, finite union, and a positive geometric join encoding strict convex combinations. We prove that every parameter assignment has a unique smallest convex-set-valued solution and give a finite Gaussian-elimination-type procedure that eliminates the unknowns while preserving this solution and produces parameter-only expressions for its coordinate sets. More generally, let $\mathcal B$ be a family of subsets containing $\emptyset$ and closed under finite unions, nonnegative dilation, Minkowski sums, positive geometric joins, and convex hulls. If all parameter sets lie in $\mathcal B$, then every coordinate set of the smallest solution lies in $\mathcal B$; when these operations are effective, so is the resulting description. In particular, if the parameters are finite unions of hemihedra—where a hemihedron is a bounded convex semi-linear set, equivalently a convex finite union of relative interiors of polytopes—then each coordinate set is a hemihedron and admits a quantifier-free semi-linear description. We apply this theory to lamination hulls. For \[ V=U\oplus\bigoplus_{i=1}^{k}W_i,\qquad \dim W_i=1,\qquad \Lambda=\bigcup_{i=1}^{k}(U+W_i), \] we prove that the lamination hull $G_{\Lambda}^{(\infty)}(S)$ of every finite $S\subset V$ is semi-algebraic and effectively computable by a quantifier-free formula over the reals.

We introduce a new algorithm for computing Kostka-Foulkes polynomials. It arises from a combinatorial procedure that computes the transition coefficients between successive pre-canonical bases for spherical Hecke algebras, introduced by Libedinsky, Patimo, and the first author, in order to interpolate between the standard and canonical bases of the spherical Hecke algebras. Using this algorithm, we prove that the coefficients of the polynomials in the transition matrix from any pre-canonical basis to the next one has nonnegative coefficients. This establishes the positivity conjecture for pre-canonical bases and, moreover, yields a strictly stronger result that uncovers additional positivity phenomena beyond the original scope of the conjecture. As a by-product, this method yields a combinatorial algorithm for computing Lascoux's atomic decomposition of canonical basis elements. Finally, our results show that, after applying the Satake isomorphism and dualizing with respect to the Hall inner product, pre-canonical bases correspond to a new family of Schur-positive symmetric functions.

A classical geometric result says that every nonzero cycle of the mod-$2$ incidence map from $d$-subsets to $(d-1)$-subsets of $[n]$ has support at least $d+1$, with equality attained by the boundary of a simplex on $d+1$ vertices. We prove an analogous result for the subspace lattice of $\mathbb{F}_q^n$, determining the minimum support size of a nonzero $d$-cycle over a field $K$ of characteristic $p \mid q+1$. Surprisingly, the boundary of a $(d+1)$-space is not always optimal. Shorter cycles occur for $d=1$, and for $d=2$ when $n\ge4$, and otherwise, the boundary of a $(d+1)$-space is shortest. For $d\ge4$, we prove a gap-stability result: every cycle with support less than $(2-10/q)$ times the minimum is a multiple of the boundary of a $d+1$ space. We also construct support-controlled cones, yielding a direct geometric analysis of the dimensions in which the homology groups of the subspace incidence complex vanish and explicit lower bounds on its coboundary expansion. The degree-$1$ expansion estimate is an ingredient in the stability theorem.