Papers

Judicious partition problems ask for vertex partitions of graphs or hypergraphs that optimize several quantities simultaneously. In this paper, we investigate judicious partitions of graphs and hypergraphs in which each class meets many edges and establish the following results. (1) Every hypergraph with nonnegative edge weights and all edges of size at most $2$ has a bipartition in which each vertex class meets edges of total weight at least $(w_1-\Delta_1)/2+2w_2/3$, where $w_i$ is the total weight of the edges of size $i$, and $\Delta_1$ is the maximum weight of an edge of size $1$. (2) Every hypergraph with all edges of size at most $3$ has a bipartition in which each vertex class meets at least $m_1/2+3m_2/4+7m_3/8+o(m_1+m_2+m_3)$ edges, where $m_i$ is the number of edges of size $i$. (3) For any integer $k\ge4$, every graph with $m\ge2(k-1)(k-2)$ edges has a partition into $k$ classes, each meeting at least $2m/(2k-1)$ edges. Both the coefficient of $m$ and the edge threshold are best possible. (4) For all sufficiently large $m$, every $4$-uniform hypergraph with $m$ edges has a partition into four classes, each meeting at least $4m/7$ edges. The first three statements are conjectures of Bollobás and Scott, and the last is a conjecture of Bollobás and Thomason on 4-uniform hypergraphs. All of the above results are best possible.

More than 50 years ago, Golomb and Welch conjectured that no tilings of $\mathbb{Z}^n$ by Lee balls of radius $r$ exist for $n \geq 3$ and $r \geq 2$. This conjecture remains open even under the additional assumption that the tiling is a lattice tiling. In general, there are two known effective approaches to the lattice case which are based on symmetric polynomials and on the arithmetic of group-ring equations, respectively. In this paper, we develop both approaches. First, we determine all coefficients of the Q-polynomials associated with Lee balls; previously, only leading coefficients and certain special cases were known. Second, for arbitrary radii, we give necessary and sufficient conditions for the existence of lattice tilings by Lee balls in terms of group-ring equations, extending earlier results for radii $r=2$ and $3$. We then derive new necessary conditions for such tilings. For every radius $3\le r\le 50$, we prove that the set of dimensions for which no lattice tiling exists has positive density in \(\mathbb{Z}^+\). We also give an algorithm that combines the available necessary conditions and apply it to all pairs $(n,r)$ for which the corresponding Lee ball of radius $r$ and dimension $n$ has size less than $2^{30}$. Among these $1{,}358$ pairs, the combined method excludes $1{,}356$, leaving only $(n,r)=(35,3)$ and $(805,3)$.

Let $G$ be a connected graph. The eccentric subgraph number $\epsilon(v)$ of a vertex $v$ of $G$ is defined as $\epsilon(v)=\min\{f_G(v,u): u\in V(G)\}$, where $f_G(v,u)$ is the number of connected subgraphs of $G$ containing both $v$ and $u$. The eccentric subgraph index $ES(G)$ of $G$ is defined as $ES(G)=\displaystyle\sum_{v\in V(G)}\epsilon(v).$ In this paper, we obtain the unicyclic graph that maximizes the eccentric subgraph index among all unicyclic graphs on $n$ vertices with a fixed girth. The graph that maximizes the eccentric subgraph index among all unicyclic graphs on $n$ vertices is also obtained. We then characterize the trees that maximize the eccentric subgraph index over trees on $n$ vertices with fixed diameter. Among all connected graphs on $n$ vertices with a fixed number of pendant vertices, the graph which maximizes the eccentric subgraph index is also characterized.

