Papers

Erdős et al. (JCT-B, 1989) conjectured that, for integers $r\ge 2$ and $\delta\ge 2$ with $3r-1\mid\delta$, every connected $K_{2r+1}$-free graph of order $n$ and minimum degree $\delta$ has diameter at most $ \frac{3r-1}{r}\cdot \frac{n}{\delta}+O(1)$. Czabarka et al. (JCT-B, 2021) later proposed the following generalization: for every $k\ge 3$ and $\delta\ge\left\lceil\frac{3k}{2}\right\rceil-1$, every connected $K_{k+1}$-free graph of order $n$ and minimum degree at least $\delta$ has diameter at most $(3-\frac{2}{k})\cdot\frac{n}{\delta}+O(1)$. We disprove the latter conjecture, including its $k$-colorable version, for every $k\ge 7$ and sufficiently large $\delta$. When $k=2r\ge 8$ and $3r-1\mid\delta$, our construction also disproves the conjecture of Erdős et al. (JCT-B, 1989).

Let $P$ be a $d$-dimensional lattice polytope with Ehrhart polynomial $L_P(t)$. Motivated by the study of Ehrhart positivity and magic positivity, we investigate the Taylor coefficients $\mathsf{A}_j(P;k)$ in the shifted expansion $L_P(t)=\sum_{j=0}^{d}\mathsf{A}_j(P;k)(t-k)^j$ about a real center $k$. In this paper, we obtain the following four main results. (i) We give exact formulas for these coefficients in terms of the ordinary Ehrhart coefficients, the $h^*$-vector, elementary symmetric functions, and Stirling numbers. (ii) We denote by $\tau(P)$ and $\tau^+(P)$ the smallest nonnegative integral centers at which all Taylor coefficients are nonnegative and positive, respectively. If $s$ is the degree of the $h^*$-polynomial, then $0\leq\tau(P)\leq\tau^+(P)\leq\min\{\max\{0,s-1\},\lfloor\frac{d-1}{2}\rfloor\}$. As an application, we slightly improve an upper bound due to Beck, De Loera, Develin, Pfeifle, and Stanley. That is, every real root of $L_P(t)$ lies in $[-d,\lfloor\frac{d-1}{2}\rfloor)$. (iii) Let $\rho(P)$ be the smallest nonnegative real center such that the Taylor coefficients are nonnegative. If $\lambda_{\mathbb{R}}(f)$ denotes the largest real zero of $f(t)$, with value $-\infty$ when no such zero exists, then $\rho(P)=\max\{0,\max_{0\leq j<d}\lambda_{\mathbb{R}}\!(L_P^{(j)})\}$. (iv) We establish structural properties of the Taylor coefficients $\mathsf{A}_j(P;k)$, including derivative interlacing, palindromic reflection symmetries, and Laguerre and Newton inequalities. As a final note, these results provide a systematic partial answer to an open problem listed on the website of the American Institute of Mathematics.

The Poincaré polynomials of the Deligne-Mumford space $\overline{M_{0,n}}$ of stable genus 0 curves have been widely studied by several authors such as Keel and Manin. These polynomials can be computed via a recursive formula that is combinatorial in nature, and their exponential generating functions satisfy elegant functional and differential equations. In this paper, we state some combinatorial formulas to the Poincaré polynomials of Hassett's heavy-light moduli spaces $\overline{M_{0,w_{m,n}}}$, with $m$ heavy marked points and $n-m$ light marked points. We express the Poincaré polynomials recursively in terms of the Möbius function of a certain lattice of set partitions. In the case of $m=2$, we get a Losev-Manin space. We give an explicit formula for the Poincaré polynomial or $\overline{M_{0,w_{2,n}}}$ by counting ordered set partitions; and give a recursive formula for this polynomial similar to that in the setting of $\overline{M_{0,n}}$. We prove this recursive formula using geometric and topological properties of the stratification of Losev-Manin spaces; and use an exponential generating function to simplify this recursive formula. Finally, we give a remarkable generalization to the ordered Bell numbers and a recurrence relation for this generalization.

We establish various connections between classes of colored and bounded ordinary partitions on one hand, and colored but not necessarily bounded binary and $b$-ary partitions on the other hand. Many of these results are based on special recurrence relations, some of which are new. We also obtain several classes of identities for sequences of colored $b$-ary partitions, and there are a few results concerning compositions.

