Papers

For every $q\ge2$, we prove that every oriented graph $G$ on $n\ge45q-8$ vertices whose minimum semidegree satisfies \[ \delta^0(G)\ge \left\lceil\frac n3\right\rceil \] contains a directed cycle of length $3q$ through every vertex. The semidegree bound is sharp. This closes the one-unit gap left by the prescribed-vertex theorem of Kelly, Kühn and Osthus when $3\mid n$. We also prove that if an oriented graph $H$ has order $N$, minimum semidegree $d\ge3$, and $7d\ge2N+3$, then every ordered pair of distinct vertices is joined by a path of length three, four, or five. The constant $+3$ is best possible. As a consequence, the order hypothesis $n\ge10^{10}\ell$ in the general prescribed-vertex theorem of Kelly, Kühn and Osthus can be replaced by $n\ge15\ell-60$ for $\ell\ge7$.

A graph $G$ is $k$-vertex-critical if $\chi(G)=k$, but $\chi(H)<k$ for every induced subgraph $H$ of $G$. A graph $G$ is $(H_1,H_2,\dots,H_m)$-free if does not contain $H_i$ as an induced subgraph for any $i\in\{1,2,\dots,m\}$.We provide the following dichotomy that for bipartite graphs $H$ and any fixed integer $k\ge 5$ , there are only finitely many $k$-vertex-critical $(P_5,H)$-free graphs if and only if $H$ is $2P_2$-free. This leads us to pose the problem about determining for which graphs $H$ with $\chi(H)\ge 3$ there are infinitely many $k$-vertex-critical $(P_5,H)$-free graphs for all $k\ge 5$. Toward this problem, we show that there only finitely many $k$-vertex-critical $(P_5, K_{s,t}+e)$-free graphs for all $k,s,t\ge 1$, where $K_{s,t}+e$ is a complete bipartite graph plus a single edge. On the other hand, we show that there are infinitely many $k$-vertex-critical $(P_5,\operatorname{net},\operatorname{co-net},\overline{C_5},\overline{C_6},\dots\overline{C_{k-1}})$-free graphs for all $k\ge 5$. We also show that there are only finitely many $k$-vertex-critical $(P_4+\ell P_1,\overline{L(K_{2,n})})$-free graphs for all $\ell,n\ge 0$, providing the largest known subfamily of $(P_4+\ell P_1)$-free graphs to satisfy this property. Our results, together with known results, imply the existence of new polynomial-time certifying algorithms to determine the $k$-colourability of many subfamilies of $P_5$-free and $(P_4+\ell P_1)$-free graphs for fixed $k\ge 5$. Our proof techniques apply a powerful theorem of Chudnovsky, Kim, Oum, and Seymour (2016) on prime graphs that we expect to be of interest and have further applications to bounding the number of $k$-vertex-critical graphs in other hereditary families of graphs.

For a graph $ G = (V, E) $ with a vertex set $ V $ and an edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a broadcast on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a dominating broadcast on $ G $. The cost of the dominating broadcast $f$ is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the broadcast domination number of $G$, denoted by $ \gamma_{b}(G) $. A multipacking is a set $ M \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ M $, that is, there are at most $ r $ vertices in $ M $ at a distance at most $ r $ from $ v $ in $ G $. The multipacking number of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. It is known that $mp(G)\leq\gamma_b(G)$. In 2014, Hartnell and Mynhardt proved that $\gamma_b(G)\leq 3mp(G)-2$ whenever $mp(G)\geq2$. In 2019, Beaudou, Brewster, and Foucaud improved this bound to $\gamma_b(G)\leq 2 mp(G)+3$ and conjectured that $\gamma_b(G)\leq 2 mp(G)$. We solve their conjecture by proving that $\gamma_b(G)\leq 2 mp(G)$ for every graph $G$. Our proof is constructive and yields a polynomial-time $2$-approximation algorithm for Maximum Multipacking problem which improves the earlier approximation factor $2+o(1)$.