The maximum likelihood degree of a Gaussian graphical model measures the algebraic complexity of its likelihood equations. This paper studies maximum likelihood degrees of Gaussian graphical models through chordal completion. When a graph becomes chordal after one missing edge is added, its maximum likelihood degree is determined by the maximal cliques and clique-tree separators containing that edge. This recovers Uhler's formula for complete bipartite graphs with one part of size two, and extends it to deleted-spine clique books, whose degree is unchanged when a page is thickened to a clique. For several fill edges, the same method gives a product formula when no clique or separator bag contains two fill edges. We also determine four classes of vertices at which clique blow-up preserves the degree. Two follow from known results, and two are established here.

Poset games form a fundamental class of combinatorial games that includes classical games such as Nim and Chomp. Determining the outcome of a poset game is known to be PSPACE-complete even for posets of height at most three. However, the exact computational complexity of Two-Level Poset Game, played on posets of height at most two, has remained an open problem for over a decade. We resolve this problem by proving that Two-Level Poset Game is PSPACE-complete via a polynomial-time reduction from Avoid True on positive CNF formulas.

We study a continuous interpolation between the type $B$ and shifted type $A$ Narayana triangles and its extension through affine moments of the continuous $q$-ultraspherical (Rogers) measure. For every fixed $0<q<1$ and $-1<\beta<1$, these affine moments form a coefficientwise Hankel-totally positive sequence in the polynomial variable $t$. The proof rests on a general continuant criterion: decreasing nonnegative off-diagonal weights and coefficientwise positivity of the leading continuants imply total positivity of the full tridiagonal matrix. A telescoping identity gives positive certificates for shifted continuants and stability under coordinatewise decreases of the weights. We determine the exact power of $t$, palindromicity, and extreme coefficients of arbitrary Hankel minors. Classical limits recover the continuous Narayana family, including its moment representation and gamma positivity. We further prove that the continuous Narayana transformations preserve strong $t$-log-convexity for every real $\theta\ge0$, and that the $d$-Hoggatt transformations have the same preservation property for every integer $d\ge1$. The preservation proofs use the Zhu–Sun criterion and a mixed-minor one-sign-change argument whose local ingredient is a hypergeometric hitting-probability inequality.

A set $A$ of integers is an $h$-basis for $n$ if every integer in $[0,n] = \{0,1,2,\ldots,n\}$ belongs to the sumset $hA$, that is, can be represented as the sum of exactly $h$ not necessarily distinct elements of $A$. The classical postage stamp problem asks for the largest integer $n_h(k)$ such that $[0,n_h(k)] \subseteq hA$ for some set $A$ of nonnegative integers of size $k+1$. We consider the effect of allowing negative elements. Let $n^{\flat}_h(k)$ be the largest integer such that $[0,n^{\flat}_h(k)] \subseteq hA$ for some set $A$ of integers of size $k+1$ containing at least one negative integer. For $k=2$, we have $n^{\flat}_h(2) < n_h(2)$ if $h$ is odd or $h=4$ and $n^{\flat}_h(2) = n_h(2)$ if $h$ is even and $h \neq 4$. Proofs of these comparison results were autonomously discovered and formally verified in Lean by https://aristotle.harmonic.fun/}{Aristotle}, a formal reasoning agent developed by https://www.harmonic.fun/}{Harmonic}. In this paper we give new proofs of these results.

In 2018, Goddard and Henning conjectured that every cubic graph has four total dominating sets covering each vertex at most twice, and asked the analogous question for transversals of $3$-uniform $3$-regular hypergraphs. We prove the conjecture, which also answers the question in the affirmative.

Let $p$ be an odd prime, and let $\rho\colon G\to \GSp_{2n}(\Z_p)$ be an irreducible symplectic residually multiplicity free representation. We define the symplectic extension graph $\Gamma_\rho^\GSp$ associated with $\rho$ to be the directed graph whose vertices are the residual factors of $\rho$ and a directed edge between two vertices corresponds to a nonsplit extension between the vertices realized by $\rho$. Using the Euclidean Bruhat–Tits building associated with $\GSp_{2n}(\Q_p)$, under some assumptions, we prove the existence of certain paths in $\Gamma_\rho^\GSp$ and show that $\Gamma_\rho^\GSp$ is a disjoint union of nonempty strongly connected subgraphs. Moreover, we provide examples to show that the result we obtain is optimal.

