Papers

In this note, we resolve the remaining open case of a conjecture by Han and Zhao concerning the codegree threshold for Hamilton $\ell$-cycles in $k$-uniform hypergraphs. Specifically, we prove that for integers $k\ge 3$, $3k/4\le \ell<k$, with $k\not\equiv 0 \pmod{k-\ell}$, and for all sufficiently large $n$ divisible by $k-\ell$, every $n$-vertex $k$-uniform hypergraph $H$ satisfying \[ \delta_{k-1}(H)\ge \frac{n}{(k-\ell)\left\lceil \frac{k}{k-\ell}\right\rceil} \] contains a Hamilton $\ell$-cycle. Our proof builds on the framework of Gan, Han and Xu, and refines their argument to obtain, at the exact threshold, the required family of paths.

Let $F$ be a $k$-uniform hypergraph, abbreviated as $k$-graph. The codegree Turán density $\gamma(F)$ is the supremum over all $\gamma \in [0,1)$ such that, for arbitrarily large $n$, there exists an $n$-vertex $F$-free $k$-graph $H$ whose every $(k-1)$-subset of vertices lies in at least $\gamma n$ edges. Let $PG_m(q)$ be the projective geometry of dimension $m$ over finite field $\mathbb{F}_q$. In this paper, we prove that $\gamma(PG_m(q)) \ge \frac{1}{p}> 0$ for all $m$ and $q$, where $p$ is the smallest prime divisor of $q+1$. This resolves an open problem proposed by Keevash and Zhao (JCT-B, 2007). Moreover, we determine the exact codegree Turán density of $PG_4(q)$ when $q$ is an odd prime power.

We extend Gårding's theorem to homogeneous posynomials: if a finite positive sum of monomials with arbitrary nonnegative real exponents is zero-free on a product of right half-planes, then its degree-normalized root is concave. Consequently, zero-freeness in a sector of aperture $\alpha\pi$ implies $\alpha$-fractional log-concavity. This sharpens generic mixing and domain-sparsification guarantees for fixed-size matchings and nonsymmetric determinantal point processes. The result was developed in an AI-assisted interaction initiated and checked by the author; Codex also assisted with assembling and typesetting the manuscript.

In this paper, we introduce multiple Schur series, which are defined by Schur-type sums over semi-standard Young tableaux and generalize both Schur multiple zeta values and multiple Eisenstein series. To study their algebraic structure, we construct a connected, commutative, graded Hopf algebra of Young tableaux and identify its linearized quotient with the quasi-shuffle algebra. Within this Hopf algebra and its quotient, we establish several relations, including a hook formula and the Jacobi–Trudi formula. Furthermore, we relate this Hopf algebra to the ring of symmetric functions, which yields polynomial reduction formulas for tableaux with constant entries. As applications, we recover Schur multiple zeta values, introduce Schur multiple Eisenstein series together with a $q$-analogue of Schur multiple zeta values, and discuss their (quasi)modularity.

We prove asymptotic formulae for positive real $(p,q)$-Rogers-Szegő polynomials when the quadratic term in the expansion about the middle coefficient vanishes. For coefficient indices whose distance from $n/2$ is of order $n^{3/4}$, the coefficient ratios have a quadratic-quartic exponential limit. A uniform bound valid for all indices allows the ratios to be summed and gives locally uniform convergence of the centred generating polynomials to a Fourier–Laplace integral. We also obtain an asymptotic formula for the sum of the coefficients, convergence of all rescaled moments, weak convergence of the normalised coefficient measures, and convergence with multiplicity of the zeros tending to $w=1$.

We show that one of the main cases of the stable forking conjecture, stability of the forking relation over a base in a finite-rank supersimple theory, is determined by finitely many pregeometries in each rank. This case of the stable forking conjecture has long had an implicitly well-known pregeometric interpretation: there is a set of matroids $\mathcal{G}_{n}$ such that the forking instability in rank $n$ is equivalent to the pregeometry on some rank-one partial type (over a finite set) embedding a matroid in $\mathcal{G}_{n}$. Our contribution is to show that this set of matroids $\mathcal{G}_{n}$, determining based forking stability in rank $n$, can be chosen to be finite. The main part of our proof was already accomplished in rank $3$ by Peretz, but does not extend as stated to higher ranks (and may or may not directly extend in a weaker sense to higher ranks, by shrinking terms). However, we obtain a sufficient substitute for Peretz's work in ranks $n > 3$: we turn Peretz's original universal result into an existence theorem. The rest of our proof refines an argument from multi-experiment parameter definability, originating from work in applied model theory by Li, Meshkat, Ovchinnikov, Pillay, Pogudin and Scanlon.

