Papers

We record five improved lower bounds for Zarankiewicz numbers with s = t = 3: z(13,19;3,3) >= 118, z(14,19;3,3) >= 126, z(16,18;3,3) >= 136, z(14,20;3,3) >= 126, z(16,19;3,3) >= 136. The first three are certified by explicit K_{3,3}-free 0/1 matrices; the last two follow from the second and third by monotone padding. Compared with the lower bounds compiled in Figure 2 of arXiv:2605.01120, namely 114, 121, 130, 125 and 132, the improvements are +4, +5, +6, +1 and +4 respectively. The three matrices were produced by a kicked-greedy local search operated autonomously by a discovery system and were verified exactly, by exhaustive inspection of every 3x3 row/column triple, in several mutually independent implementations; they were also re-verified independently by the authors of arXiv:2605.01120 using their own verifier in July 2026. All three witnesses are printed in full in Appendix A and accompany this note as machine-readable ancillary files together with standalone, dependency-free verifiers.

The permanent of an $n\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was improved by Bezáková, Štefankovič, Vazirani, and Vigoda (2008) to $O(n^7\log^4 n)$ for $0/1$ matrices, for any fixed approximation and success parameters. We present the first asymptotic improvement over this running time bound, obtaining an $O(n^6\log^5 n)$-time algorithm. As in the previous works, our algorithm extends to arbitrary nonnegative matrices. The analysis of Bezáková et al. yields an $O(n^4)$ relaxation time bound for the JSV Markov chain on perfect and near-perfect matchings with ideal hole weights, under which each hole pattern (the unmatched vertices, if any) is equally likely in the stationary distribution. We introduce a restricted Poincaré inequality for the partition into hole patterns and prove an $O(n^3)$ bound on the corresponding restricted relaxation time. Our proof uses a coupled multicommodity flow argument inspired by a recent transport-flow argument of Chen et al.~(2025) for the Jerrum-Sinclair chain on all matchings.

This article studies identifying codes in oriented graphs from a computational complexity perspective. We investigate the $\mathcal{F}$-Id Code problem, where given a simple graph $G$ and a vertex subset $C$, which induces a subgraph in the family $\mathcal{F}$, as inputs and ask whether it is possible to orient $G$ in such a way that $C$ becomes its oriented identifying code. Focusing on the family $\mathcal{F}_d$ of $d$-regular graphs, we establish a complete dichotomy by proving that the problem is polynomial-time solvable for $d\leq1$ and NP-complete for all $d\geq2$.

Standard machine-learning training minimizes a loss function over a dataset, but does not guarantee that the resulting model will satisfy predefined rules or constraints on its outputs. In many real-world applications, ranging from autonomous systems to network routing, such guarantees are essential. We propose CG4AI, a framework that builds a convex combination of AI models while enforcing linear constraints on the combined output. A master linear program (LP) determines the optimal mixture weights, while a pricing subproblem generates new models guided by LP dual variables, focusing attention on the most violated constraints. A cutting-plane procedure extends feasibility guarantees beyond the training set. We apply CG4AI to two problems: (i) digit classification on MNIST, where we demonstrate four distinct uses of constraints, learning from constraints alone, improving adversarial robustness, correcting misclassified examples, and enforcing output relabeling; and (ii) the multi-commodity flow problem, where link capacity constraints are enforced on neural-network routing predictors. Experiments on MNIST and standard SNDLIB benchmark networks show that CG4AI reliably produces feasible predictors while achieving better accuracy than single-model baselines.

It is proved that, for every $\delta \in (0,1)$, the Glauber dynamics for the uniform distribution on proper $q$-colorings is rapidly mixing when $q \geq (1+\delta)\Delta$ and the underlying graph has girth at least $5$ and maximum degree $\Delta = \Omega_\delta(1)$. This result also extends to general multi-spin systems satisfying a $\textit{local spectral contraction}$ condition, including the anti-ferromagnetic Potts model with $q\geq (1+\delta)(1-\beta)\Delta$. These results are achieved by a new spectral local-to-global principle on graphs with girth at least five for general multi-spin systems, and a novel Fourier analysis for Glauber dynamics on a star. The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra.

