Discrete Mathematics Papers

ALT We study the interplay between two types of graph classes: the ones defined by intersections of geometric objects and the ones defined by the absence of a substructure. More precisely, we study intersection graphs that are grounded, that is, the objects lie above a horizontal line that they touch, and ordered graphs with forbidden patterns, that is, ordered graphs that avoid a set of ordered induced subgraphs. These two approaches are fundamentally different, but it is known that several interesting graph classes have both types of characterizations, and we aim to understand whether this is a general phenomenon. Our contributions are the following. First, we identify a family of patterns on four vertices and a natural hierarchy of intersection graphs of strings whose classes are nicely interleaved. This raises hopes to prove connections between the two perspectives. Second, we dampen these hopes by proving that a class of (ordered) intersection graphs that we study cannot be characteri

ALT Given a finite field Fq, we say that a set A⊆ Fⁿq is an (r,c) subspace evasive set if and only if for any affine subspace U⊆ Fⁿq with bounded dimension dim(U)≤ r, the intersection size |A∩ U| is at most c. The probabilistic method shows the existence of (r,c) subspace evasive sets with |A| = q⁽¹⁻εn) with c = O(r/ε). However, the best explicit constructions by Dvir–Lovett (STOC 2012) and Ben-Aroya–Shinkar (CJTCS 2013) have c growing as an exponential function of r. Here, we give an explicit construction of such subspace evasive set that achieves the intersection bound c=O(min(r{log(r/}ε)/ε, r²/ε)) when both r and 1/ε are constants. Our approach is simple and the key idea is to compose subspace design codes (Guruswami-Xing, STOC 2013) with a suitably chosen “local” subspace evasive set. As a corollary, we give the first construction of an explicit (strongly) capacity-achieving list-recoverable code with nearly optimal list size, circumventing all previously-known barriers to construction

ALT A queue layout of a graph consists of a linear order of the vertices and a partition of the edges into queues so that no two edges in a single queue are nested. The minimum number of queues needed in a queue layout of a graph is called its queue number. A planar product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood (JACM, 2020) states that every planar graph is a subgraph of the strong product of a graph of simple treewidth at most 3, a clique K₃, and a path. The result has been used to show that the queue number of planar graphs is at most 49. Recently, Bekos, Gronemann, and Raftopoulou (Algorithmica, 2023) investigated how the general approach based on the product structure can be optimized for planar graphs. They claim that an appropriate reordering of the three vertices associated with each bag in the product structure decomposition, called a tripod, reduces the queue number of planar graphs to 42. We first highlight a gap in their queue layout algorithm: o

ALT We show that, given a Horn expression and a family of inclusion-wise maximal satisfiable subsets of its clauses, deciding whether there exists another maximal satisfiable subset is NP-complete. As a consequence, unless P=NP, there is no output-polynomial time algorithm enumerating the maximal satisfiable subformulas of a Horn expression.

ALT Recently, a new coordinate-based normalization has been introduced in [1] to represent tetrahedral similarity classes by normalized coordinates, enabling the study of LEB orbits as a discrete dynamical system. However, the uniqueness of this representation is not guaranteed when two or more edges adjacent to the selected longest edge have the same minimum length and remain admissible under the normalization criteria. In this paper, we demonstrate that different admissible choices may lead to distinct normalized coordinate representations of the same tetrahedral similarity class. We first present an explicit counterexample in which two admissible vertex labelings yield different normalized coordinate representations related by reflection, despite corresponding to the same similarity class. We then provide a systematic classification of the nine possible edge configurations arising in the selection of the canonical face when the longest edge of the tetrahedron is unique, and analyze the