We study symmetric 2-(v, k, {\lambda}) designs admitting a flag-transitive point-primitive subgroup G of automorphisms, where gcd(k, {\lambda}) = p and p is a prime. In this paper, we show that G is of affine or almost simple type.

We introduce a $q$-analogue of the bicolored Eulerian quasisymmetric functions by incorporating an additional grading arising from affine length, obtained by interpreting bicolored permutations as affine permutations. We also provide an intrinsic description of this refinement in terms of bicolored permutations by introducing notions of alignments and crossings, together with an explicit bijection identifying these statistics with the alignments and crossings in the existing literature. Finally, we prove that our refinement is symmetric by expressing it in terms of the Theta operators appearing in the Theta coinvariant Conjecture and the modified Macdonald symmetric functions. Assuming the Theta coinvariant conjecture implies the Schur-positivity of our refinement.

We investigate Conjecture 7.4 of Guo and Krattenthaler \cite{GK}, which predicts that for every positive integer $n$, the polynomial \[ P_n(q) = \frac{(1-q)^2}{(1-q^{10n-1})(1-q^{15n-1})}\qbin{30n}{5n} \] has non-negative coefficients, except for $q^1$ and $q^{125n^2-25n+3}$, which equal $-1$. We study this problem through three main perspectives: First, by linking the boundary coefficients to the second differences of the partition function, we settle the first and last $25n+1$ coefficients via a novel partition injection. Second, by introducing a “defect” generalization of Andrews' classical lemma, we reduce the conjecture to an almost-unimodality property and employ a uniform saddle-point analysis to prove it analytically for all large $n \ge 2\cdot 10^{29}$. Finally, we connect these quotients to graph binomial coefficients, providing a natural orbit-counting interpretation via Burnside's lemma on directed cycles and paths.

As its 40th anniversary nears, we present a history of the International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC), through interviews with figures from its past, present, and future.

We study orthogonal $(4,3)$-equipartitions of finite measures absolutely continuous with respect to Lebesgue measure: every three of four mutually orthogonal affine hyperplanes must divide each measure into eight equal parts. For every number $m$ of measures, we determine the exact dimension threshold of Musin's polynomial criterion and express it in terms of the binary expansion of $m$. The threshold coincides with the geometric lower bound precisely when $m=2^j-1$. Consequently, $\Delta^*(2^j-1,4,3)=7\cdot2^{j-1}-2$ for every $j\geq1$.

Optimal Morse vector fields on closed surfaces, i.e.\ fields with the minimal possible number of critical points (a single source and a single sink), are classified up to topological trajectory equivalence by one-cycle signed chord diagrams in Kybalko, Prishlyak and Shchurko (2018). We recall this construction and the associated duality, which corresponds to reversing the direction of the flow, in a unified encoding in which both endpoints of a chord carry the same label, and we make it algorithmic. We give an explicit traversal procedure that detects one-cycle diagrams, a canonical form of an equivalence class under cyclic shifts, reversal and relabeling of chords, and a construction of the dual diagram. On this basis we describe an algorithm that enumerates all one-cycle signed chord diagrams with a given number of chords, both for orientable and for non-orientable surfaces, groups them into equivalence classes, pairs each class with its dual, and identifies the self-dual ones. The algorithm is implemented in Python and archived in Zenodo; its output is validated against the Harer–Zagier numbers in the orientable case and against orbit-size counts in both cases. We also note that, when a one-cycle diagram is read as a cellular embedding of a one-vertex graph, its dual diagram describes the embedding of the dual graph.