A homogeneous set in a graph is a clique or a stable set. The Erdős–Hajnal conjecture states that, for every graph $H$, there exists $c>0$ such that every $H$-free graph on $n$ vertices has a homogeneous set of size at least $n^c$. Nguyen, Scott and Seymour proved that for every $d>0$, graphs of VC-dimension at most $d$ have the Erdős–Hajnal property, confirming a conjecture of Fox, Pach and Suk. In particular, they showed that every such $n$-vertex graph contains a homogeneous set of size at least $n^{\eta_d}$ for some $\eta_d\ge 2^{-2^{O(d)}}$. In this paper, we give a sharper quantitative bound on the homogeneous sets in graphs of VC-dimension at most $d$, showing that one may take $ \eta_d\ge (Cd)^{-d}, $ where $C$ is an absolute constant. Equivalently, every graph $G$ of VC-dimension at most $d$ satisfies \[ \max\{\omega(G),\alpha(G)\}\ge |G|^{(Cd)^{-d}}. \] Our proof refines the iterative sparsification method of Nguyen, Scott and Seymour. The main enhancement is to apply the VC-dimension assumption directly, which gives a more efficient induction and thus improves the dependence on $d$. We also derive quantitative consequences for polynomial Rödl subgraphs, hypergraph Ramsey bounds under bounded VC-dimension, induced-free and viral formulations, tournaments, NIP and semi-algebraic graphs, Boolean combinations of relations of bounded VC-dimension, graphs whose adjacency matrices have bounded rank, graphs of bounded sign-rank, and graphs defined by dot-product threshold representations.

A $q$-kernel of a digraph $D$ is an independent set $Q\subseteq D$ such that every vertex of $D$ is reachable from $Q$ by a directed path of length at most $q$, which is a natural generalization of kernels and quasikernels. In this paper, we establish three results on generalized quasikernels. Firstly, we prove that any $n$-vertex source-free bipartite oriented graph with no directed 4-cycles has a quasikernel of size at most $17n/35$. Secondly, we show that every digraph with no $(r-1)$-source set contains $r$ pairwise disjoint $(3r-2)$-kernels, where $r\ge 2$. At last, we consider unicyclic digraph with a directed cycle of length $2\ell$ and bipartition $U\cup V$, and we prove that for every odd integer $q\ge 3$, there exist two $q$-kernels $Q_U\subseteq U$ and $Q_V\subseteq V$ such that \[ |Q_U|+|Q_V| \le 2\cdot \frac{\lceil \ell/(q+1)\rceil}{\ell} |V(D)|. \] These results confirm two conjectures and give an affirmative answer to a question posed by Spiro in European Journal of Combinatorics 133 (2026), 104307.