ALT We give an exact formula for the fractional distance-edge-monitoring number of G∘ H, where G is connected of order m≥2 and H has order n≥2. By the previously established endpoint-monitoring property, the fractional monitoring program reduces to fractional vertex cover, whose linear-programming dual is fractional matching. Writing dc(H) for the critical difference of H, we obtain demf(G∘ H)=(mn-D(G,H))/2, where D(G,H)=max{A∈ℐ(G)}(dc(H)|A|-n|N_G(A)|) and ℐ(G) denotes the family of all independent sets of G, including the empty set, while N_G(A) is the open neighborhood of A. This formula characterizes the products attaining mn/2 and gives an equality criterion for the fractional matching lower bound of Ma, Cheng, Mao and Wang. Under the stated hypotheses, the lower bound of Ma et al. is attained if and only if either factor has a fractional perfect matching or H is edgeless. Two outer trees show that the factor orders and fractional matching numbers do not determine the product value.

ALT We study the positivity of sequences f that satisfy a third-order holonomic recurrence f(n+3)=P₂(n) f(n+2) + P₁(n) f(n+1) + P₀(n) f(n) whose coefficients P₀, P₁ and P₂ are rational functions in ℝ(x). We provide a sufficient condition on P₀, P₁ and P₂ for the recurrence to admit a solution all but finitely many terms of which are positive, and whose positivity is robust under small perturbations of the initial values. This sufficient condition is also a necessary condition for a subclass of the recurrences. By developing the proof of this sufficient condition, for another subclass of the recurrences, we show that it is decidable whether all the terms of a given sequence are positive for any initial values outside an exceptional plane. It is common to construct a positivity certificate, which guarantees the positivity of a solution, to show this kind of decidability. In this paper, we construct a new type of positivity certificate via the S-scaled difference f(n+1) - S(n) f(n) for a suit

ALT We consider matroid intersection under the minimum rank oracle model, in which two matroids are accessible only through an oracle that returns the minimum of the ranks of a given set in the two matroids. By Edmonds' theorem, this oracle determines the matroid intersection polytope, although it does not reveal the exchangeability graphs on which classical algorithms rely. Recent work by Bárász, Bérczi, Király, Oki, Yamaguchi, and Yokoi (2025) showed that unweighted matroid intersection is polynomially solvable in this model. In this paper, we present a strongly polynomial-time algorithm for weighted matroid intersection in this model. The key to our algorithm is a polynomial-size extended formulation of tangent cones of common base polytopes that can be constructed using the minimum rank oracle. We also give min-max theorems in terms of the minimum rank function via 1/3-submodularity, and present a strongly polynomial-time algorithm to compute an optimal dual solution.

ALT In pinwheel scheduling with real periods, an instance consists of n tasks with real periods 1≤ a₁≤ a₂≤⋯≤ aₙ. The goal is to find a schedule that assigns one task to each day indefinitely such that, for every task i∈{1,…,n} and every positive integer ℓ, task i occurs at least ℓ times in every block of ⌈ℓ aᵢ⌉ consecutive days. Given an instance (a₁,a₂,…,aₙ), its dimension is n, its density is ∑ᵢ₌₁ⁿ1/aᵢ, and its potential is ∑ᵢ₌₁ⁿ⁻¹1/aᵢ. We prove that every real-valued instance of density at most 5/6 admits a periodic schedule of period length less than 4⋅2ⁿ. For integer periods, the 5/6 density bound was a long-standing conjecture settled by Kawamura using a computer-assisted proof [STOC 2024, PNAS 2026]. Our result confirms the real-period conjecture of Fujiwara, Miyagi, and Ouchi [DMTCS 2026]. Our computer-assisted proof builds on Kawamura's ideas while using fewer explicit schedules. It combines dimension reduction by folding with nine satisfiability modulo theories (SMT) checks over

ALT Dallard, Milanič, and Štorgel, and independently Gartland and Lokshtanov, conjectured that for every planar graph H, Maximum Weight Independent Set and List 3-Coloring are polynomial-time solvable in H-induced-minor-free graphs. As a structural explanation, Gartland and Lokshtanov further conjectured that such graphs admit balanced separators dominated by a constant number of vertices. Bonnet and Chang recently refuted the independent-set part of the algorithmic conjecture, by showing that Maximum Independent Set is NP-hard in graphs excluding the 5×5 grid as an induced minor. We revisit both conjectures. We show that the graphs used by Bonnet and Chang exclude much simpler planar graphs, including several 16-vertex trees, and we introduce a second, independent family of hard instances. We also prove that 3-Coloring is NP-hard in both settings, thus refuting the algorithmic conjecture in full, even in its quasipolynomial version, unless NP⊆QP. On the structural side, we identify planar