Let $p$ be a prime and let $\mathcal{P}_p$ be the set of primitive elements of $\mathbb{F}_p$. Inspired by the work of Cohen, Oliveira e Silva and Trudgian on consecutive primitive elements, and by the work of Chang on arithmetic progressions in multiplicative subgroups of finite fields, in this paper, using estimates for multiplicative character sums over systems of linear forms together with the relative Szemerédi's theorem of Conlon, Fox and Zhao, we show that, for every fixed integer $k\ge3$ and any fixed number $0<\delta\le 1$, each subset $A\subseteq\mathcal{P}_p$ with $\#A\ge\delta\#\mathcal{P}_p$ contains a nontrivial $k$-term arithmetic progression, provided that $p$ is sufficiently large. Also, by applying Behrend's theorem, we construct a large subset $A'$ of $\mathcal{P}_p$ with $\#A'=\lfloor(\#\mathcal{P}_p)^{1-\varepsilon}\rfloor$ such that $A'$ contains no nontrivial $k$-term arithmetic progressions.

The Job Sequencing and Tool Switching Problem (SSP) is a well-known combinatorial optimization problem arising in the context of flexible manufacturing. Since the seminal work of Tang and Denardo (1988), the SSP has received significant attention in the literature, leading to the development of numerous exact and heuristic approaches. Despite these efforts, several benchmark instances proposed decades ago and containing only 20 jobs have remained unsolved to proven optimality. In this work, we propose an exact algorithm for the SSP, namely the Combinatorial Branch-and-Bound (C-B&B) algorithm, which combines two distinct branch-and-bound algorithms, each introducing novel features compared with the existing literature. The former relies on a new branching scheme designed to reduce the size of the implicit enumeration tree, together with a collection of new bounding functions. The latter builds on the branching scheme introduced by Laporte et al. (2004) and strengthens it with a new bounding function and two dominance rules. Within C-B&B, these exact algorithms are complemented by a preprocessing phase that incorporates a new branch-and-bound-based heuristic capable of rapidly generating a high-quality initial incumbent solution. Extensive computational experiments show that C-B&B represents a strong breakthrough over previously published approaches, proving optimality for more instances with significantly less computational effort and closing several benchmark instances that have remained open for decades.

For positive integers $n\ge r$, let $\lambda(r,n)$ denote the maximal relative projection constant of $r$-dimensional subspaces of $\ell_\infty^n$ and $\lambda(r)$ denote the maximal absolute projection constant, respectively. It is known that for any fixed $r$, $\lambda(r,n)$ is a non-decreasing sequence with limit $\lambda(r)$ as $n\to \infty$. A natural question is whether $\lambda(r,n)$ stabilizes at $\lambda(r)$ for some $n>r$. We prove that for any fixed $r$, \[\lambda(r,n)=\lambda(r) \qquad \text{for every}\qquad n\ge 2^{r}\binom{r+1}{2}.\] This answers a question of Basso. The technique used is of independent interest.

Using a bijection between the lattice points in a lecture hall polytope and Lakshimibai-Seshadri (L-S) paths, we prove the Koszul property of lecture hall polytopes in complete generality, and give new proofs for their Integral Decomposition Property and for a criterion on Gorenstein property.

We resolve two open problems regarding uniquely colorable Cayley graphs posed by Klotz and Sander (2017). First, we construct an infinite family of uniquely 3-colorable integral circulant graphs with a clique number of 2. This provides a negative answer to Problem 3.6, which asks whether every uniquely colorable circulant graph satisfies $\chi(G) = \omega(G)$. Because verifying unique colorability inherently relies on the exact independence number, we demonstrate that traditional spectral bounds fail to tightly capture this parameter, necessitating a rigorous combinatorial proof based on exact structural isomorphisms. Second, we establish a general algebraic construction proving the existence of uniquely colorable Cayley graphs over nonabelian groups whose color classes are left cosets of strictly distinct subgroups. By utilizing right-coset partitions of non-normal subgroups, this result provides a definitive affirmative answer to Problem 2.4.

(This is a reprint of the thesis published in the Transactions of the Conference Devoted to the 90th Anniversary Of Alexei A. Lyapunov, Novosibirsk, October 8-12, 2001, pages 323-327). The number of ways for partial $n$-quasigroups of order $4$ to be extended to $n$-quasigroups is investigated. Upper bounds on the number of $n$-quasigroups of order $4$ are obtained. The asymptotic $3^{n+1}2^{2^n+1}$ of that number is established.

In 1983, Daykin and Frankl conjectured that if $P$ is a convex subset of $Q_n$, then it contains at least $|P|\binom{n}{\lfloor n/2\rfloor}2^{-n}$ pairwise incomparable elements. We verify and communicate an LLM-generated proof of this conjecture.

We introduce the notion of a non-attacking rook placement on a crossword grid. A crossword grid is a collection of white squares (which comprise across and down words) and black squares (which separate the words), and a complete non-attacking rook placement on such a grid is a subset of white squares which intersects every across and every down word exactly once. We prove an upper bound on the number of rook placements that a general grid can admit. We then study sparse grids in which no two black squares share an edge and show that rook placements on certain sparse grids correspond bijectively to alternating sign matrices with prescribed $-1$ entries. Specializing further to permutation grids, we prove that every permutation grid admits at least one rook placement, and characterize the permutations whose grids admit exactly one placement in terms of the Robinson–Schensted correspondence. Throughout, we pose a variety of conjectures and open questions.

Combinatorial set theory provides several tools to study derived limits of certain inverse systems of abelian groups. Most known nonvanishing results for $\lim^n$ with $n>1$ depend on some guessing principles of the form $\mathrm{w}\lozenge(S)$ called weak diamonds. In this paper, we explore some applications of the guessing principle $\clubsuit(S)$ and its weakenings instead.

It was recently shown by Yeliussizov \cite{Yeliussizov} that integer partitions in dimensions $d \geq 7$ asymptotically grow strictly faster than MacMahon numbers. As MacMahon numbers match with integer partitions in dimensions $d = 1,2$, the comparison of asymptotics of integer partitions with MacMahon numbers in intermediate dimensions ($d = 3,4,5,6$) is an open question. In this work, we perform Markov chain Monte Carlo (MCMC) simulations till $N=15000$ by using adaptive weight learning followed by conventional MCMC steps to numerically estimate the asymptotics of integer partitions in these intermediate dimensions. We numerically establish that in these intermediate dimensions, partitions asymptotically grow faster than MacMahon numbers. More specifically, assuming that the limits exist, we show: $\lim_{n\to\infty}n^{-3/4}\log p_3(n) = 1.8196 \pm 0.0019$, $\lim_{n\to\infty}n^{-4/5}\log p_4(n) = 1.7215 \pm 0.0045$, $\lim_{n\to\infty}n^{-5/6}\log p_5(n) = 1.6521 \pm 0.0059$, and $\lim_{n\to\infty}\log n^{-6/7}p_6(n) = 1.652 \pm 0.021$ for partitions in dimensions $d=3,4,5,$ and $6$ respectively. These numbers are all larger than MacMahon leading order asymptotic coefficients of $1.7898, 1.6614, 1.5737,$ and $1.509$ respectively. Additionally, we also find estimates for some of the sub-leading asymptotic terms in $\log p_d(n)$ in each of the dimensions.

We construct finite geproci sets in every projective dimension and in every positive characteristic by introducing $\mathbb{F}_N$-Artin-Schreier configurations. In $\mathbb{P}^3$, we characterize exactly when such configurations are geproci: an $\mathbb{F}_N$-Artin-Schreier configuration on $q$ lines spanning $\mathbb{P}^3$ is $(q,N)$-geproci if and only if $q\leq N$. We then develop a lifting construction which produces geproci sets in $\mathbb{P}^n$ for every $n\geq 3$.

For a finite graph $H$, a connectivity graph-code is a family $\mathcal C\subseteq 2^{E(H)}$ such that $A\triangle B$ is a connected spanning subgraph of $H$ whenever $A$ and $B$ are distinct members of $\mathcal C$. Let $m(H)$ denote the maximum size of such a family, and let $f(d)$ be the largest integer $q$ for which $m(H)=q$ for infinitely many pairwise nonisomorphic $d$-regular graphs $H$. Restricting codewords to the edges incident with a vertex gives $f(d)\leq 2^d$. Alon proved equality for all sufficiently large $d$ and asked whether it holds for every $d\geq 4$. We answer this question affirmatively. More precisely, for every $d\geq 4$ we construct infinitely many finite simple $d$-regular bipartite graphs carrying a linear connectivity graph-code of dimension $d$. The construction begins with a vector-labelled copy of $K_{d,d}$. For $d\geq 7$, the required labelling follows from a probabilistic count over an irreducible conjugacy class in $\mathrm{GL}_d(2)$; explicit matrices, verified by a short exact exhaustive program, cover $d=4,5,6$. Cyclic voltage lifts then produce the required infinite families.

We develop a localized persistent theory of commutative algebra for Stanley-Reisner rings, based on local cohomology supported at a coordinate prime rather than at the maximal ideal. The construction is modeled on the persistent Stanley-Reisner theory of Suwayyid and Wei (arXiv:2503.23482) and its functorial development for graphs and hypergraphs (arXiv:2512.17619), in which invariants of the face ring such as graded Betti numbers and f- and h-vectors are persisted across a filtration. That framework is built from the minimal free resolution and is thus Tor-theoretic; we work instead on the injective side, and the resulting modules record information localized at a single vertex, complementing the global picture given by maximal-support local cohomology. For a vertex prime $p_i = (x_j : j \neq i)$ we prove an exact $\mathbb{Z}^n$-graded decomposition of $H^q_{p_i}(k[\Delta])$ into the maximal-support local cohomology of the deletion and of the link of the vertex $i$, the first in $x_i$-degree zero and the second repeated in every positive $x_i$-degree; at the level of graded dimensions this recovers the vertex-prime case of Rahimi's bigraded formula. With Hochster's formula this yields a closed combinatorial description of every multigraded piece. Building on this structure we introduce per-vertex persistent local cohomology numbers, prove a persistent links-Hochster formula, obtain interval decompositions of the resulting reversed-arrow persistence modules and a bottleneck stability theorem, retain multiplication by the uninverted variable as a morphism of persistence modules that the two barcodes alone do not determine, and extend the theory to an arbitrary coordinate prime, where the multiplication maps of the uninverted variables assemble into a commuting Boolean diagram of persistence modules.

Temporal graphs model dynamic networks by assigning positive integer time labels to the edges, while information propagates along temporal paths, whose edge labels are traversed in nondecreasing order. A temporal $\alpha$-spanner of a temporal graph with $n$ vertices is a temporal subgraph that approximates the minimum-hop temporal distance between every pair of vertices within a factor of $\alpha$. While general temporal graphs may not admit sparse temporal $\alpha$-spanners for any value of $\alpha$, temporal cliques are known to admit temporal $(2k-1)$-spanners of size $\widetilde{\mathcal{O}}(kn^{1+1/k})$ for every positive integer $k$. We present a simple recursive algorithm that computes, for every temporal clique on $n$ vertices, a temporal $3$-spanner of size $n^{1+2/\sqrt{\ln n}}=n^{1+o(1)}$, thereby improving the previous best upper bound of $\widetilde{\mathcal{O}}(n^{3/2})$. We also show that a modified version of our algorithm computes temporal $3$-spanners of size $\mathcal{O}(nL)$ when the lifetime is bounded by $L$, i.e., all time labels are in $\{1,\ldots,L\}$, thus improving the previous bound of $\mathcal{O}(2^Ln\log n)$. Both results are particularly striking in light of the known lower bound of $\Omega(n^2)$ on the size of temporal $2$-spanners, which already holds for temporal cliques of lifetime $L\geq 3$. Both algorithms rely on a new simple recursive decomposition that certifies temporal connectivity for a large collection of source-target pairs using only $\mathcal{O}(n)$ carefully selected edges and recursively processes only the remaining pairs. Besides yielding substantially improved upper bounds, this approach is significantly simpler than previous constructions.

We construct realizable-volume models over every field for the factorial normalizations of homogeneous Lascoux, Lascoux-atom, and positive Grothendieck packets, including their minimal homogenizations and layers. In particular, the construction realizes the factorial normalizations of all Schubert and key polynomials and of the minimal sign-corrected homogeneous Grothendieck polynomials. The normalized polynomials are Lorentzian, and the ordinary supports are the lattice points of integral generalized polymatroids. On a Bott–Samelson tower, row and co-row filtrations assemble the local factors into globally generated bundles; a creation-state graph absorbs the remaining kernel factors by Chern flow. We also construct intrinsic algebras of joint Chern moments. Positive inverse-Chern presentations give these algebras Hard Lefschetz and Hodge–Riemann relations, and supply source-level Hodge completions of the packets. For globally generated tropical toric bundles in the sense of Kaveh–Manon, finite generating witnesses and matroid duality provide the presentations required by Larson–Partida's theorem, without representability. These constructions yield joint Chern-number inequalities, nonvanishing polymatroids, and equality criteria.

A $B$-coloring of a graph is a proper edge-coloring in which every $4$-cycle is rainbow, and $q_B(G)$ denotes the minimum number of colors in such a coloring. Let $\Delta_2(G)$ denote the maximum number of common neighbors of two distinct vertices of $G$. We prove that, for integers $1\le d\le\Delta$, every finite simple $d$-degenerate graph $G$ with $\Delta(G)\le\Delta$ satisfies $$q_B(G)\le \Delta+(d-1)\Delta_2(G)\le d\Delta.$$ Consequently, $d\Delta$ is the exact maximum, with equality precisely for graphs containing $K_{d,\Delta}$. More generally, if $q_B(G)\ge d\Delta-s$, where $0\le s<\Delta$, then $G$ contains $K_{d,\Delta-s}$; if also $s<d$, then $G$ has at least $d-s$ vertices of degree $\Delta$ with the same open neighborhood. For $\Delta\ge3$, we further show that every $K_{3,\Delta}$-free 3-degenerate graph satisfies $q_B(G)\le3\Delta-2$; the example $K_{3,\Delta-1}$ shows that this bound is best possible up to one. For loopless multigraphs, we establish a sharp gap in the possible values of $q_B(G)$. For every integer $\Delta\ge3$, every finite loopless multigraph $G$ with $\Delta(G)\le\Delta$ satisfies $$q_B(G)\le\Delta(\Delta-1)$$ unless $G$ has a component isomorphic to $K_{\Delta,\Delta}$, in which case $q_B(G)=\Delta^2$. The bound $\Delta(\Delta-1)$ is attained by both $K_{\Delta,\Delta-1}$ and $K_{\Delta,\Delta}-e$. Consequently, among finite loopless multigraphs with maximum degree at most $\Delta$, no value of $q_B(G)$ lies strictly between $\Delta^2-\Delta$ and $\Delta^2$.

We give an example showing that the dual of an algebraic matroid need not be algebraic. Our example is a matroid of rank 6 on 10 elements which is algebraic in characteristic 2. It is obtained by gluing an algebraic realization of the non-Fano matroid to a realization of the Fano matroid. Its dual is shown not to be algebraic using the Ingleton-Main lemma.

We prove that the proportion of $0/1$-equivalence classes of $d$-dimensional $(0,1)$-polytopes that are normal tends to zero at least at a double exponential rate as $d\to\infty$. As a consequence, the same holds for any of the following classes given by the type of triangulation possible: (a) quadratic, (b) flag unimodular, (c) regular unimodular, or (d) unimodular, among others. We classify the $0/1$-equivalence classes of $d$-dimensional $(0,1)$-polytopes for $d\leq5$ according to whether they admit a unimodular, flag unimodular, or quadratic triangulation. In dimension five, exactly $175$ out of $1{,}226{,}525$ classes have a flag unimodular triangulation, but no quadratic triangulation. Among them, there are polytopes whose toric rings are not Koszul; thus, we find the first polytopes that have a flag unimodular triangulation, but whose toric ring is not Koszul. In contrast with the matroid case, we exhibit a delta-matroid polytope that is not normal.

For a tournament $T$ and a vertex ordering $\prec$, let $T^{\prec}$ be the graph of backward arcs in $\prec$. The diclique number of a tournament is $\domega(T)=\min_{\prec}\omega(T^{\prec})$, and the dichromatic number is $\dchi(T)=\min_{\prec}\chi(T^{\prec})$. We prove a mixed parameter transfer theorem: for all $k$ and $r$, if $\tww(T)\le k$ and $\omega(T^{\prec})\le r$, then the ordered twin-width of $(T^{\prec},\prec)$ is bounded by a function of $k$ and $r$. The proof combines the regular-semigrid theorem for ordered graphs with permutation-encoding obstructions to bounded twin-width in tournaments. Together with polynomial $\chi$-boundedness of graphs of bounded twin-width, this implies that tournaments of bounded twin-width are $\dchi$-bounded by $\domega$, resolving a conjecture of Aboulker, Aubian, Charbit, and Lopes.

An Euler circuit of a graph is a closed path that visits every edge of the graph exactly once. Euler circuit and circuit decomposition problems can also be formulated for higher dimensional simplicial complexes. An Euler k-circuit in K is a cyclic sequence of vertices v_1...v_n such that every k+1 adjacent terms { v_i,v_{i+1},...,v_{i+k} } (indexed modulo n) form a k-simplex, and every k-simplex of K appears exactly once in the sequence v_1v_2...v_n(v_1v_2...v_k). We investigate the 2-circuit decomposition problem for triangulated closed compact surfaces. For an orientable triangulated surface we use interior angles of paths to define an obstruction that lives in the first cohomology of the surface. It vanishes if and only if the surface has a 2-circuit decomposition. We also show that a non-orientable triangulated surface has a 2-circuit decomposition if and only if its orientable 2-fold cover does.

The pairwise independent correlation gap is the ratio of the maximum expected value of a set function under arbitrary dependence to that under pairwise independence, measuring the loss from this independence restriction. Under mutual independence, this gap is universally bounded by $e/(e-1)$ for monotone submodular functions. With pairwise independence, a tighter $4/3$ upper bound was established for several special cases, including $n=3$, and conjectured to hold universally. A recent AI-assisted counterexample disproved this conjecture for $n=5$, leaving the validity of the $n=4$ bound and the tight worst case bound open. We resolve both questions. First, for $n=4$, we establish that the $4/3$ bound holds universally and is tight using an AI-assisted proof combining theoretical analysis and computational verification. The proof combines a structural characterization of optimal numerator vertices, permutation symmetry, cone certificate systems, Bernstein polynomial representations, recursive simplex subdivision, and verification of $2,745$ Bernstein coefficient systems. Second, we show that the worst case pairwise independent correlation gap attains $e/(e-1)$ asymptotically by constructing an instance with identical marginal probabilities and a monotone submodular union coverage function on a ground set partitioned into $m$ blocks. The number of blocks grows sublinearly with the ground set size. The result follows by constructing a feasible solution to a scaled asymptotic reduced dual of the pairwise independent linear program and immediately extends to $t$-wise independent random elements ($t\ge2$), since $t$-wise independence implies pairwise independence. Thus, pairwise independence, despite being the least restrictive form of independence in the $t$-wise independence hierarchy, can be as restrictive as mutual independence in the worst case.

The equivalence classes of boundary conditions of a gauge theory on a two-dimensional orbifold are the fibres of a marginal map, indexed by an affine semigroup: one generator per alphabet label, graded by weight, embedded by its local data at the fixed points. This note identifies that semigroup. Without weights the configuration has a name and a literature, whose results about our cases are attributed here: over $\mathbb{Z}_2$ it is the cut configuration of an explicit graph in the sense of Sturmfels-Sullivant — the four-cycle for $T^2/\mathbb{Z}_2$, the wheel $W_4$ for $S^1/\mathbb{Z}_2\times S^1/\mathbb{Z}_2$ — verified as an equality of configurations; over $\mathbb{Z}_m$ with equal cone orders, the group-based phylogenetic model on a claw tree; with unequal orders, a mixed-order variant we do not find in the literature; for higher products, the binary hierarchical model of a cross-polytope boundary complex. The product orbifold's ring is a row of a 2008 table — codimension, degree, minimal generators, normality — every invariant of which our machinery reproduced without knowing of it. What none of the three covers is the alphabet with weights, which arise from induction to higher-dimensional irreducibles of a non-abelian space group and from conjugate-pair recombination over real or quaternionic ground. That sector is adjacent to, but not identified with, the non-abelian direction Sturmfels and Sullivant raised in 2005, and is where our contributions sit: gluing trees for the weighted alphabets and the orthogonal and symplectic columns, and the group-based model on the tripod, a complete intersection exactly when the finite abelian group has order at most three. The first group beyond $\mathbb{Z}_3$ separates local from global: the $\mathbb{Z}_4$ tripod is a complete intersection on the Zariski-open set the phylogenetics literature works in, and not globally.

We prove the Lonely Runner Conjecture for fourteen and fifteen runners. Our proof combines a stronger bound on the speed product in a primitive counterexample with exhaustive computations modulo primes. To obtain the bound, we work with a projected lattice basis and use cases of the conjecture with fewer runners to bound partial sums of its squared Gram-Schmidt lengths. For fifteen runners, the product bound derived from the work of Malikiosis, Santos, and Schymura gives a logarithmic threshold of about $810$; ours reduces this to about $415$, making the computation feasible. For fourteen runners, the new bound reduces the required number of primes from $111$ to $61$. The computations start with a complete two-branch covering search, followed by binary lifting. Since $14$ and $15$ are composite, the polynomial argument used in earlier work does not apply directly. We finish the fourteen-runner case by a direct search. For fifteen runners, we use the factorisation $15=3\cdot5$ and a shifting argument when all but a few speeds share a common divisor. The code and certificates are publicly archived.

A graph $G$ is minimal Ramsey for a graph $H$ if every $2$-colouring of the edges of $G$ contains a monochromatic copy of $H$, but for every proper subgraph of $G$, there is a $2$-colouring that does not contain such a monochromatic copy. Characterizing minimal Ramsey graphs is a widely studied problem. Recent research in this field includes the characterization of the size of the set $\mathcal{M}_2(H)$ of all minimal Ramsey graphs for $H$, or finding the smallest minimum degree among all graphs in $\mathcal{M}_2(H)$. In this paper, we introduce a game theoretic analogue of the above concept by considering the Maker-Breaker $H$-game on a graph $G$. In this game, two players, Maker and Breaker, alternately claim unclaimed edges of $G$, and Maker wins if in the end of the game the graph spanned by Maker's edges contains a copy of $H$. Otherwise, Breaker wins the game. We call a graph $G$ winnable for $H$ if Maker has a winning strategy for the Maker-Breaker $H$-game on $G$, and we call it minimal winnable if additionally Breaker wins the $H$-game on every proper subgraph of $G$. Along the lines of minimal-Ramsey theory, we characterize all graphs $H$ for which there exist infinitely many minimal winnable graphs, and we prove tight bounds for the smallest minimum degree among all these minimal winnable graphs. Amongst others, we obtain precise results for trees, cycles, cliques, and complete bipartite graphs. In general, we find many similarities between the Ramsey setting and the Maker-Breaker setting, but we also show substantial differences.

Although almost all graphs are asymmetric – having no nontrivial global automorphisms – they may still possess local symmetries in the form of isomorphisms between induced subgraphs, i.e., partial automorphisms. We study such local symmetries via asymmetric depth, defined in terms of the maximum rank of a nontrivial partial automorphism. We prove a tight upper bound on asymmetric depth in the class of planar graphs and identify the extremal graphs: duals of IPR fullerenes attain the maximum already on $47$ vertices. Our main structural result concerns the IPR fullerenes that are neither maximally asymmetric nor symmetric. In such a cage no purely local action realises a low asymmetric depth, and we show that the map which does realise it cannot be confined to a small part of the cage either: neither to a single face, nor behind an interface of at most $5-k$ edges, $k \le 3$ being the deficiency. A cage of asymmetric depth $2$ or $3$ is therefore not asymmetric in one place; it carries a broken symmetry invisible to its automorphism group. Such cages are rare – under $2\%$ of the asymmetric IPR fullerenes at $n = 118$. In all $727$ of them the largest partial automorphism is a near-mirror reflection, which we state as an explicit conjecture. We also extend the asymmetric depth bound to graphs of higher genus.

Let f be a labeling of the edges of a finite graph G by positive integers, and let the weight of a path be the sum of the labels of its edges. The labeling is a geodesic Leech labeling if the weights of the geodesics are exactly 1, 2, ..., t_gp(G), each occurring once, where t_gp(G) is the geodesic path number of G. Let W_n be the wheel on n vertices, a hub joined to an (n-1)-cycle. Our main result is an upper bound: if n >= 5 and W_n is geodesic Leech, then n <= 40. The proof quantifies, via a finite Fourier kernel, the Sidon-type structure of the spoke labels, in which only the cyclically adjacent pairs are allowed as defects, and closes the last three cases with a six-variable Parseval argument. In the other direction, explicit labelings of W_7, ..., W_13, found by a computer search, answer in the negative a problem of Lakshmanan S. and Manattu, who had found labelings of W_5 and W_6 and expected every W_n with n >= 7 to be a non-geodesic Leech graph. Writing E for the set of n >= 5 for which W_n is geodesic Leech, we obtain {5, 6, ..., 13} is contained in E, which is contained in {5, 6, ..., 40}.