The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP '26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomassé; STACS '23], [Bannach, Marwitz, Tantau; STACS '24], [Anand, van den Brand, McCarty; NeurIPS '26], [Kozma, Opler '26], and [Cardinal, McCarty, Yuditsky '26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.

Multi-objective combinatorial optimization arises in a wide range of problems and applications, including the canonical multi-objective MaxCut problem. Differentiable single-instance quadratic methods have recently achieved remarkable performance in single-objective combinatorial optimization. In this paper, we develop a differentiable framework for multi-objective MaxCut by combining an adjacency-based quadratic formulation with linear scalarization, thereby reducing the problem to a preference-conditioned single-objective signed-weight MaxCut problem. Theoretically, we characterize projected gradient ascent (PGA) fixed points and their local dynamics under the signed-weight adjacency formulation. We further characterize how these fixed points depend on preferences and establish their connection to Pareto optimality. Computationally, unlike conventional heuristics and branch-and-bound methods, our approach is GPU-parallelizable and can therefore benefit from substantial performance speedups. We term our algorithm Multi-objective QUadratic Combinatorial Optimization (MO-QUCO) and its parallelized variant pMO-QUCO. Empirically, we evaluate our methods on multi-layered graphs with different sizes and edge-weight distributions. Both our CPU-only and GPU-based algorithms outperform state-of-the-art exact and heuristic methods in terms of wall-clock runtime and objective quality. Despite operating under different computational settings, MO-QUCO also outperforms the SOTA quantum method.

Standard neural architectures often fail to generalize to longer inputs for dynamic programming (DP) targets. We investigate what makes this hard geometrically. Every finite min-plus DP is a shortest path on a DAG, which is equivalently a tropical polynomial whose extended Newton polyhedron encodes the decision boundary of which path wins. We prove these three descriptions (graph, polynomial, polyhedron) form isomorphic semirings at two levels — formal polynomials and their computed functions — connected by operations that characterize all structural redundancies. We then address the length-generalization question geometrically: does the decision boundary at length $T$ decide the boundary at $T+1$? We present two structural negatives. The semiring's two native ways to reduce dimension (setting a variable to each identity) are neither injective nor always closed within the DP. Series and parallel composition fail to construct all DAG topologies from smaller sub-DAGs, and even all terminal-only operations do not capture all DP compositions.

Lipschitz constants are a standard way to quantify the sensitivity of neural networks to small input perturbations, but computing them is difficult even for shallow ReLU networks. We study this problem for two-layer input-convex neural networks (ICNNs), a restricted architecture where nonnegative output weights enforce convexity. Computing the $L_p$-Lipschitz constant for these networks is equivalent to maximizing the dual norm over a zonotope. While $L_1$- and $L_\infty$-norm maximization on zonotopes admit fixed-parameter and polynomial-time algorithms, respectively, the parameterized complexity of the remaining $L_p$-norms was open. We prove that, for every fixed $p\in (1,\infty)\cap \mathbb{Q}$, maximizing the $L_p$-norm over a zonotope in $\mathbb{R}^d$ is W[1]-hard with respect to the dimension $d$. Moreover, our hardness results imply that brute-force enumeration algorithms are essentially optimal for this problem under the Exponential Time Hypothesis. By duality, the same hardness results hold for computing the $L_p$-Lipschitz constant of two-layer ReLU ICNNs. Our proof first establishes the result for the $L_2$-norm and then transfers the construction to arbitrary fixed $p\in (1,\infty)\cap\mathbb{Q}$ using a suitable Taylor approximation. These results resolve the corresponding questions regarding the parameterized complexity status for zonotope norm maximization and two-layer ICNN Lipschitz constants. Our paper resolves an open problem posted at COLT'25. There are several independent concurrent papers resolving the same problem. Our paper prioritizes a clear exposition of the underlying mathematics and conceptual intuitions behind the proof. Additionally, we explicitly describe our research process including the use of LLMs.

We show that there exists a polynomial-time algorithm to find a stable matching in network hypergraphic preference systems. The key connection that drives the algorithm was discovered by chatting with ChatGPT-5.6 Sol Max. We verified it independently and present the details in our own words.

It is shown in this manuscript that a random graph $G$ drawn from the Erdős–Rényi model $\mathcal{G}(n,p)$ with \[ p=p(n)\leq 1/2, \qquad \lim_{n\to+\infty}(np-\log n-\log\log n)=+\infty, \] is a homomorphic core, i.e., every homomorphism from $G$ to itself is an automorphism. This implies tight ETH-based lower bounds of the subgraph isomorphism problem for almost all $k$-vertex patterns with polynomial average degree.

Metric bases of graphs have been widely studied since their introduction in the 1970's by Slater and, independently, by Harary and Melter. In this paper, we concentrate on the existence of vertices in a graph $G$ that belong to all metric bases of $G$. We call these basis forced vertices, and denote the number of them by $\mathrm{bf}(G)$. We show that $\mathrm{bf}(G)\le 2/3(n-k-1)$ for any connected nontrivial graph $G$ of order $n$ having $k$ vertices in each metric basis. In addition, we show that this bound can be attained. Furthermore, the previous result implies the bound $\mathrm{bf}(G)\le 2/5(n-1)$ formulated in terms of the order $n$ of the graph for any nontrivial connected graph $G$. This result answers a question posed by Bagheri et al. in 2016. Moreover, we provide a complete realization of the parameters $n$, $\dim(G)$ and $\mathrm{bf}(G) \ge 1$ within the previous bounds. We consider some extremal cases related to basis forced vertices in a graph, in particular, we give a full characterization of the graphs with $\mathrm{bf}(G) = 2$ and $\dim(G) = n-4$.

We prove three theorems on the flow monoids of finite graphs. First, we show that a non-empty finite graph G = (V, E) is connected if and only if its flow monoid contains a constant map on V, equivalently, if and only if it contains all constant maps on V. Second, we give a new characterization of graph minors in terms of division of flow transformation monoids, together with an algebraic crossing condition that detects edges between the vertex sets being contracted. Third, we strengthen this to an embedded-copy theorem: a graph M is a minor of G if and only if, subject to analogous crossing conditions, the flow transformation monoid of M is realized as the induced action of a subsemigroup of the ambient flow monoid of G, this subsemigroup being a monoid with a local idempotent identity.

We study subsets of the integer lattice represented by single-variable-per-inequality (SVPI), difference-constraint (DC), unit two-variable-per-inequality (UTVPI), and two-variable-per-inequality (TVPI) systems. We relate five viewpoints: inequality representation, discrete convexity, polymorphisms, reconstruction from two-coordinate projections, and fixed points of closure operators. Our central result completely characterizes UTVPI-representability. For every set $S\subseteq\mathbb Z^n$ with $n>1$, \[ \begin{aligned} &S\text{ is UTVPI-representable}\\ &\;\Longleftrightarrow\; S\text{ is closed under the directed midpoint and median operations}\\ &\;\Longleftrightarrow\; S\text{ is integrally convex and $2$-decomposable}. \end{aligned} \] The median condition may instead be replaced by closedness under some majority operation, and the same class is the fixed-point class of a pairwise directed-midpoint closure operator. Thus, all five viewpoints yield equivalent characterizations of UTVPI-representability. In particular, $2$-decomposability is exactly the global condition needed to lift the known two-dimensional equivalence between integral convexity and UTVPI-representability to arbitrary dimension. This theorem is embedded in a broader pairwise-closure theory. For a family $F$ of operations, we define a closure operator by closing every two-coordinate projection under $F$ and joining the resulting sets. Its fixed points are precisely the sets that are both $2$-decomposable and $F$-closed, and we establish a local-to-global criterion for such characterizations. A closed-convex-hull analogue characterizes TVPI-representability. We also characterize SVPI-representability by natural multioperations, prove limitations of operation-based characterizations for several related classes, and determine the complete inclusion hierarchies in the general, Boolean, and two-dimensional settings.

A graph is called 10-tough and $(2P_2 \cup P_1)$-free if every vertex set whose deletion leaves at least two components has cardinality at least ten times the number of those components and if the graph has no induced subgraph consisting of two disjoint edges and an isolated vertex. We prove that every finite simple 10-tough $(2P_2 \cup P_1)$-free graph on at least three vertices is Hamiltonian. The proof splits according to whether some edge has joint neighbourhood of order at most $4n/11$. In the small-neighbourhood case, a matched path-cover is compressed to a prescribed matching. In the large-neighbourhood case, an asymmetric analysis of the two components left by a putative small cut yields the required connectivity bound. A Hamilton cycle through the prescribed edges is then expanded, and a cycle-extension lemma inserts the remaining vertices.

Centrality measures are defined for simple graphs – directed, undirected, weighted or unweighted. Attributed graphs have to be reduced to simple graphs for computing centrality measures. However, when applications with multiple types of relationships are modeled using multilayer networks (MLNs), simple graph algorithms cannot be directly used. Existing approaches typically analyze MLNs by aggregating layers of an MLN into a single graph, which results in the loss of structural and semantic information. The semantic information loss can be more pronounced particularly, in weighted networks. This work focuses on computing degree centrality in weighted homogeneous multilayer networks (HoMLNs) using a decoupling-based framework. The framework performs independent layer-wise analysis on MLNs without reducing them to simple graphs. The decoupling approach allows use of exiting algorithms for each layer and uses minimal information from individual layers for computing degree centrality of HoMLNs. We propose heuristic-based algorithms that strike a balance between accuracy and efficiency. The proposed methods are evaluated against ground truth (GT) results obtained using Boolean OR aggregation and naive baselines. Experimental results on both synthetic and real-world HoMLN datasets demonstrate that the heuristics achieve accuracy comparable to the ground truth while significantly improving computational efficiency, thereby establishing the scalability and effectiveness of the HoMLN algorithms developed using the decoupling approach.

We study autonomous mathematical discovery in the Station, an open-world multi-agent environment in which AI agents from different model families pursue a shared research goal without a central coordinator or scripted pipeline. Agents choose their own research directions, conduct experiments, collaborate and publish papers. These papers accumulate into a shared body of knowledge that later agents can read, cite and extend. We evaluated the Station on 12 mathematical construction problems from the AlphaEvolve study and two additional case studies. Five of the 12 problems yielded results novel relative to the prior literature: a new infinite family of finite field Kakeya sets, new exact 604-point kissing configurations in eleven dimensions, improved bounds for the discretized Kakeya needle and sign uncertainty problems, and a substantially improved lower bound for Erdős's minimum overlap problem. Agents also discovered novel infinite families for Book Ramsey numbers. Their research extended beyond searching for high-scoring constructions: agents developed explanations of their findings and proved theorems outside the assigned tasks. These explanations guided further discoveries and were preserved in the agents' papers, making the underlying insights easier for external researchers to understand and build upon. All presented discoveries are supported by exact constructions or proofs formally verified in Lean. We release the source code, full agent dialogues, papers and verification code, providing a transparent record of how these discoveries emerged.

For integers $k,g \ge 3$ let $n_g(k)$ denote the minimum order of a graph with chromatic number $k$ and girth at least $g$. Exoo and Goedgebeur (DMTCS 2019) proved $26 \le n_6(4) \le 66$; their 66-vertex witness has remained the smallest known 4-chromatic graph of girth 6. We improve both bounds to $29 \le n_6(4) \le 64$. The upper bound is witnessed by an explicit 4-chromatic graph of girth 6 on 64 vertices with 152 edges; it is vertex- and edge-critical, and its automorphism group is cyclic of order 8 and acts semiregularly. The lower bound is an exhaustive isomorph-free computation in the SAT modulo symmetries framework with co-certificate learning, driven by the Liu-Postle edge-density bound for 4-critical graphs of girth five; it re-derives $n_6(4) \ge 26$ by a disjoint method and is validated on the known values $n_4(4)=11$ and $n_5(4)=21$. We complement the bounds with structural obstructions: no smaller witness arises from either known witness by local modifications; no 4-chromatic Cayley graph of girth 6 exists on 54-63 vertices (for orders 59 and 61 no vertex-transitive witness exists at all); and no witness on at most 63 vertices admits a semiregular automorphism group with two or three vertex orbits, for any finite group. Since every known witness of an $n_g(4)$ record with $g \ge 6$ is a lift of a small base graph along a semiregular action, these results close the most symmetric part of that regime below 64 vertices. All properties of the new graph are verified by independent programs and formally certified in the Lean 4 proof assistant: the non-3-colourability is established inside Lean by a formally verified checker that re-validates a 219,532-node refutation certificate, with a machine-checked soundness theorem.

The boxicity of a graph $G$, denoted by $box(G)$, is the minimum integer $d\geq 0$ such that $G$ is the intersection graph of axis-parallel boxes in $\mathbb{R}^d$. The class of zero divisor graphs introduced by Beck (1988) is a popular class of graphs and has been studied extensively by several researchers. Suppose $Z(R)$ is the set of zero divisors of a ring $R$. The zero divisor graph $\Gamma(R)$ for a ring $R $ is defined as the graph with the vertex set $V(\Gamma(R))=Z(R)$ and $E(\Gamma(R))=\{\{x,y\}\colon x,y\in Z(R)\text{ with }x\neq y\text{ and }x y=0\}$. One can define an equivalence relation $\sim$ on $V(\Gamma(R))$ such that for vertices $x$ and $y$, one has $x\sim y$ if and only if $x$ and $y$ have the same annihilator, i.e., $Ann(x)=Ann(y)$. The compressed zero divisor graph $\Gamma_E(R)$ for a ring $R$ is the simple graph obtained from $\Gamma(R)$ by retaining exactly one vertex from each equivalence class induced by $\sim$. In this paper, we completely answer two open questions posed in Discrete Applied Mathematics 391 (2026), pp. 127-136. Let $N=\prod_{i=1}^a p_i^{n_i}$ be the prime factorization of a positive integer $N$ and let $\mathbb{Z}_N$ be the ring of integers modulo $N$. We determine the exact boxicity of the compressed zero divisor graph $\Gamma_E(\mathbb{Z}_N)$. We show that when $a\geq 2$, $box(\Gamma_E(\mathbb{Z}_N))= a-1$ if and only if one of the following is true: $(i)$ $a\geq 2$ and $N$ is the product of two coprime integers $x$ and $y$ such that $x$ is a square-free integer and $y$ is the cube of a prime number; $(ii)$ $a\geq 3$ and $N$ is square-free; $(iii)$ $a\geq 2$, $N$ is cube-free, not square-free, and contains at least one prime divisor $p_i$ such that $n_i=1$. If $a=2$ and $n_1=n_2=1$, then $\Gamma_{E}(\mathbb{Z}_N)$ is a clique, and so, $box(\Gamma_{E}(\mathbb{Z}_N))=0$. In all other cases, $box(\Gamma_{E}(\mathbb{Z}_N))=a$.

Let $\lambda(n)=(-1)^{\Omega(n)}$ be the Liouville function. We prove a fixed power-logarithmic bound for its logarithmically weighted two-point correlations across the full shift range. There is an absolute $c>0$ such that every sufficiently large $x$ admits a single set $\mathcal E_x\subseteq[1,x]$ with $|\mathcal E_x\cap[1,H]|\ll_A H(\log x)^{-A}$ $(1\le H\le x)$ for every fixed $A>0$, while $\max_{\substack{1\le h\le x\ h\notin\mathcal E_x}}\sup_{1\le y\le x}\left|\sum_{n\le y}\frac{\lambda(n)\lambda(n+h)}{n}\right|\ll(\log x)^{1-c}$. The same exceptional-set formulation extends, without an upper cutoff, to all positive integer shifts. Earlier full-range theorems average over the shift; here a fixed saving holds pointwise outside one set whose density in every initial segment is smaller than every fixed negative power of $\log x$. The new middle-scale argument combines a general-good-modulus Liouville deletion lemma with a linear bad-modulus score, a progression Fourier estimate, and a Mellin-localized dilation that separates divisor-dependent endpoints. Maximal fixed-moment bounds evacuate the low prefix and control the long-shift range. Assuming GRH for primitive Dirichlet $L$-functions, we also prove, uniformly for $h\in\mathbb N$ and $1\le y\le x$, $\left|\sum_{n\le y}\frac{\lambda(n)\lambda(n+h)}{n}\right|\le\log(2\min{h,y})+O((\log x)^{1-c_{\mathrm G}})$ for an absolute $c_{\mathrm G}>0$, with no exceptional shifts.

A graph $G$ is apex if $G$ has a vertex $v$ such that $G-v$ is planar. We prove that every $2$-connected apex cubic graph is three-edge-colorable. This result gives the final piece of the proof for the well-known Tutte's three-edge-coloring conjecture from 1966 \cite{tutte}. The proof, as well as the result, generalizes that of the Four Color Theorem, which requires computer checks. As in the previous proof of the Four Color Theorem, the proof is constructive. More precisely, given a $2$-connected apex cubic graph $G$ on $n$ vertices, our reducibility and discharging procedure yields a three-edge-coloring of $G$ in $O(n^2)$ time. As an additional reproducibility check for our computer checks, independent implementations reconstructed from the detailed pseudocode (given in the appendix) using generative AI systems reproduced the required computational results. These reconstructions are not part of the mathematical justification of the theorem, but provide additional evidence for the reproducibility of the computations.

We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online together with their incident edges. After each arrival, the algorithm must maintain a maximum-cardinality matching while minimizing the total number of reallocations, also known as the recourse budget. Despite extensive work, the exact recourse complexity of the problem remains unsettled: the best lower bound is $\Omega(n \log n)$, whereas the best upper bound is $\mathcal{O}(n \log^2 n)$, where $n$ denotes the number of online vertices. Tight upper bounds of $\mathcal{O}(n \log n)$ are known only for restricted graph classes, such as forests. The best known upper bounds are attained by a very simple and natural algorithm SAP, which after each arrival applies a shortest augmenting path, and it is conjectured to be optimal. All known upper bound analyses of this algorithm do not depend on the particular maximum matching maintained by the algorithm. Consequently, they also apply to a more difficult problem, which we call the malicious matching setting: after each arrival, the maintained matching is replaced by a worst-case maximum matching for the next step. This led to the conjecture that the malicious setting still admits an $\mathcal{O}(n \log n)$ recourse bound, in line with the conjectured optimal complexity of the original model. Our main result is an $\Omega(n \log^2 n)$ lower bound for the malicious matching setting, thus disproving the conjecture. Together with the previous upper bound, this settles the asymptotic recourse complexity of the malicious variant of the problem. We complement our lower bound with an upper bound of $\mathcal{O}(n \log n)$ for expander graphs.

The Hadamard maximal determinant problem seeks an $n\times n$ matrix $X$ with entries in $\{\pm 1\}$, which maximizes the determinant $\vert \det X \vert$ for a given order $n \in \mathbb{N}$. We report matrices attaining new record determinants for orders $n\equiv 3\pmod{4}$ between $103$ and $119$, as well as $n=51$. We provide a proof of optimality within a specific family of circulant–block constructions for $X$. For these orders, we recast the Hadamard problem as a sequence reconstruction problem from a pair of periodic autocorrelation functions, subject to certain arithmetic conditions. We describe several learning–based strategies for reconstruction and provide a comparison with classical simulated annealing–style approaches as a benchmark.

Baste et al. (2020) conjectured that every regular graph of positive degree has domination number at most its edge domination number, the least size of a maximal matching. Combining published bounds settles the inequality for every degree at least nine. A reduction proves the inequality whenever one endpoint of each edge of a minimum maximal matching can be chosen to form a dominating set, and the Lovász Local Lemma shows such a choice exists for every degree at least seven, newly closing degrees seven and eight and leaving degrees three through six open. The reduction settles each open degree up to a bounded number of vertices, forty-eight for cubic graphs. At fifty vertices, however, the reduction meets an explicit cubic graph it cannot settle, though the inequality holds there too. The inequality cannot be tightened, since infinitely many cubic graphs have equal domination and edge domination numbers. The cubic case stays open, and even linear arguments from the local structure cannot close it. The middle degrees stay open beyond the graphs already settled.

The Erdős-Pósa theorem states that for every integer $k\geq1$, every graph contains either $k$ vertex-disjoint cycles or a set of $\mathcal{O}(k\log k)$ vertices meeting all cycles. This fundamental min-max duality has been extended to numerous settings, including long cycles, $S$-cycles, that is, cycles containing a vertex in a prescribed set $S$, and cycles satisfying various additional constraints. In contrast, much less is known when the packing itself is required to be induced, namely, when distinct cycles are vertex-disjoint and have no edges between them. We prove that long $S$-cycles admit an induced version of the Erdős-Pósa-type duality. More precisely, we show that there exists a polynomial function $f(k,\ell)$ such that for all integers $k\geq1$ and $\ell\geq3$, every graph contains either an induced packing of $k$ $S$-cycles of length at least $\ell$ or a set of at most $f(k,\ell)$ vertices whose closed neighbourhood intersects all $S$-cycles of length at least $\ell$. The proof introduces a new ear-decomposition technique based on fragile ears and yields a polynomial-time algorithm for every fixed $\ell$.

Fine and Wilf [Proc. Amer. Math. Soc. 1965] showed that any string of length at least $p+q-d$ with periods $p$ and $q$ also has period $d=\gcd(p,q)$. For parameterized strings, Apostolico and Giancarlo [Discrete Appl. Math. 2008] proved an analogue with length bound $p+q$, assuming that the two induced bijections commute. Ideguchi et al. [SPIRE 2023] removed this assumption and gave the bound $p+q+\min(p,q)(\sigma-1)$, where $\sigma$ is the number of distinct letters. This was later improved by Hamai et al. [SPIRE 2024] to $p+q+\min(p,q)(\sigma-2)$, which was used to bound the number of non-equivalent parameterized squares. In this paper, we establish the optimal Fine–Wilf type bound for parameterized strings. Namely, if a string $s$ containing $\sigma$ distinct letters has parameterized periods $p$ and $q$ and satisfies $|s| \ge p+q+(\sigma-3)d+1$, where $d=\gcd(p,q)$, then $d$ is also a parameterized period of $s$. We also give matching lower-bound instances, proving that our bound is optimal for any $\sigma \geq 2$.

We study the linear recurrence order of the Potts model partition function on thermal 2D grid graphs. By restricting the transfer matrix (TM) to the real coupling axis, the physical operator maintains diagonalizability under the Spectral Theorem. We show that this thermal regularization allows the Krylov subspace to saturate the unconstrained planar state capacity, locking the recurrence order to the Dyck path up to reversal (OEIS A007123) for $q \ge 4$. Furthermore, the recurrence order collapses to height-restricted Dyck paths up to reversal (OEIS A001998) for $q=3$ due to finite-index Jones-Wenzl projections, and to the zero-magnetization conservation sector (OEIS A001405) for $q=2$. This framework bridges graph-theoretic combinatorics with the representation theory of physical loop gas models.

Phylogenetic networks model evolutionary histories that involve reticulate events, but their structural complexity makes them difficult to interpret. Extracting their simple substructures both clarifies the evolutionary pathways and quantifies the complexity of the networks themselves. For a given rooted almost-binary phylogenetic network, the Level Minimization problem asks for a spanning subgraph that has the same root and leaf-set and whose level is minimum, i.e., which is as close to a tree as possible. Networks for which the minimum level is zero are known as tree-based networks and can be recognized in linear time. However, Level Minimization is NP-hard in general. State-of-the-art algorithms rely on exhaustive searches of the solution spaces and hence apply only to networks of limited size. In this paper, we propose two methods for Level Minimization using integer linear programming: an exact formulation for finding such a subgraph of level at most one, and a heuristic formulation for the general case. Computational experiments confirmed the practicality of both formulations. An application to ancestral recombination graphs suggests that the minimum level provides an alternative measure of the topological complexity of an inferred network.

We study \emph{$T$-Robinson spaces}, a tree-based generalization of Robinson spaces in which every path of a compatible tree induces a Robinson subspace. This framework extends the classical notion of Robinsonian representations from linear orderings to tree structures, allowing the modeling of hierarchical and branching data. We establish a complete combinatorial characterization of $T$-Robinson spaces by proving their equivalence with several graph- and hypergraph-theoretic properties. In particular, we show that a dissimilarity space is $T$-Robinson if and only if all its level graphs are dually chordal with a common compatible tree. Combined with the characterization of hypertrees established by Brucker~\cite{brucker2005hypertrees}, this yields the equivalent characterization in terms of the associated cluster, ball, and 2-ball hypergraphs being hypertrees. Building upon these structural results, we develop a recognition algorithm with complexity \(O(K n^{2})\), where \(K\) denotes the number of minimum spanning trees of the dissimilarity space, improving upon existing hypertree-based approaches whenever \(K\) remains moderate. We further introduce a quantitative measure of $T$-Robinson structure that evaluates the extent to which an arbitrary dissimilarity space admits a tree-like representation. Finally, we discuss applications to real-world datasets, illustrating how $T$-Robinson spaces provide an interpretable framework for analyzing and organizing relational data.

Planning accessible public services such as health care, emergency response, and schools often requires not only choosing where to open facilities but also improving the network that connects people to them, for example upgrading flood-prone roads in vulnerable regions. Most location models, however, take the network as fixed and the budget as given. We study the Maximum Covering Network Design Problem, in which a single budget is shared between opening facilities and upgrading weak links to maximize the population within a target travel distance of an open facility. The problem is hard even on the simplest networks, and planners usually want to see how coverage grows with the budget, not a single plan. We develop an exact dynamic-programming framework that exploits a property common to real road networks: their low connectivity, with many cut points whose removal disconnects the network. On trees, the recursion is self-contained: each state reduces to a few simple facility and upgrade choices that are fast to compute without a solver, giving predictable running times; for larger budgets and travel distances it outperforms solving the MILP formulation directly. On general low-connectivity networks, the framework decomposes the problem at the cut points and embeds a given MILP formulation to solve the resulting pieces, coordinating them through coverage conditions at the interfaces. This lets us compare a formulation on its own against the same formulation inside the framework: across 306 test cases the framework matches or outperforms direct solving on more than 80% of instances. Because it evaluates all budget levels in a single run, it also yields the full coverage-versus-budget curve at no extra cost, whereas direct solving must split its time across individual budgets.