ALT One aspect of pangenome analysis that has received little attention is the recovery of the individual genomes that gave rise to a pangenome graph. While substantial effort has focused on constructing pangenomes from collections of genomes, the inverse problem remains largely unexplored: given a pangenome represented as a set of weighted adjacencies, can we reconstruct the constituent linear genomes that underlie it? Thus we introduce the pangenome peeling problem, which seeks to decompose a weighted adjacency graph into a collection of linear genomes whose combined adjacencies reproduce the observed edge weights. This problem is particularly relevant when considering ancestral pangenomes, where the graph structure may be known or inferred, but the underlying genomes are not. As a first step toward addressing this problem, we formally define pangenome peeling and derive a lower bound on the minimum number of genomes required to explain a given weighted adjacency graph. We then present t

ALT A proper conflict-free coloring is a proper coloring in which each nonisolated vertex has a neighbor whose color occurs exactly once in its open neighborhood. We prove that deciding whether the clique number of colors suffices is NP-complete on undirected path graphs, even with a supplied representation by paths in a star. One extra color suffices on every instance in the reduction. We also prove NP-completeness on chordal bipartite graphs for every fixed palette size k≥4. For strongly chordal graphs, reverse simple elimination gives a constructive upper bound of one more than the clique number. We obtain exact polynomial-time algorithms under several conditions on the maximum cliques, including when they induce a connected subtree of a clique tree. For strictly chordal graphs we characterize the optimum and construct an optimal coloring in O(n+m) time, where n and m count the vertices and edges. For strongly chordal graphs with clique-tree separators of size at most s, we give an exac

ALT We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in our framework is to relate convergence within a phase to the geometry of disagreements between two independent configurations drawn from that phase. As applications of our approach, we consider three canonical models on random regular graphs that have been central to low-temperature sampling, and establish fast convergence from natural initialisations of Glauber dynamics for every fixed degree. We show: — For the hard-core model on random bipartite d-regular graphs, Glauber dynamics initialised from either one-sided independent set mixes within the corresponding phase in n³/²⁺ᵒ⁽¹) steps throughout the non-uniqueness regime λ>λc(d). — For the random-cluster model on random d-regular graphs, for every real q>2, Glauber dynami

ALT The boxicity of an undirected graph Γ, denoted as box(Γ), is the smallest non-negative integer d such that Γ can be represented as the intersection graph of axis-parallel rectangular boxes in mathbbR^d. The power graph of a group G, denoted as Pow(G), is an undirected graph whose vertex set is the group itself, with two elements being adjacent if one is a power of the other. We determine the exact boxicity of power graphs of finite nilpotent groups. For a cyclic group of order n=prod_i=1^rp_i^e_i>1, where the p_i are distinct primes, we prove that its power graph has boxicity \sum_i=1^re_i-max_i e_i. For a finite nilpotent group G, let the number of noncyclic odd Sylow subgroups be denoted by t(G). If G has odd order or if G has a cyclic Sylow 2-subgroup, then box(Pow(G))=box(Pow(mathbbZ_exp(G)))+t(G), where exp(G) denotes the exponent of a group G. When the Sylow 2-subgroup is noncyclic, and the odd part is nontrivial, the boxicity equals this value or one more, and we characterise pr