A proper sub-box of $A=\{0,1,2\}^d$ is a product $S_1\times\dots\times S_d$ with each $\varnothing\neq S_i\subsetneq\{0,1,2\}$. A double cover is a finite multiset of proper sub-boxes covering every point of $A$ exactly twice; write $f(d)$ for the minimum size of a double cover. Leader, Milicevic and Tan asked whether $f(d)\ge 2^d$ for all $d$ (Question 4.1 of the PatternBoost paper of Charton-Ellenberg-Wagner-Williamson), analogous to the Alon-Bohman-Holzman-Kleitman partition bound $2^d$. No better than the trivial volume bound was previously known, for any $d\ge 2$. We prove the first nontrivial lower bounds. A modular refinement of the parity argument gives $f(d)\ge 2^{d+1}/(d+1)$; a slicing argument gives $f(4)\ge 19$, $f(5)\ge 33$, both above $2^d$, resolving the question for $d=4,5$ – the first cases beyond the trivially known $d\le 3$. A finer "line rigidity" argument yields $f(6)\ge 60$, breaking the profile-statistic barrier (capped at $57$, shown here). This is formally verified in Lean 4: $f(6)\ge 60$ is machine-checked on the three standard Mathlib axioms alone. On the upper-bound side, a dimension-lifting construction $f(r+3)\le 6\cdot 2^r+3f(r)$ gives $f(6)\le 81$ (improving the known $82$) and $f(d)\le(\tfrac65+o(1))2^d$ asymptotically; a refinement improves the constant to $\tfrac87$. This makes partial progress on PatternBoost's problem of reducing their constant $1.28$, and refutes the closed-form guess $f(d)=5\cdot 2^{d-2}+1$ from $d=7$ on. Together, $60\le f(6)\le 81$. Finally we isolate the construction-side obstruction – an "S+c=2^j+1" phenomenon, every skeleton sitting exactly one box past the partition bound – and show it is of a piece with the Leader-Milicevic-Tan question itself.

Let $q=2^e$ with $e\ge2$ even, put $d=(q^2+q+1)/3$, and let $\sigma(X)=X+X^d+X^{dq}$ be the permutation of $\mathbb F_{q^2}$ introduced by Ding, Qu, Wang, Yuan, and Yuan. For $\alpha\in\mathbb F_q^*$, define the Boolean function \[ f_\alpha(x)=\operatorname{Tr}_{q^2}\bigl(\alpha(\sigma^{-1}(x))^3\bigr), \qquad x\in\mathbb F_{q^2}. \] In this paper, we determine the complete Walsh distribution of $f_\alpha$ in the remaining cubic case $\alpha\in(\mathbb F_q^*)^3$. More precisely, these functions are not bent but are $2$-plateaued: their Walsh values are precisely $0$ and $\pm 2q$, with exact multiplicities. The main new tool is a completion method for the outside Walsh coefficients: the punctured Fourier transform arising from the outside reduction is filled on the missing line, a modification invisible to outside frequencies, and the completed function is then identified with a Boolean component of a Kasami APN monomial. The APN property supplies a fourth-moment identity which, together with the known subfield spectrum and a Hasse divisibility congruence, forces the pointwise cubic spectrum.

A graph is homogeneously traceable if each vertex is an endpoint of a Hamiltonian path. Chartrand, Gould, and Kapoor (1979) proved irregular homogeneously traceable nonhamiltonian graphs exist for every order $n\ge 9$. Hu and Zhan (DAM, 2022) considered the $3$-regular and $4$-regular cases and asked which order $n$ can be realized by a $k$-regular homogeneously traceable nonhamiltonian graph. Recently, Liu and Qiao (DAM, 2026) showed that $n=p(k-1)+q\ge 6(k-1)+q$ can be realized if $k\ge 5$ is odd and $q\in\{0,2,4,6\}$, or $k\ge 6$ is even and $q\in\{0,1,...,6\}$. In this paper, we show that for any $k\ge 6$ and $n\ge 6(k-2)$, there exists a $k$-regular homogeneously traceable nonhamiltonian graph of order $n$.

OpenAI's recent disproof of the Erdős unit distance conjecture marked a milestone for AI in mathematics. It also inspired another breakthrough: a human disproof of the Erdős–Szemerédi sum-product conjecture over $\mathbb R$. In this paper, we present a simple agent built on GPT-5.5 Pro. Using a problem-agnostic, three-stage prompting pipeline – proof-plan proposal, proof construction, and review – the agent autonomously generated correct proofs that the sum-product conjecture is false over $\mathbb R$ in 7 of 8 independent trials; in the remaining trial, it identified an unresolved gap in its argument. The seven proofs are diverse: some are close to existing unit-based constructions, while others avoid units by using $L^p$-type regions of algebraic integers. The system used an average of 132.4k reasoning tokens per trial. We release the code, intermediate outputs, and generated proofs, providing a reproducible, data-contamination-free case study in autonomous proof generation.