There is a fascinating array of interrelated questions studying which structures can be guaranteed in digraphs of large minimum out-degree. These often have intriguingly simple statements, yet seem surprisingly difficult to approach. A well-known example is Lichiardopol's conjecture (2014), stating that there exists a function $g:\mathbb{N}\rightarrow \mathbb{N}$ such that every digraph with minimum out-degree at least $g(k)$ contains $k$ vertex-disjoint directed cycles of distinct lengths. In this paper, building on earlier work of the second author, we confirm this conjecture in full generality. We also generalise this result to a weighted setting. Our proof uses and combines many ingredients from structural digraph theory such as butterfly minors, directed tangles, a directed analogue of the Tangle-Wall Theorem due to Robertson and Seymour as well as a local variant of the Directed Flat Wall Theorem due to Giannopoulou, Kawarabayashi, Kreutzer and Kwon. These techniques, which are somewhat atypical in the study of minimum degree conditions, may be of independent interest and may find further applications.

We study synchronization in the Kuramoto model on finite graphs. We prove that there is an absolute constant $\eta>0$ such that every finite simple graph $G$ on $n$ vertices with minimum degree at least $(3/4-\eta)n$ has no local minima of the Kuramoto energy other than the fully synchronized states. This strictly improves the previous $3/4$ upper bound and refutes a conjecture of Bandeira, Kireeva, Maillard, and Rödder.

A set of positive integers $R$ is called a set of nice recurrence if for any measure preserving system $(X,\mu,T)$, for all measurable $A\subseteq X$, and each $\varepsilon>0$, there exists $n\in R$ such that $\mu(A\cap T^{-n}A)\geqslant \mu(A)^2 - \varepsilon$. Answering a long-standing question of Bergelson, we show that sets of nice recurrence have the following Ramsey property: any finite colouring of a set of nice recurrence admits a monochromatic set of nice recurrence.