ALT A graph class C is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from C using a fixed formula of first-order logic. We prove that every monadically dependent graph class has almost bounded merge-width, thereby confirming a conjecture of the first and the last author [STOC '25]. Our proof is algorithmic and the witnessing decompositions in the form of merge sequences can be computed in nearly-cubic time. This is a step towards the proof of fixed-parameter tractability of model checking first-order logic on monadically dependent graph classes, which is achieved in a companion paper.

ALT In [Combinatorica 1996], Reed, Robertson, Seymour and Thomas proved Younger's conjecture dating back to 1973 that states that directed cycles have the Erdős-Pósa property. Specifically, they showed that every directed graph D contains either k arc-disjoint cycles or a set of at most f(k) arcs that intersect every directed cycle. The function f, depending only on k, is however notoriously large–in fact, not even elementary. The first improvement on this function was only very recently provided by Hatzel, Kreutzer, Milani, and Muzi [FOCS 2024] who showed that f can be taken to be an exponential tower of height 8. In this work, we improve this function to O(k⁴) in the case where the digraph is Eulerian. This also answers an open question by Wahlström [Springer Monographs in Mathematics 2018] who asked explicitly when Eulerian digraphs have a polynomial Erdős-Pósa property. The only other known result about Erdős-Pósa on Eulerian digraphs is a result from Seymour [Combinatorica 1996] who s

ALT We view a k× n Latin rectangle as n points in the grid [n]ᵏ. Each symbol gives one point, whose coordinates are the columns it occupies. The rectangle is balanced when these points are pairwise equidistant in the ℓ₁ metric. Its imbalance measures the distance from this ideal. We study the minimum imbalance from three sides. Constructively, we use a simulated annealing that moves symbols within rows and only penalises column clashes. Against the reference table of Voboril et al. (2025), it improves 33 of the 51 non-square values for 8≤ n≤ 13, by up to 39.4%, and matches the rest. A cheap invariant, the row group, certifies that none of the 33 new rectangles is isotopic to rows of a group table, so the earlier column-swapping local search cannot reach any of them. Exactly, a computer-assisted branch and bound proves that the minimum imbalance of a 3× 9 rectangle is 56. Díaz et al. found this value, but its optimality was open. A sharper pruning bound, derived from the identity I=2∑(d-t)⁺

ALT The classification of K-geodetic graphs is a fundamental problem in graph theory concerning the number of shortest paths connecting pairs of vertices. A graph is called K-geodetic if every pair of distinct vertices is joined by at most K geodesics, where a geodesic is a shortest path between two vertices. The cases K=1,2,3 correspond, respectively, to geodetic, bigeodetic, and trigeodetic graphs. Despite substantial progress in the study of their structural properties, a comprehensive classification of these graph families remains elusive. This paper develops a research framework for investigating the classification problems by combining metric graph theory, distance-regular graphs, algebraic graph theory, and combinatorial design theory. Particular attention is given to distance-regular graphs, for which the number of geodesics between vertices at a fixed distance is determined by the intersection numbers of the graph. This property converts the K-geodetic condition into a finite coll

ALT A natural way to compare two graphs is to align their vertex sets by a bijection and to measure the difference of the aligned adjacency matrices in a matrix norm. Depending on the norm, this yields, for example, the edit distance, the cut distance, the spectral distance, and the local edit distance. To make these distances applicable to graphs of different order, one can consider blowups of the graphs or, equivalently, relax bijections to fractional alignments, that is, optimal transport plans between the uniform distributions on the vertex sets, in the spirit of Gromov-Wasserstein distances. We investigate how much the optimal transport versions can differ from their bijective counterparts, that is, we quantify their integrality gaps. For the edit distance, we improve the best known upper bound on the integrality gap from 3 to 2 and the lower bound from 6/5 to 4/3. For the cut distance, we approach Lovász's conjecture that δ□ ≤ 2δ□ᴼᵀ from both sides. We improve the previously best kno

ALT In the random-pair Monte shuffle on n cards, each step chooses two positions independently and uniformly and exchanges their cards with probability 1/2. The chosen positions are public; the decisions to exchange cards remain hidden. We prove that the mixing time in expected conditional total variation distance is 2nlog n+O(n), with an exact leading constant and an O(n) cutoff window. To our knowledge, this is the first public-schedule Monte shuffle whose full-permutation mixing time has been determined up to an additive O(n) term. The upper bound follows by comparing two executions with the same public schedule to a classical random-transposition walk. For the lower bound, we construct a schedule-dependent test function and estimate its variance using a matrix-averaging operator. Combined with the depth bound of Czumaj and Lingas, the mixing estimate gives public switching networks with at most 2nlog n+O(n) switches and O(log n) depth for fixed error and failure probabilities. The auth