Let \(G\) be a finite simple graph. We study perfect matchings through two complementary viewpoints: reductions to bipartite permanent terms and the directed cycle covers counted by the ordinary adjacency permanent. The main identity is an explicit odd-cycle-indexed form of the classical cycle-cover expansion: it separates \(\perfmat(G)^2\), the even-cycle-cover contribution coming from superposing two perfect matchings, from the contribution of cycle covers containing odd cycles. This gives a nonnegative odd-cycle defect \(\delta_{\mathrm{odd}}(G)\). Combining the identity with the Bregman–Minc inequality yields a structural refinement of the Alon–Friedland degree-sequence bound. We prove product, positivity, and fractional-perfect-matching interpretations for the defect; show that for \(K_{2n}\) the defect asymptotically accounts for almost the entire Bregman–Minc target; and derive from this a derangement identity. We also study near equality in the Alon–Friedland bound: we classify all one-edge perturbations of the extremal graphs, record the uniform obstruction coming from \(K_4\), and formulate a sharp bounded-degree gap problem whose two natural candidate extremal graphs cross between maximum degrees \(9\) and \(10\).

An integer $n \ge 1$ is cyclic if $\gcd(n,\varphi(n))=1$ (equivalently, if every group of order $n$ is cyclic), and Sophie Germain cyclic if both $n$ and $2n+1$ are cyclic. Let $C_\sigma(N)$ count the Sophie Germain cyclic integers in $[1,N]$. Cohen conjectured that $C_\sigma$ is subadditive, $C_\sigma(m+n) \le C_\sigma(m)+C_\sigma(n)$ for all $1 \le m \le n$ (his Conjecture 66), having checked $m,n \le 10^6$ without finding a counterexample. We give one: at $m=31$, $n=3928$, $C_\sigma(3959)=697 > 696 = C_\sigma(31)+C_\sigma(3928)$. The argument is short, and is verified by the Lean 4 kernel.

AlphaZero has demonstrated that a neural-guided Monte Carlo Tree Search can achieve superhuman performance, but strong play does not necessarily imply perfect play. We study this gap in two oracle-evaluable domains with contrasting structure: Connect Four, a solved partisan game with exact game-theoretic values, and Chomp, an impartial game whose optimal play is governed by Grundy-number structure. Under a unified self-play $+$ MCTS pipeline, we compare vanilla AlphaZero, a multi-frame variant (limited to Chomp), and an AlphaZero Auxiliary Loss (AZAL) that adds oracle-derived policy supervision. We find that vanilla AlphaZero achieves strong play across both domains but cannot preserve the exact trajectories required for optimal play: in Connect Four, it fails to maintain the optimal line of play, while in Chomp, it fails to consistently restore the $g=0$ invariant. On rectangular Chomp boards, multi-frame inputs alone do not remove this gap. Nevertheless, AZAL substantially improves oracle consistency across multi-seeded full-game traces and sampled-state evaluations. On Chomp, AZAL reaches perfect full-game oracle consistency on 10x11 and high but not complete consistency on 9x10; on Connect Four, AZAL improves oracle-match rate and delays the first oracle mistake, but does not reach perfect play.

A solution determining the parity of unit entries in Redheffer matrices is given. The solution solves the problem by enumerating two disjoint sets from which set membership determines parity. The solution framework uses generating functions.

We determine the asymptotics of a game inspired by classic vector balancing problems in combinatorial discrepancy theory. In this game, which we call the online Komlós game, two players, Paul and Carol, update the state vector $y$ in $\mathbb{R}^m$, initially placed at $0$. At each round, Paul chooses freely a set of $n$ vectors in the Euclidean unit ball, and Carol chooses, for each such vector, whether to leave it unchanged or reverse its sign. The resulting vectors are all added to $y$, and the game proceeds to a new round. After $T$ rounds, the game ends, and the $\ell_\infty$ norm of the state vector $y$ is determined. Paul's objective throughout the game is to maximize this norm, and Carol's objective is to minimize it. As $T$ gets large, we establish that the leading order term of the value of this game is $\sqrt{T/2\tau}$, where $\tau$ is the extinction time of the unit cube in $\mathbb{R}^m$ under a curvature-based flow characterized by the values of $m$ and $n$. When $n\geq m-1$, this flow is the mean curvature flow, and we show that $1/\sqrt{2\tau} =\Theta(\sqrt{\log m})$. Our results build upon the work of Kohn and Serfaty on deterministic games and mean curvature flow, combined with Banaszczyk's $\ell^2$ analogue of the Beck-Fiala theorem. As the large $T$ limit of the online Komlós game amounts to a localization of the classic Komlós problem, we hope this work can shed light on this and other vector balancing problems. Our results generalize to the version of the online Komlós game with the final value given by an arbitrary norm in $\mathbb{R}^m$.