We construct an infinite family of solutions to the Mondrian art problem with absolute defect bounded above by $280$, of side lengths $n_0 = 315$, $n_1 = 106785$, and $n_{j+2} = 340n_{j+1} - n_j$, where $n_j$ is congruent to $315 \pmod{630}$. This absolute bound shows that the minimum defect does not necessarily increase with $n$, providing a counterexample to a conjecture which has been open since the problem's original proposal. Our design is derived from a well-known seven-rectangle dissection over the real quadratic field $\mathbb{Q}(\sqrt{19})$, with non-integer side lengths; we tailor the side lengths to be integers via an infinite Pell family. Using the same method, we devise a second family with defect $560$ that contains infinitely many side lengths which are divisible by any given positive integer, implying that for any $k$ there are infinitely many side lengths $n \equiv 0 \pmod{k}$ with defect bounded above by $560$. This constant bound offers a dramatic improvement on the previous quadratic bounds.

The Chan–Robbins–Yuen polytope $\mathrm{CRY}_{m+1}$ has normalized volume $\prod_{j=1}^{m-1}C_j$, a product of Catalan numbers. Zeilberger proved the formula using the Morris constant-term identity; finding a combinatorial proof remained an open problem. We give such a proof by counting nonnegative integer flows. We add an extra edge from each vertex to a common sink and count flows according to how many of these edges carry positive flow. A double count proves a special case of a recurrence of Morales and Shi and gives these counts in terms of Narayana numbers. Deleting the first vertex then yields the Catalan product. We also give an explicit bijection for the recurrence and prove the corresponding reduction formula posed by Postnikov.

A $u\hbox{-}v$ separator in $G$ is a set $S\subseteq V(G)\setminus\{u,v\}$ such that there is no $u\hbox{-}v$ path in $G\setminus S$. A minimal separator in $G$ is a set $S$ such that for some $u,v\in V(G)\setminus S$, $S$ is a $u\hbox{-}v$ separator in $G$ but no proper subset of $S$ is. A set $S$ is bisimplicial if it is the union of at most two cliques. Recognizing graphs in which every minimal separator is the union of at most $k$ cliques is polynomial-time solvable for $k=1$ and NP-hard for every fixed $k\geq 3$. We settle the remaining case $k=2$ by giving a polynomial-time algorithm to decide whether every minimal separator in a graph is bisimplicial. A set $S$ is triad-free if its independence number $\alpha(S)$ is at most two. Given a graph $G$ and two vertices $u,v$, the problem of finding a $u\hbox{-}v$ separator $S$ with $\alpha(S)\leq k$ had the same complexity gap: it was known to be polynomial-time solvable for $k=1$ and NP-hard for every fixed $k\geq 3$. We resolve the remaining case $k=2$ by giving a polynomial-time algorithm that finds a triad-free $u\hbox{-}v$ separator or determines that none exists.

An internal partition of a graph is a partition of its vertex set into two nonempty parts such that every vertex has at least half of its neighbors in its own part. DeVos asked whether, for every fixed positive integer $r$, all but finitely many $r$-regular graphs admit an internal partition. This was previously known to hold only for $r\in\{3,4,6\}$. In this paper, we confirm this for $r\in\{5,8\}$ by proving that every $r$-regular graph on at least $10^7$ vertices has an internal partition.

For every fixed integer $r\ge3$, we prove that the Turán density of every $r$-uniform hypergraph $F$ with $m\ge1$ edges satisfies $\pi(F)\le1-c_rm^{-(r-1)/r}$, where $c_r>0$ depends only on $r$. This improves Sidorenko's general bound, whose gap from $1$ is of order $m^{-1}$. Complete $r$-uniform hypergraphs show that the exponent $(r-1)/r$ is optimal. The proof combines a potential argument for partial embeddings with the Lovász Local Lemma.