A partial permutation of $[n] := \{1,\dots,n\}$ is a bijection $g: I \to J$ between two subsets $I,J \subseteq [n]$. Given a partial permutation $g$ of $[n]$, let $a_g \in \mathbb{C}[\mathfrak{S}_n]$ be the group algebra sum of those permutations $w \in \mathfrak{S}_n$ which extend $g$. Informally, a partial permutation $g$ is obtained by forgetting some data in a genuine permutation. The forgotten symmetric functions are the least-studied of the six `standard' bases for the ring of symmetric functions. We show that forgotten symmetric functions arise naturally in class function evaluations on partial permutations.

We discuss three questions from a recent paper of Bhandari, Cunningham, Morrell, Oh and Smith. We obtain an exact local formula for the facet gap between the order and the chain polytope of a finite poset. This gives a classification of the case $\gap(P)=2$ in terms of star elements. For marked chain–order polytopes, the same local weights determine the facet differences between all admissible decompositions.

In this paper the tree structure of numerical semigroups is studied. An internal numerical semigroup is a semigroup located in an internal node of the tree. Analogous a leaf numerical semigroup is placed in a leaf node. Internal semigroups with fixed multiplicity, Frobenius number or genus are studied by providing algorithms to construct all of them. Several conjectures are established, for example, in each case (fixed multiplicity, fixed Frobenius number and fixed genus respectively), the results suggest that there are always more internal than leaf numerical semigroups. Finally, numerical semigroups with fixed multiplicity and Frobenius number simultaneously are investigated. In this case with two invariants fixed, moreover closed formulas to count the number of internal and leaf semigroups are provided for some values of multiplicity and Frobenius number.

Fractional revival (FR), a generalization of perfect state transfer (PST), is a significant phenomenon in quantum state transfer that allows quantum information to be transmitted between two qubits with a certain probability. The existence of FR has been extensively studied on many classes of graphs. However, oriented graphs have not yet been investigated. In this paper, we investigate the existence of proper FR on oriented graphs. We first establish necessary and sufficient conditions for oriented graphs to admit proper FR between strongly cospectral vertices. Furthermore, we prove that oriented Cayley graphs over abelian groups do not admit proper FR, and we subsequently characterize the conditions under which oriented semi-Cayley graphs over abelian groups admit proper FR.

Plane hypermaps are plane maps endowed with a proper coloration of their inner faces in black or white. We consider the problem of enumerating plane hypermaps with prescribed face degrees and a $k$-alternating boundary condition: by this we mean the colors of inner faces incident to the outer face alternates at most $2k$ times when turning around the hypermap. The present paper deals with the cases $k=1,2$, the general case being left to the forthcoming part II. Our approach relies on the so-called slice decomposition and uses crucially the notion of accessibility, which exploits the canonical orientation of hypermaps and the marking variable $t$ associated with vertices, to enumerate pointed hypermaps by decomposing them according to the set of all vertices that can access to the marked vertex. This process enables us to express the generating functions of hypermaps with mixed boundaries in terms of the generating functions of hypermap slices and to recover, in a purely combinatorial way, some formulas previously obtained through algebraic methods.

For fixed graphs $H$ and $F$, let $\ex(n,H,F)$ denote the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. In this note, we prove the generalized rational exponents conjecture, posed by Gerbner and Palmer, showing that for every rational number $\alpha\ge1$, there exist fixed graphs $H_\alpha$ and $F_\alpha$ such that \[ \ex(n,H_\alpha,F_\alpha)=\Theta(n^\alpha). \] Furthermore, the counting graph $H_\alpha$ can always be chosen connected with diameter at most $3$. Our argument hinges on a localization–compression–shift framework, which transforms the Bukh–Conlon finite family construction for edges into a generalized Turán problem setting with a single forbidden graph.

Phylogenetic networks are graphs that represent the evolutionary history of species. Recently, the class of orchard phylogenetic networks, which can be reduced by so-called cherry-picking sequences, has gained attention for its computational and biological aspects. In this paper, we study a fundamental question on orchards and their cherry-picking sequences by considering the CoveringNumber problem: given an orchard network $N$, how many cherry-picking sequences are needed to reduce all subnetworks of $N$? We initiate this study by considering the problem for trees. We then show that the covering number can be computed for binary trees recursively using a similar but more fine-grained notion of survival covering number. We also give a recursive formula for the survival covering number of non-binary trees. However, computing the covering number for non-binary trees appears to be considerably more challenging. For this case, we show that the covering number of star trees (whose root is adjacent to all leaves) is equivalent to the so-called SubsetConnectivity problem, which we introduce in this paper. Finally, we show that if there is no restriction on the sequence length, a single sequence of minimum length $\binom{n}{2}$ suffices to reduce all subtrees of a tree on $n$ leaves.

Let $G=N\rtimes H$ be a finite Frobenius group with $|N|=q$ and $|H|=q-1$. We classify all Ramanujan Cayley graphs of $G$ whose connection sets are normal, in the sense of being unions of conjugacy classes. The group-theoretic input is a simple blow-up phenomenon: every such Cayley graph is either $Y[\overline{K_q}]$ or $Y[K_q]$ for a connected regular Cayley graph $Y$ on the complement $H$. We first prove a graph-theoretic result classifying all Ramanujan graphs of these two forms when $Y$ is an arbitrary connected regular graph on $q-1$ vertices. The proof combines the classical characterization of regular graphs with least eigenvalue greater than $-2$ with a second-moment identity in the bipartite case. Translating the resulting five graph types back to $G$ yields a complete classification for all ratio-one Frobenius groups, and in particular for $\operatorname{AGL}(1,q)$ over every finite field.

Let $\mathsf{P}$ be a finite graded poset and $\Delta_a^{\mathsf{P}}$ the height-$a$ thickening of its diagonal, with projections $q_1,q_2$ to $\mathsf{P}$. We study the window convolution $C_a=\operatorname{Lan}_{q_1}\circ q_2^\ast$ on $\mathrm{Shv}(\mathsf{P};k)$, a discrete analogue of convolution against a thickening kernel. An interleaving distance needs the homotopy window convolution $\mathbb{C}_a$ to compose as a flow, $\mathbb{C}_a\mathbb{C}_b\simeq\mathbb{C}_{a+b}$; where the meet assignment $\Phi$ is total it is a functor and carries a comparison map. Finality is sufficient, and necessary at every minimal apex and wherever the finality defect of $\Phi$ is essential; where $\Phi$ is total at a minimal apex with unit windows, it is the failure of a length-two interval above the apex to have a single interior element. The flow fails at every branching length-two interval with minimal bottom element, and with it on the face poset of every finite regular cell complex of dimension $\ge2$. It survives on tame posets, where $\mathrm{id}\Rightarrow\mathbb{C}_a$ gives a canonical extended interleaving pseudometric on $\operatorname{D^{b}}(\mathrm{Shv}(\mathsf{P};k))$; in the saturation cases computed here it takes no finite value above the length of $\mathsf{P}$, and is finite if and only if the derived colimits agree.

Let $F_1=F_2=1$ and $F_{t+2}=F_{t+1}+F_t$ for $t\geq1$. For every $n\geq2$, there are unique integers $a,b,t$ such that $n=aF_t+bF_{t-1}$ with $t\geq2$ and $1\leq a\leq b\leq F_t$. The Fibonacci walk with initial pair $(b,a)$ reaches $n$ as late as possible, and the term following $n$ in this walk is $\lfloor\phi n\rfloor$ when $t$ is even and $\lceil\phi n\rceil$ when $t$ is odd, where $\phi=(1+\sqrt5)/2$. Let $D=\{d_1<d_2<\cdots\}$ and $U=\{u_1<u_2<\cdots\}$ be the sets corresponding to even and odd $t$, respectively. For $\ell,m\geq1$, define $D_\ell=\{d_{k+\ell}-d_k:k\geq1\}$, $U_\ell=\{u_{k+\ell}-u_k:k\geq1\}$, $D_\ell(m)=\{d_k:d_{k+\ell}-d_k=m\}$ and $U_\ell(m)=\{u_k:u_{k+\ell}-u_k=m\}$. Chung, Graham and Spiro conjectured that $D_\ell=U_\ell$ for all $\ell$, and asked for the densities of $D_\ell(m)$ and $U_\ell(m)$, especially when $\ell=1$. In this paper, we determine the third and fourth order gap spectra, and show that the conjecture holds for $\ell=3$ but fails for $\ell=4$. We also answer their density question by characterizing when $D_\ell(m)$ and $U_\ell(m)$ have natural densities and proving that their logarithmic densities always exist and are equal. For $\ell=1$, we give the exact logarithmic densities.

A combinatorial game is a two-player game without hidden information or chance elements. The main object of combinatorial game theory is to determine the outcome (i.e., which player has a winning strategy) of a given position in combinatorial games. Nim is a well-known and fundamental ruleset in combinatorial game theory. This paper proposes a novel partizan variant of Nim called Partizan-Serial-Nim, defined as follows: there are $n$ piles of stones indexed by $1, 2, \ldots, n$; the two players have permutations $\mathbf{\sigma}^L$ and $\mathbf{\sigma}^R$ of $(1, 2, \ldots, n)$, respectively; a move is to remove any positive number of stones from the non-empty pile with the minimum value in the player's permutation; the player who cannot make a move loses. This ruleset is a generalization of Serial-Nim and Partizan-End-Nim. We give an algorithm to compute the outcome of a given position in Partizan-Serial-Nim in $O(n^2)$ time, provided that each arithmetic and comparison operation is performed in $O(1)$ time. Also, for the case where all non-empty piles have the same number $m$ of stones, we prove that the outcome does not depend on $m$ for $m \geq 2$ and present an algorithm to compute the outcome in $O(n)$ time. Further, we prove that the atomic weight of every position in Partizan-Serial-Nim is an integer.

Let K_q(n,R) denote the minimum cardinality of a q-ary code of length n with covering radius R. We improve the known bounds on K_q(n,R) in 83 cases (82 distinct cells). On the upper-bound side we give 25 improved bounds for 5<=q<=15 – twenty-four found by search and one propagated by monotonicity – using two complementary methods: an engineered focused local search seeded with structural constructions, and a large-neighbourhood search driven by exact full-space coverage transforms that evaluates every candidate codeword position simultaneously. These are, to our knowledge, the first improvements to any upper bound on K_q(n,R) with q >= 5 since the 2011 revision of Keri's tables; several bounds decrease by more than 20%, e.g. K_6(8,4)<=166 (previously 216) and K_8(10,5)<=1883 (previously 2461). On the lower-bound side we give 58 improved bounds for 6<=q<=21, obtained from the semidefinite programming hierarchy of Gijswijt and Polak, whose published results cover q<=5, by combining an exact-arithmetic reimplementation of the reduced program with a multiprecision solution pipeline. Every new lower bound is certified by a rational dual solution validated by a standalone exact-arithmetic checker; no floating-point computation is part of the trusted base. The same pipeline also gives strong numerical evidence of limits: on a dozen further cells the certified value of the relaxation, which the solver reports as optimal to within its working precision, lies below the best known bound, indicating that no improvement is available there at this level of the hierarchy. One cell is improved from both sides: 441<=K_6(10,4)<=2751, previously 417–2952. All codes and certificates are provided in machine-readable form together with standalone verifiers.

Vizing conjectured that the list edge chromatic number of any graph with maximum degree $\Delta$ is at most $\Delta + 1$. This conjecture has been confirmed for several important classes of graphs, in particular, Lang proved that it holds for all graphs of treewidth $3$. In this paper, we introduce the list edge coloring of signed graphs, a framework that generalizes both classical list edge coloring and the signed edge coloring introduced by Behr. We extend Lang's result by proving the signed analogue of Vizing's conjecture for all signed graphs of treewidth $3$, as well as for signed graphs of treewidth $4$ with maximum degree $\Delta \ge 10$.

For $n\geq 4$, let $c(n)$ be the minimum number of distinct circles containing at least three points of an $n$-point set in the Euclidean plane, where the set is neither collinear nor concyclic. Put[F(n)=1+\binom{n-1}{2}-\left\lfloor\frac{n-1}{2}\right\rfloor.]We determine $c(n)$ for every $n\geq 4$: it equals $F(n)$ apart from three exceptional orders. We also solve the variant in which no three points are collinear; that variant has a single exceptional order. The proofs and exact finite verifications were developed through a collaboration between human researchers and artificial-intelligence systems.

Cells for the canonical and $p$-canonical bases organise the representation theory and geometry of Hecke categories. We determine the relevant $p$-canonical basis elements and the resulting $p$-cell structure for the subregular and submaximal cells in all classical types.

Let $G$ be a connected bridgeless graph. In 2011, Kung and Royle showed that all roots of the flow polynomial $F(G,\lambda)$ of $G$ are integers if and only if $G$ is the dual of a chordal plane graph. In this article, we further prove that if $F(G,\lambda)$ has real roots only, then $G$ is the dual of a chordal plane graph and each root of $F(G,\lambda)$ is an integer in the set $\{1,2,3\}$.

For any graph $G$, let $P(G,k)$ and $P_{\ell}(G,k)$ denote the chromatic polynomial and the list-color function of $G$, respectively. It remains an open problem whether, for every graph $G$ and integer $k$, the equality $P(G,k)=P_{\ell}(G,k)>0$ implies that $P(G,k+1)=P_{\ell}(G,k+1)$ also holds. In this paper, we answer this question in the negative. For every integer $k\ge 3$, we construct an infinite family of graphs $G$ such that $P(G,k)=P_{\ell}(G,k)>0$ while $P(G,k+1)>P_{\ell}(G,k+1)$. Moreover, using this infinite family of graphs as attachment gadgets, we further show that any graph $H$ with $P(H,k)=P_{\ell}(H,k)>0$ can be developed into an infinite family of graphs $H'$ with $P(H',k)=P_{\ell}(H',k)>0$ and $P(H',k+1)>P_{\ell}(H',k+1)$.

For a $C_4$-free graph $G$ on $n$ vertices — one with no induced cycle on four vertices — we study the two-sided extremal problem for the triangle density $\tau$: How large and how small can $\tau$ be for given edge density $\varepsilon$ and clique-number density $\kappa = \omega(G)/n$? We give lower and upper bounds for $\tau$ in terms of $\kappa$ and $\varepsilon$. The two bounds sandwich $\tau$, and their compatibility forces a lower bound for $\kappa$ in terms of $\varepsilon$. When the clique complex of $G$ is $2$-Leray over a field $\Bbbk$, the resulting bound on the clique-number density lies between the previous best $C_4$-free bound and the sharp chordal bound. It improves on the former for every $\varepsilon \in (0,1)$. The lower bound is elementary. The upper bound is homological, obtained by passing to the Stanley–Reisner ring of the clique complex. When the complex is $2$-Leray, its Betti table has at most two linear strands. The two first entries in the first strand encode edge and triangle densities, and the strong structural form of a Boij–Söderberg decomposition constrains what these entries can be, yielding the upper bound. For $2$-Leray graphs with no holes in the range $[4,g]$ we give a conjecturally sharp bound. We further ask questions concerning the triangle bound for any $C_4$-free graph.

For every fixed $k\ge2$, we give a randomized one-pass insertion-only algorithm that colors an $n$-vertex $k$-uniform hypergraph of maximum degree $\Delta$ with $O(\Delta^{1/(k-1)})$ colors using $\widetilde O_k(n)$ bits of working memory. As a graph-theoretic result of independent interest, we also prove a tight palette-sparsification theorem for general uniform hypergraphs. Independently sampled lists of $\Theta(\sqrt{\log n})$ colors from a palette of size $O(\Delta^{1/(k-1)})$ preserve colorability with high probability; the list-size dependence is asymptotically optimal. These results extend to bounded-rank hypergraphs. We complement the algorithm with a deterministic lower bound: for every fixed polylogarithmic semi-streaming space bound, there are polylogarithmic values of $\Delta$ for which any deterministic one-pass algorithm requires $\exp(\Delta^{\Omega(1)})$ colors.

For a full-dimensional rational polytope $P\subset\mathbb{R}^d$ and a real dilation parameter $t>0$, the integer point enumerator is defined by $L_{P}(t):= |tP\cap\mathbb{Z}^d|$. We determine exactly which translation vectors $\mathbf y=(y_1,\ldots,y_d)\in\mathbb{R}^d$ have the property that the single translated counting function $t\longmapsto L_{P+\mathbf y}(t)$, with $t\in\mathbb{Q}_{>0}$, uniquely determines $P$ among all full-dimensional rational polytopes in $\mathbb{R}^d$. The necessary and sufficient condition is that $1,y_1,\ldots,y_d$ be linearly independent over $\mathbb{Q}$. In particular, we may use the explicit algebraic vector $\mathbf y^* := (2^{1/(d+1)},2^{2/(d+1)},\ldots,2^{d/(d+1)})$ in every dimension $d$. The sufficiency proof recovers the primitive facet inequalities from isolated discontinuities of the counting function, while necessity follows from an affine-unimodular obstruction.

We present a compact formula for the exact partition function of the $d$-dimensional arithmetic Ising model (AIM). For a $2\times2$ system, we express it analytically using the $q$-Hurwitz-Lerch zeta function and derive explicit forms for the free energy and entropy. Additionally, we find that the entropy increases at high temperatures, supporting the presence of entropic order.

Let $X$ be a projective line bundle over a nonsingular toric surface which is a blowup the projective plane along at most 4 invariant points, or a blowup the product of the projective lines along at most 4 invariant points. Let $L$ be an ample line bundle on $X$. Then $L$ defines a projectively normal embedding to big projective space. We show the ideal of this embedded $X$ is generated by elements of degree two.

Our previous papers [8, 9] are the first and second to discuss minimum numbers of “region” colors, while minimum numbers of arc colors such as Fox colors are well-studied. As the third installment, in this paper, we investigate the minimum number of Dehn $\mathbb{Z}$-colors. In particular, we show that the minimum number of Dehn $\mathbb{Z}$-colors of a nonsplittable $\mathbb{Z}$-colorable link is three.

Weak arcs are point sets in PG$(n-1,q)$ meeting every general hyperplane (those are the hyperplanes not going through one of the points given by the standard basis vectors) in at most $n-1$ points. In this paper, we study weak arcs together with balanced variants which are contained on the sides of the fundamental simplex. We give an upper bound on the size of weak arcs, characterise the largest balanced quasi-arcs in the plane and construct large balanced quasi-arcs in PG$(3, q)$. We then use these configurations to build point sets for the random-access problem in DNA-based storage. The constructions are explicit, work over small fields, and attain recovery expectations matching the best known asymptotic bounds.