Tao and Vu introduced a discrete analogue of John's theorem in which convex progressions are approximated by generalized arithmetic progressions. In the covering version of this problem, one asks for a small GAP containing all lattice points of a given origin-symmetric convex body. We prove that every such convex progression in dimension $n$ admits an infinitely proper GAP cover whose size is within a factor $O(n)^{2n}$ of the cardinality of the original set, improving the previously known factor $O(n)^{3n}$. We also show that a loss of order $\Omega(n)^n$ is unavoidable for infinitely proper GAP covers.

We introduce a framework for tackling questions in discrete optimization associated with parametric constraint matrices. More precisely, the constraint matrices have entries that are polynomials in one variable and all subdeterminants of these matrices are polynomials in a given prescribed set $S$. Two key problems arise in this context. The first is the recognition problem: can a matrix of this form be recognized in polynomial time? The second is the optimization problem: given an integer program whose constraint matrix is of this form, can it be solved in polynomial time? We answer both questions affirmatively for a particular set $S$ consisting of nine linear forms. The matrices we consider are of themselves independent interest; they arise as matrix projections of certain bimodular matrices that admit two distinct unimodular projections.

Inversion sets of permutations in the affine symmetric group $\widetilde{S}_n$ were studied extensively by Björner and Brenti. One of their methods for encoding an inversion set is through an affine inversion graph, which is a certain weighted graph on vertex set $[n]=\{1,2,\ldots,n\}$. Subsequent work by Papi characterized which graphs arise as affine inversion graphs. In this paper, we provide an alternative characterization in terms of a simple local condition on each triangle in a weighted tournament graph. This new characterization was produced with the assistance of ChatGPT, which suggested several key insights that simplified portions of Papi's original characterization. Consequences of our characterization include efficient algorithms for recognizing inversion graphs and inversion sets. Furthermore, we give bounds on the weights along directed paths, and we show that standardizing the labels on an induced subgraph results in another inversion graph. We conclude with a new order $O(|R|+n^{3})$ algorithm for testing if a given set $R$ is the inversion set of an affine permutation.

In a binary polynomial optimization problem (BPO, in short) we are maximizing a multilinear polynomial expression depending on n binary variables. This is a hard optimization class, containing many NP-hard problems, including unconstrained quadratic binary optimization. Several tractable special classes were considered in the literature, including problems with bounded tree-width (Crama, Hansen, Jaumard, 1990), Berge-acyclic problems (Buchheim, Crama, and Heck, 2019), $\beta$-acyclic problems (Del Pia and Di Gregorio, 2022, 2023), limited reach problems (Clausen, Crama, Lusby, Rodríguez, and Ropke, 2024), and $\alpha$-acyclic problems with bounded rank (Del Pia and Khajavirad, 2025). We focus on a general variable elimination scheme for BPO, and develop the unique explicit multi-linear polynomial form for the equivalent BPO problem obtained after the elimination of a given subset of the variables. The obtained closed form representation of such an equivalent BPO problem allows us to characterize new special classes for which this elimination method, when applied recursively, provides a computationally efficient solution. Our approach is elementary1, algebraic, and provides efficient solution to a wide problem class that properly generalizes all of the above mentioned tractable special cases.

We can regard a generalized quadrangle as a hypergraph in which points and lines are identified with vertices and hyperedges, respectively. A vertex coloring is said to be rainbow on a hyperedge if all vertices contained in that hyperedge are assigned pairwise distinct colors; if no hyperedge is rainbow, the coloring is termed rainbow-free. For a given hypergraph $H$, the maximum integer $k$ for which there exists a rainbow-free $k$-coloring is called the upper chromatic number of $H$, and is denoted by $\overline{\chi}(H)$.