We prove that there exists an absolute constant $c > 0$ such that the following holds for every $k \ge 3$ and $p \ge n^{-c / \log \log k}$. Letting $\delta > 0$ and $D \sim [n]_p$, with high probability every ${S \subset [n]}$ with $|S| \ge \delta n$ contains a $k$-term arithmetic progression whose common difference lies in $D$. This improves the best known bounds for the threshold of Szemerédi's theorem with random differences for all sufficiently large $k$, previously of the form ${p \ge n^{-2/k+o(1)}}$, due to Briët and Castro-Silva. We obtain our improvement via a small cover lemma, in the sense of Alon and Pham's work on random Cayley graphs, and its proof crucially relies on a construction of Green and Ruzsa in the context of the arithmetic Kakeya conjecture. The usage of the latter was suggested to us by GPT 6 Astra.

Let $V_i(n)$ denote the minimum worst-case number of comparisons needed to find the $i$-th smallest of $n$ distinct elements. We construct algorithms showing $V_7(16)\le28$ and $V_8(16)\le29$, improving the previously reported upper bounds of 30 and 31. Together with known lower bounds, these results establish $V_7(16)=28$ and leave $V_8(16)\in\{28,29\}$. For 17 elements, we establish $V_5(17)=27$ and improve the upper bounds for ranks 6 through 9 to 29, 30, 31, and 31, respectively. Every new upper bound has an explicit decision-graph certificate verified by a static checker developed independently of the search. We also derive a lower bound for selection from a partially ordered state by combining the Fussenegger-Gabow weight with its order-reversed counterpart. All new upper bounds and this lower bound are formally verified in Lean 4. For $V_8(16)$, we show that a lower bound based solely on the total number of decision-tree leaves cannot establish $V_8(16)\ge29$. The algorithms were found using fixed-budget search, information-guided comparison ordering, and proof-number search. Proof-number search was decisive in finding the 28-comparison algorithm; in our experiments, refuting a comparison budget remained substantially more expensive than finding an algorithm within it.

The rational exponents conjecture of Erdős and Simonovits asserts that for every rational $r\in [1,2]$ there exists a graph $H$ such that $\mathrm{ex}(n,H)=\Theta(n^r)$. We present a proof of this conjecture claimed by Epoch AI, explaining how it builds upon ideas and methods developed by many researchers.

We construct an approximate sampler for finite doubly free-boundary Macdonald rail-yard processes with Macdonald, boundary, and edge parameters in $(0,1)$. The construction allows arbitrary finite sequences of additions and removals of horizontal or vertical strips and all four boundary types. It reverses a finite commutation–reflection history from a partition sequence whose entries are equal, with the common partition weighted by both boundaries. We derive local reconstruction kernels from the skew Cauchy, Littlewood, and branching identities. Bulk and boundary updates combine integer increments with conditional shape sampling at a prescribed size; same-sign swaps use finite conditional resampling. For $K$ reflection periods and an initial partition-size cutoff $M$, the algorithm terminates almost surely and samples the resulting approximating law exactly. We prove total variation convergence to the target process as $K,M\to\infty$ and give explicit bounds for both truncation errors, decaying geometrically in the cutoffs for fixed input parameters. Under fixed parameter bounds, we also bound the expected operation count of direct enumeration in a unit-cost model. We further construct an exact rejection sampler for the initial partition law without a size cutoff or evaluation of its normalizing constant. Using this sampler removes the size-truncation error, leaving only the error from the finite reflection history.

We prove four conjectures of Takigiku and Tsuchioka consisting of eight Rogers–Ramanujan type identities. Two conjectures involve triple sums and a third involves quadruple sums, and their product sides are certain level $2$ principal characters of $A_{13}^{(2)}$. The fourth conjecture gives multisum representations of certain level $2$ principal characters of $A_{2\ell-1}^{(2)}$. The proofs rely on the Bailey pair method, finite sum identities involving Gaussian polynomials, and the quintuple product identity.

