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