We study subindices, subfactors, and index stability in the cyclic group $\mathbb{Z}_n$. We prove several theorems that not only confirm a conjecture and resolve some open problems about index stability of such groups, but also provide basic tools for the characterization of finite $k$-index stable groups. As a consequence, we completely characterize all 2-element index stable subsets of $\mathbb{Z}_n$, obtain an exact closed formula for their density, and determine all $n$ for which every 2-subset is index unstable. Finally, we present some problems and a research project extending the study to 3-subsets and general $k$-subsets.

We prove the matroid intersection conjecture, due to Nash-Williams \cite{ahaziv}, for infinite matroids: If $M_k = (E, {\mathcal I}_k)$ are matroids for $k \in \{0,1\}$, both having the same base set $E$, then there is $J^* \in {\mathcal I}_0 \cap {\mathcal I}_1$ and disjoint subsets $J_k\subseteq J^*$ for $k\in \{0,1\}$ such that $\text{cl}_{M_0}(J_0) \cup \text{cl}_{M_1}(J_1) = E$.

Gilbreath's conjecture asserts that if one starts with the sequence of primes and takes successive absolute differences to create a triangular array, then the left diagonal of this array consists entirely of ones after the first row. In this paper, we show that the analogue of this conjecture for a Cramér random model holds, in which the (normalized) prime gaps are replaced by independent random variables with geometric distributions of logarithmic size. We also give some preliminary analysis of the associated continuous probabilistic model for this problem, as well as a deterministic "inverse theorem" that isolates the specific obstructions to Gilbreath's conjecture (assuming a Cramér type bound on prime gaps), namely long blocks of zeroes, or very long shallow $\{0,d\}$-valued blocks for some $d \geq 2$.

Let $q$ be a prime power, $F=\mathbb F_q(\!(t^{-1})\!)$, $G=\mathrm{SL}_2(F)$, $\Gamma=\mathrm{SL}_2(\mathbb F_q[t])$, and $K=\mathrm{SL}_2(\mathbb F_q[\![t^{-1}]\!])$, and let $U<G$ be the upper unipotent subgroup. We study right $K$-spherical averages along $U$ on $X=\Gamma\backslash G$. Expanding translates of compact $U$-orbits and compact-open F$\unicode{x00F8}$lner-ball averages become terminal layers of rooted descendant shadows in the Bruhat–Tits tree. In the even sector, we compute the Haar height law and signed finite-scale discrepancy exactly. This yields $K$-spherical equidistribution for compact-orbit translates and, for irrational boundary endpoints, for F$\unicode{x00F8}$lner-ball averages. For a depth-$N$ shadow rooted at height $k$, with cutoff $M=N-k\ge0$, bounded-profile errors are $O_q(q^{-M})$ in the backward state and $O_q(q^{-M/2})$ uniformly for moving roots, while the shadow law eventually agrees exactly with the Haar law on every fixed finite height window. For $|\Phi(2m)|\le Cq^{\alpha m}$, $\alpha<2$, three rate regimes arise, with a linear-in-scale factor at $\alpha=1$ and explicit moving-root dependence. Artin continued-fraction digits eventually encode the cutoff and these rates excursion by excursion through individual digit degrees.