We develop a new approach to the Joint Intersectivity Conjecture of Bergelson, Leibman, and Lesigne for commuting transformations. The conjecture asserts that the necessary divisibility condition is the only obstruction to polynomial multiple recurrence and, consequently, to the multidimensional polynomial Szemerédi theorem. We establish the conjecture for pairwise independent polynomials, obtaining the first general result for sequences of arbitrary length beyond the classical one-transformation setting. Our argument is inspired by the Furstenberg-Katznelson approach and its polynomial enhancement due to Bergelson-Leibman. Its main novelty, however, lies in the development of new techniques that allow us to bypass the use of the polynomial van der Waerden theorem, on which these methods traditionally rely, and for which no suitable analogue is currently available in our setting. In particular, we prove a Nil-Bohr returns theorem for compact extensions in systems with nilpotent structure, as well as a nil-plus-null decomposition for polynomial multicorrelation sequences that preserves joint intersectivity and positivity.

For a graph G of order n with adjacency eigenvalues lambda_1(G) >= ... >= lambda_n(G), the cospectrality of G within the set G of all graphs of order n is the smallest spectral distance from G to another graph of G. Abdollahi and Zakeri conjectured that for every n >= 4 the cospectrality of the complete tripartite graph K_{n,n,n}, both in the Manhattan and in the Euclidean spectral distance, is attained precisely at K_{n-1,n,n+1}. We show that both conjectures are false for every n >= 4, that is, in the whole range in which they are stated. The counterexample is the graph H_n obtained from K_{n-1,n,n} by adding a vertex adjacent to the part of cardinality n - 1, and it is the natural generalization of the graph which the authors themselves exhibited for n = 3 and considered to be exceptional. We determine the spectrum of H_n in a closed form, and we show that the two spectral distances tend to 1 and to 1/2 respectively, instead of to (2*sqrt(3))/3 and to 2/3 as conjectured. On the other hand, we show that in the Euclidean distance the conjecture becomes asymptotically true when the competing graphs are restricted to complete multipartite graphs, so that it fails because a graph of rank four beats the conjectured minimizer.

We consider a natural extension of the classical saturation problem to oriented graphs, defined as the minimum number of edges in an oriented graph $H$ on $n$ vertices that avoids a fixed oriented graph $G$, but adding any missing edge to $H$ creates a copy of $G$. Our main result shows that saturation functions of oriented graphs attain at least four distinct orders of magnitude. In particular, if $G$ is acyclic, then its saturation function is bounded if and only if $G$ contains an isolated edge; otherwise, it is linear. Certain tournaments together with an isolated edge give further infinite examples of bounded and linear saturation functions. Two additional orders of magnitude are $\Theta(n \sqrt{\log n})$ and $\Theta(n \log n)$. For these two, the lower bounds are obtained by adapting a recently developed approach for the saturation problem in edge-ordered graphs, while the matching upper bounds are constructive. Finally, we study the semisaturation problem, in which we require only that adding any missing edge to $H$ creates a copy of $G$. We completely characterize the possible orders of magnitude: the semisaturation function is either bounded, linear, or $\Theta(n \log n)$.

Let $\tau(G)$ denote the maximum number of pairwise edge-disjoint spanning trees contained in a graph $G$. Zhang and Fan [J. Graph Theory, 2026] posed the problem of determining the corresponding tight spectral-radius condition for every $s$-edge-connected graph with \[ k+1\leq s\leq2k-1, \] together with a characterization of the associated extremal graphs. In this paper, we completely resolve this problem.

We characterize several properties of higher-arity function classes, specifically finite $\VC_k$-dimension, slicewise finite $\VC$-dimension, and finite slicewise Littlestone dimension, in terms of generalizations of Rademacher complexity. These characterizations sets up simple new proofs of several results on finite $\VC_k$-dimension and slicewise finite $\VC$-dimension. These include the preservation of finite $\VC_k$-dimension under taking expectations and uniform law of large numbers statements for both properties. All of these results apply naturally to real-valued function classes as well as boolean-valued classes. We also prove a new adversarial uniform law of large numbers for classes with finite slicewise Littlestone dimension.