We construct a measure that exhibits two aspects of a new type of universality and dramatically simplifies the integration of tensors $T_{a_1,a_2,\ldots,a_D} \in \mathbb{C}$ ($a_1,\ldots,a_D=1,\ldots,N$) at large $N$. In contrast to matrix integration, in which matrix traces canonically yield the integrand, tensors need additional information (equivalent to a $D$-coloured graph $B$) to contract their indices and form a tensor trace $B(T)$. We show that, whenever each $B_1,\ldots, B_n$ can be obtained by a recursive construction known as melonicity, then the leading order in $N$ of the integral of $ {B_1}(T) {B_2}(T) \cdots {B_n}(T) $ is independent of the – often intricate – combinatorics of the traces $B_i$, but also, to our surprise, independent of $D$ as far as $D\geq 3$. Instead, at large $N$, these integrals are some functions (indexed by $n$) of the number of vertices $2p_i$ of $B_i$ which we call melonic polynomials. Melonic traces cumulants with respect to any ('interacting') measure \[ \exp\Big\{-N^{D-1} \sum_{i=1}^m g_i {B_i}(T)\Big\} \mathrm{d}\mu_0(T) \quad (g_1,\ldots,g_m \in \mathbb{R}, \mathrm{d}\mu_0(T) =\text{the tensor Gaussian}) \] with each $B_i$ melonic, can be computed with our universal measure that replaces each $B_i$ by a canonical trace depending only on $p_i$. We prove that any two melonic tensor models are indistinguishable at large-$N$, independently of the number of tensor indices (first universality aspect), and of the fine-grainedness of their interactions (second universality), being a sufficient condition that the couplings (the parameters $g_i$ above) agree and their respective traces are monomials with the same degree in $T$.

Let $k$ and $\ell$ be positive integers. The family $C(k,\ell)$ consists of all digraphs obtained from two internally vertex-disjoint directed paths of lengths at least $k$ and $\ell$, respectively, and identifying their initial vertices and their terminal vertices. Addario-Berry, Havet and Thomassé (JCT-B, 2007) asked whether, for any positive integers $k$ and $\ell$ with $k+\ell \ge 4$, the chromatic number $\chi(D)$ is at most $k+\ell-1$ for every $C(k,\ell)$-free strongly connected digraph $D$. Let $D$ be a $C(k,\ell)$-free Hamiltonian digraph. Kim, Kim, Ma and Park (JGT, 2018) showed that $\chi(D) \le k+\ell$ and the bound is attained when $k+\ell=5$. In this paper, we prove that $\chi(D) \le k+\ell-1$ for $k+\ell\ge 6$ and this bound is best possible for all $k+\ell\geq 6$, which resolves the problem posed by Addario-Berry, Havet and Thomassé for Hamiltonian digraphs.

The Balister–Győri–Schelp (BGS) conjecture asks whether every zero-sum list of $2^{s-1}$ nonzero vectors in $\mathbb{F}_2^s$ is the prescribed-difference profile of a perfect matching. The conjecture remains open in general, whereas the classical Hall hyperplane case is solved when all prescribed differences cross between two affine copies of a hyperplane. We isolate the smallest mixed case beyond Hall: exactly two prescribed differences are internal. Although only two requests have changed type, the complete Hall permutation is replaced by a prescribed-difference bijection between two punctured copies of the hyperplane, with two unknown deleted vertices on each side. We call this the two-hole problem. We develop a new combinatorial method for prescribed-difference matchings, based on counting and the character structure of the binary vector space. Unlike the known Hall-type methods, which construct a matching through a sequence of local algorithmic choices, our approach proves existence through a global noncancellation phenomenon. This loss of algorithmic structure is compensated by a different advantage: the method can retain global boundary information that local exchanges do not control. As a first application, it gives a new proof of the binary Hall theorem, and it then yields a complete solution of the two-hole problem with no multiplicity assumption. We also give direct constructive proofs for symmetric even-multiplicity two-hole and four-hole families. More broadly, the new technique provides a framework for studying further subfamilies of the BGS problem by measuring how far their matching structure departs from the Hall case.

Recently, there has been significant interest in applying the method of moments developed by Wood and others to study distributions of finite abelian groups that arise in number theory and combinatorics. When the moments do not grow too fast, they determine a unique distribution. We construct large families of distributions that have the same moments. These families include several distributions that arise naturally in the study of sandpile groups of families of random graphs. Wood determined the distribution of Sylow $p$-subgroups of sandpile groups of Erdős–Rényi random graphs. This was extended by Mészáros to sandpile groups of random $d$-regular graphs, who observed an interesting special case when $d$ is even and $p = 2$. We study Sylow $p$-subgroups of sandpile groups of random bipartite graphs and similarly find a special case for $p =2$. Although this distribution differs from that of Mészáros, we show that they have the same moments and fit into our broader construction. To compute the moments of the distributions we study, we apply combinatorial tools from the theory of Hall–Littlewood functions.