cs.DM — Pith

Top Pith

5

math.CO 2026-05-22 2 theorems

Projection of flags complex gives sub-polynomial expander

by Max Hopkins, Arka Ray

A Simple Sub-Polynomial Degree Coboundary Expander

A combinatorial construction from subspace chains achieves spectral and coboundary expansion at once, yielding near-linear PCPs and hypergr

abstract click to expand

High dimensional expanders simultaneously satisfying spectral and combinatorial (coboundary) expansion have recently played a major role in breakthroughs in PCP and coding theory, but the only known construction of such complexes is extremely involved, requiring deep algebraic number theory. In this work, we give an extremely simple combinatorial construction of a sub-polynomial degree complex based on projections of the flags complex (subspace chains) that is (i) a local spectral expander, (ii) a coboundary expander, and (iii) a swap coboundary expander. As a corollary, we also give the first near-linear size combinatorial hypergraphs with good agreement tests in the '1%' regime, and a simple PCP construction with near-linear size.

0

Top Pith

5

stat.ML 2026-05-20 2 theorems

Contradiction graph decides VC dimension threshold for any m

by Jesse Campbell, Daniel Ibaibarriaga +1 more

Contradiction Graphs Determine VC Dimension

Vertices are realizable label sequences of length m; edges mark label disagreements on shared points, fixing whether dimension meets or tops

abstract click to expand

We study the contradiction graphs associated with binary concept classes. For a class $H \subseteq \{0,1\}^X$, the order-$m$ contradiction graph $G_m(H)$ has as vertices the $H$-realizable labeled sequences of length $m$, with two vertices adjacent when the two sequences assign opposite labels to some common domain point. Our main result is that the single graph $G_m(H)$ determines the threshold predicate $\mathrm{VCdim}(H)\ge m$. Consequently, the full sequence $(G_m(H))_{m \ge 1}$ determines the exact VC dimension and, in particular, detects finite versus infinite VC dimension, answering a question posed by Alon et al. (2024).

0

Top Pith

4

cs.DM 2026-05-14

Gallai vertex decision is Θ₂^p-complete

by Amir Nikabadi, Eva Rotenberg +1 more

The Gallai Vertex Problem is Theta₂^p-Complete

The problem requires a logarithmic number of parallel NP queries and rules out constant-factor approximations for the longest-path hitting-1

abstract click to expand

When a graph $G$ admits a vertex $v$ that is contained in all its longest paths, we call $v$ a Gallai vertex. These are named after Gallai, who in 1966 asked the question if it is true that every connected graph contains such a vertex. This was soon answered in the negative by Walther and Zamfirescu, who presented a graph in which every vertex is omitted by some longest path of the graph. In spite of its long history, the Gallai Vertex Problem, i.e. determining whether a graph has a Gallai vertex, was until now neither known to be NP- nor co-NP-hard. In this work, we show something much stronger, as we completely settle the computational complexity of determining whether a graph has a Gallai vertex: we show that it is complete for the complexity class $\Theta_2^p = \text{P}^{\text{NP}[\log n]}$. This class, also known as parallel access to NP, is a complexity class larger than NP situated just below the class $\Sigma^p_2$ in Stockmeyer's polynomial hierarchy. In more generality, the longest path transversal number of a connected graph is the minimum size of a set of vertices that intersects all its longest paths. I.e. if the graph has a Gallai vertex, its longest path transversal number is $1$. Thus, as a consequence of our theorem, the longest path transversal number of a graph cannot be approximated in polynomial time by a factor better than 2, unless $\text{P} = \text{NP}$. In fact, using related techniques, we show a strengthening of this result: For any constant $C$, if there is a graph with longest path transversal number $C$, then there is no polynomial time algorithm for approximating the longest path transversal number by a factor better than $C$, unless $\text{P} = \text{NP}$. In particular, this excludes approximation by a factor below $3$. Similar results hold for the longest cycle transversal.

0

math.PR 2026-07-03

Subcritical percolation gives spin mixing time log N / lambda

by Alexandre Stauffer, Oskar Vavtar

Mixing times of spin systems on dynamical percolation

When edge flips are slow the combined chain equilibrates in time proportional to log of system size divided by the flip rate.

abstract click to expand

We study the mixing times of stochastic spin systems corresponding to nearest-neighbour Glauber dynamics on dynamical percolation, defined on $d$-dimensional torus of side-length $N$. In this model, the status of each edge (open or closed) updates independently at rate $\lambda>0$, according to $\mathrm{Ber}(p)$ samples. Simultaneously, the spin of each site updates at rate $1$ according to Glauber dynamics on the environment restricted to open edges. We show that for a relatively general class of nearest-neighbour systems, as long as $p<p_c(d)$, for any temperature, if $\lambda$ is sufficiently small, the mixing time is of order $\frac{\log N}{\lambda}$. This Markov chain is non-reversible, and the proof is obtained by developing a particular coupling that couples together local configurations whenever the environment behaves well.

0

math.CO 2026-07-03

Minor-free graphs admit 3-colorings with n^{4/9} cluster size

by Vida Dujmović, Hussein Houdrouge +1 more

3-Colouring Graphs Excluding a Fixed Minor

Extends the planar result to all proper minor-closed classes and improves the 2008 square-root bound

abstract click to expand

We show that, for every fixed graph $H$, every $n$-vertex graph $G$ that excludes $H$ as a minor is $3$-colourable with clustering $O_H(n^{4/9})$. That is, there exists a function $f$ such that for every graph $H$, every $n\ge 1$, every $n$-vertex graph $G$ that excludes $H$ as a minor has a vertex colouring with $3$ colours in which each monochromatic component has size at most $f(H)\cdot n^{4/9}$. This generalizes a recent result of Dujmovi\'c, Morin, Norin, and Wood (\textit{arXiv}:2507.03163) from planar graphs to all proper minor-closed graph classes and is the first improvement on clustered $3$-colouring of proper minor-closed graph classes since the upper bound of $O_H(\sqrt{n})$ due to Linial, Matou\v{s}ek, Sheffet, and Tardos (\textit{Comb. Prob. Comput.}, \textbf{17}(4):577--589, 2008).

0

math.CO 2026-07-03

Bounded row treewidth allows unbounded geodesic treewidth

by Laura Merker, Lena Scherzer +1 more

Separating Geodesic Structure and Product Structure

Graphs of bounded row treewidth can require arbitrarily large geodesic treewidth; deciding geodesic treewidth 1 for treewidth-2 graphs is in

abstract click to expand

The geodesic treewidth of a graph $ G $ is the smallest $k$ for which there is a partition $\mathcal{P}$ into geodesics such that $G/\mathcal{P}$ has treewidth $k$, where $G/\mathcal{P}$ is obtained from $ G $ by contracting each part of $ \mathcal{P} $. Based on this notion, row treewidth was developed and is defined for a graph $ G $ as the smallest $ k $ such that $ G \subseteq H \boxtimes P $ for some graph $ H $ of treewidth $ k $ and a path $ P $. Equivalently, the row treewidth of a graph $ G $ is the smallest $ k $ for which there is a partition $ \mathcal{P} $ into disjoint unions of geodesics that are aligned with respect to some layering such that $ G/\mathcal{P} $ has treewidth $ k $. We separate the two notions by showing that bounded row treewidth does not imply bounded geodesic treewidth and by presenting a polynomial-time algorithm to decide whether a graph of treewidth 2 has geodesic treewidth 1, which is known to be NP-hard for row treewidth [Biedl, Eppstein, Ueckerdt, 2025]. More generally, we provide an algorithm to decide whether a given graph has geodesic treewidth at most $ d $ that is XP in the treewidth, whereas there is no such algorithm for row treewidth, unless P = NP [Biedl, Eppstein, Ueckerdt, 2025]. On the other hand, we show that computing the geodesic treewidth is NP-hard and that every graph with geodesic treewidth 1 has bounded row treewidth. Moreover, we improve the best known lower bound on the geodesic treewidth of planar graphs to 5.

0

math.CO 2026-07-02

Annihilation gap bounded by 2μ + 1 − ceil(sqrt(6μ))

by Ohr Kadrawi, Vadim E. Levit

Annihilation, Independence, and Residue: Sharp Matching Bounds for the Annihilation Gap and a TxGraffiti Application

The difference a(G) − α(G) never exceeds a closed-form function of the maximum matching size, attained for every μ.

abstract click to expand

Let $G$ be a finite simple graph. The annihilation number $a(G)$ is an efficiently computable upper bound on the independence number $\alpha(G)$. We develop a sharp matching-number theory for the gap $a(G)-\alpha(G)$. The strongest general theorem is the exact closed form \[a(G)-\alpha(G)\leq 2\mu(G)+1- \lceil \sqrt{6 \mu(G)} \rceil \qquad(\mu(G)\geq 1), \] and the bound is attained for every prescribed matching number. We also prove sharp matching-dependent bounds for forests, bipartite graphs, and K\"onig-Egerv\'ary graphs, with equality constructions, equality certificates, and equality criteria. Finally, we treat a TxGraffiti output as a machine-conjecture case study. Using annihilating decompositions together with the classical Havel-Hakimi residue inequality $res(G)\leq \alpha(G)$, we give an independent proof of the TxGraffiti annihilation-residue inequality \[ \alpha(G)\geq \frac{a(G)+res(G)}{\Delta(G)} \] for every connected graph $G$ of order at least three, show that both hypotheses are necessary, and compare this proof with a recent Caro-Wei approach. We also refine the Caro-Wei annihilation estimate by an explicit nonnegative slack term, identify its equality cases in degree-sequence form, and combine the refinement with our exact matching-number bound to obtain a combined computable bracket for the independence number and a Gupta-residue bound for the annihilation gap.

0

cs.CG 2026-07-02

Convex polygon reconstruction mapped across all one- and two-feature cases

by Alexander Baumann, Therese Biedl +4 more

On Reconstructing a Convex Polygon from Partial Information

Study supplies algorithms and hardness results for some scenarios and leaves many open

abstract click to expand

The reconstruction problem asks to construct a (convex) polygon that has a specified set of features, such as an ordered set of edge-lengths or an ordered set of polygon-angles. In this paper, we do a systematic exploration of the reconstruction problem in all scenarios where one or two sets of features have been specified. Some of these scenarios were well-studied already, for some we develop testing-algorithms and/or hardness results, and many give rise to interesting open problems for future study.

0

cs.DS 2026-07-02

Hypergraph components found with O(n) cut queries

by Deeparnab Chakrabarty, Hang Liao

Query Complexity of Hypergraph Connectivity and Learnability using CUT Oracles

Independent families bypass the identifiability barrier that blocks exact edge reconstruction.

abstract click to expand

We investigate the power of CUT queries to reveal the structure of unknown hypergraphs. While simple graphs allow for optimal $O(n)$-query connectivity algorithms, hypergraphs face a fundamental identifiability barrier in that distinct hypergraphs can share identical cut-profiles, making exact edge learning impossible in general, a primitive crucial in the graph connectivity algorithms. We first present a zero-error randomized algorithm that identifies the connected components of any weighted hypergraph using $O(n)$ expected queries, matching the $\Omega(n)$ lower bound. This approach bypasses the reconstruction barrier by introducing the notion of ``independent families'' -- vertex subpartitions that do not share hyperedges -- and iteratively coarsening them using auxiliary weighted graph connectivity techniques [Liao-Chakrabarty, 2024]. Second, we demonstrate that the impossibility of exact learning depends on hyperedge parity. For even-parity hypergraphs, we show that the structure is reconstructible using a M\"obius transform on the CUT function to implement binary-search-style vertex identification. This yields deterministic algorithms for obtaining $k$-connectivity certificates for $r$-bounded even hypergraphs in $\tilde{O}_r(kn)$ queries. Finally, we bypass parity and rank constraints for linear hypergraphs, achieving a subquadratic $\tilde{O}(kn^{1.5})$ query complexity for $k$-connectivity. This significantly improves upon the general $\tilde{O}(n^2)$ bound derived via symmetric submodular function minimization.

0

cs.GT 2026-07-02

The paper develops online algorithms for allocating indivisible items with mixed positive

by Georgios Amanatidis, Giulio Giaconi +2 more

Online Fair Division Meets Reordering Buffers

With buffers of size linear in k and number of agents, algorithms achieve EF1 at every step and EF at most steps for personalized k-value…

abstract click to expand

We study the online fair division of indivisible mixed manna among agents with additive valuation functions. Under the standard online model, at each time step an indivisible item arrives; each agent may assign it a positive, negative, or zero value, and it must be irrevocably allocated, before the arrival of the next item. At the same time, we also wish to maintain some fairness guarantee, and in this work we focus on envy-freeness (EF) and one of its most prominent relaxations, envy-freeness up to one item (EF1). Given the strong negative and the scarce positive results for this problem without additional assumptions, we augment our algorithms with buffers that can store and rearrange a limited number of items. This setting interpolates naturally between the fully online case (no buffer) and the fully offline case (a buffer large enough to hold all items). We show that algorithms equipped with reasonably sized buffers can achieve strong guarantees for personalized $k$-value instances, i.e., instances in which each agent assigns at most $k$ distinct values to items. In particular, we construct allocations that are EF1 at every time step and EF at most time steps, using a buffer of size linear in $k$ and in the number of agents. Our approach relies on novel combinatorial arguments and on constructing a sequence of envy-free matchings that allocates most items. Finally, we extend our results to general additive valuation functions, with a dependence on the largest per-agent ratio between two values of the same sign, and we also identify limitations of our approach via impossibility results on the use of buffers with smaller size.

0

math.CO 2026-07-02

One forbidden subgraph characterizes balanced distance-hereditary graphs

by Lucía Busolini, Guillermo Durán +1 more

Characterization and linear-time recognition of balanced distance-hereditary graphs

Equivalence with hereditary clique-Helly property yields linear-time recognition inside this class.

abstract click to expand

A graph is balanced if its clique-matrix contains no square submatrix of odd order with exactly two $1$'s in each row and in each column. Although it is known that a graph is balanced if and only if it contains no induced extended odd sun, a characterization of balanced graphs by minimal forbidden induced subgraphs is still unknown. In this work, we prove that, within the class of distance-hereditary graphs, balanced graphs are exactly the hereditary clique-Helly graphs. Equivalently, they are characterized by a single forbidden induced subgraph, namely $\overline{3K_2}$. From this result, we derive an explicit linear-time algorithm that decides balancedness within the class of distance-hereditary graphs and returns an induced $\overline{3K_2}$ when the input graph is not balanced.

0

math.CO 2026-07-02

Fixed point families give largest t-intersecting permutations

by Nathan Keller, Andrey Kupavskii +2 more

A Complete Intersection Theorem for Large Permutation Groups

For all n larger than some n0 the maximum t-intersecting families in S_n are the F_{n,t,r} families defined by fixed points in an initial se

abstract click to expand

A family of permutations is called $t$-intersecting if any two permutations in the family agree on at least $t$ elements. We prove that there exists $n_0 \in \mathbb{N}$ such that for any $n>n_0$ and any $1 \leq t \leq n$, the maximum size of a $t$-intersecting family in $S_n$ is obtained by one of the families $\mathcal{F}_{n,t,r}=\{\sigma \in S_n: |\mathrm{Fixed}(\sigma) \cap \{1,2,\ldots,t+2r\}|\geq t+r\}$, where $\mathrm{Fixed}(\sigma)$ is the set of fixed points of $\sigma$. This proves an analogue of the classical Complete Intersection Theorem for large permutation groups, thus providing an essentially complete solution of the Deza-Frankl intersection problem for permutations (1977).

0

math.CO 2026-07-01

Chromatic Sum complexity fully classified on forbidden graph classes

by Clément Dallard, Daniël Paulusma +1 more

Determining the Complexity of Chromatic Sum in Classes Defined by a Set of Forbidden Graphs

New NP-completeness result on planar subdivisions completes the map for all minor-free and H-free classes.

abstract click to expand

The Chromatic Sum problem asks, given a graph $G$ and an integer $k$, whether $G$ admits a colouring $c$ with sum $\sum_{v\in V}c(v) \leq k$. We study the complexity of Chromatic Sum on graph classes defined by some set of forbidden graphs. First, we show that three known frameworks fully classify the complexity of Chromatic Sum on $HH$-minor-free graphs and $HH$-topological-minor-free graphs for any set of graphs $HH$, and on $HH$-subgraph-free graphs for any finite set of graphs $HH$. To show this, we prove a new NP-completeness result for Chromatic Sum on certain subdivisions of planar subcubic graphs. Next, we consider other containment relations. We formalise a novel framework of problems that are NP-complete for planar graphs as well as for graphs of bounded independence number. For every problem in this framework, we obtain an almost complete complexity classification on $H$-induced-minor-free graphs, $H$-induced-topological-minor-free graphs, and $H$-free graphs for every graph $H$. We show that Chromatic Sum belongs to this framework, as do several other problems. We also define a more fine-grained framework for the induced subgraph relation. We apply this to obtain a complete complexity classification for Chromatic Sum on $H$-free graphs, as well as for several other problems. We justify the choice of this framework by proving that Chromatic Sum is NP-complete for graphs of clique-width at most $3$. This result complements a known polynomial-time result for graphs of clique-width at most $2$.

0

cs.CC 2026-07-01

n^{γ/(log log n)^2} approx for MIS on twin-width 4 refutes ETH

by Édouard Bonnet, Maël Dumas +1 more

Independent Set Hardness in Graphs of Bounded Twin-Width and Low-Radius Merge-Width

Nearly matches the existing n^{O(1/log log n)} approximation and holds even with a provided 4-sequence.

abstract click to expand

For every $\varepsilon > 0$, Max Independent Set admits a polynomial-time $n^\varepsilon$-approximation algorithm on $n$-vertex graphs of effectively bounded twin-width [Berg\'e et al., STACS '23]. The approximation factor actually obtained is more precisely $n^{O(1/ \log \log n)}$. Prior to the current paper, no approximation hardness was known for this problem, and the existence of a polynomial-time approximation scheme (PTAS) was repeatedly raised as an open question. We answer this question in a strong sense: We show that there is a constant $\gamma > 0$ such that a polynomial-time $n^{\gamma/ (\log \log n)^2}$-approximation algorithm for Max Independent Set on graphs of twin-width at most 4 would refute the Exponential-Time Hypothesis (ETH). This lower bound further holds if a 4-sequence is provided as part of the input. We show the same hardness of approximation for Min Coloring, which also has a nearly matching $n^{O(1/ \log \log n)}$-approximation algorithm on graphs of effectively bounded twin-width. We also clarify the parameterized complexity of $k$-Independent Set on graphs of bounded radius-$r$ merge-width when the range of $r$ is limited. There is a fixed-parameter tractable algorithm for $k$-Independent Set on graphs given with radius-$2^{O(k^2)}$ merge sequences of bounded width [Dreier and Toru\'nczyk, STOC '25]. We complement this result by showing that $k$-Independent Set is W[1]-hard on graphs given with radius-$o(k)$ merge sequences of bounded width. We further show that this result also holds for $k$-Dominating Set.

0

math.CO 2026-07-01

646099441937791106493755218560442089979 labeled posets on 19 points

by Rafael Ayala

The number of labeled partial orders and topologies on 19 points

The 39-digit total extends the OEIS sequence A001035 and supplies the labeled topology count for 19 points.

abstract click to expand

We report the exact value of the number of labeled partially ordered sets (equivalently, labeled $T_0$ topologies) on 19 points, P(19) = 646099441937791106493755218560442089979, a 39-digit integer extending OEIS A001035, whose largest previously computed term was P(18) (Brinkmann and McKay). By the Stirling transform we also obtain the number of labeled topologies on 19 points, A000798(19) = 689054943207246404281592791142107048261. Our route is the Ern\'e-Stege moment reduction, which expresses P(19) through a few sums of antichain counts over the posets on at most 16 points. All of these are available from the posets on at most 15 points (whose number is catalogued, and which standard software generates on demand), except a single moment over the 16-point posets. That moment is obtained not by enumerating the 16-point posets but by inserting a single element into the 15-point ones, with a per-parent kernel that advances the sum at the cost of computing the parent's own antichain count. The result passes several independent checks, among them the residue predicted by the modular periodicity of A001035 and the recovery from the same sweep of the known count P(16) and the Ern\'e-Stege moments G(16,1) and G(16,2). We also report the moments G(16,3) and G(16,4), the latter an input to the analogous computation for 20 points.

0

cs.DS 2026-07-01

Constant-factor approx for distance-2 sets in bounded merge-width graphs

by Maël Dumas

Constant-factor approximation of maximum distance-2 independent set in graphs of bounded merge-width

LP relaxation works when radius-2 merge-width is bounded, but the domination-to-independence ratio grows unbounded at radius-1.

abstract click to expand

We give a constant-factor approximation algorithm for Max Dist-2 Independent Set in graphs of bounded radius-2 merge-width. The same result holds for Min Dominating Set from [Bonamy and Geniet, 2025], [Chan et al., SODA '12]. Both approximation algorithms are LP-based, showing that the domination-to-2-independence ratio is bounded in graphs of bounded radius-2 merge-width. Moreover, this result is tight in the sense that the ratio can be unbounded in graphs of bounded radius-1 merge-width.

0

cs.DS 2026-06-30

Geodetic set is FPT on chordal graphs

by Dibyayan Chakraborty, Sandip Das +3 more

Algorithms and complexity for geodetic sets on interval and chordal graphs

The problem admits f(tree-width) * n^O(1) algorithms on chordal graphs and is NP-hard even when restricted to interval graphs.

abstract click to expand

We study the computational complexity of finding the geodetic number of a graph on chordal graphs and interval graphs. A set $S$ of vertices of a graph $G$ is a \textit{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$. The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. We show that \textsc{Minimum Geodetic Set} is fixed parameter tractable for chordal graphs when parameterized by its \emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$-trees, for fixed $k$. Then, we show that \textsc{Minimum Geodetic Set} is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012), who showed that \textsc{Minimum Geodetic Set} is polynomial-time solvable on proper interval graphs. As interval graphs are very constrained, to prove the latter result, we design a rather sophisticated reduction technique to work around their inherent linear structure.

0

math.CO 2026-06-30

Seymour conjecture holds for out-degree 7 oriented graphs

by Arpan Sadhukhan, R. B. Sandeep +1 more

A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7

Minimum-out-degree threshold raised from 6 to 7 via local reductions and CP-SAT checks on obstructions.

abstract click to expand

We prove Seymour's second neighborhood conjecture on oriented graphs whose minimum out-degree is equal to $7$. This gives, to our knowledge, the first improvement of the minimum out-degree threshold in two decades, since the work of Kaneko and Locke in 2001, who resolved the conjecture for oriented graphs whose minimum out-degree is at most $6$. The proof is partially computer-assisted: after a sequence of local reductions, the remaining finite obstruction models are eliminated by reproducible OR-Tools CP-SAT infeasibility checks.

0

cs.DM 2026-06-30

Representatives branch-and-cut solves convex recoloring fastest

by Boyue Lin, Phablo F. S. Moura +1 more

Convex Recoloring of General Graphs: Formulations, Polyhedra, and Computational Experiments

Tests on benchmarks and new synthetic instances show it outperforms three other MILP formulations for the connected-coloring task.

abstract click to expand

A vertex coloring of a graph is convex if the vertices of each color induce a connected subgraph. In the convex recoloring problem (CR), the goal is to find a convex coloring while minimizing the weight of recolored vertices, i.e., vertices assigned a color different from their original one. This problem was originally motivated by the study of phylogenetic trees in bioinformatics and is NP-hard even on paths. Most existing research focuses on trees, with only limited results available for general graphs. We advance the state of the art by developing exact solution methods for CR on general graphs. In particular, we propose four mixed-integer linear programming formulations, including a compact flow-based model and a representatives model, and design corresponding solution methods. We compare the polytopes associated with the linear relaxation of the proposed formulations. Computational experiments on benchmark instances and on new synthetic instances show that a branch-and-cut algorithm based on the representatives formulation performs best overall.

0

math.CO 2026-06-30

List 3-coloring C4-free diameter-2 graphs runs in polynomial time

by Yukihiro Murakami

List 3-coloring C₄-free graphs of diameter-2 in polynomial-time

Structural proof shows many graphs without universal vertices are not 3-colorable once maximum degree reaches 17.

abstract click to expand

We show that list $3$-coloring a~$C_4$-free graph of diameter-$2$ can be done in polynomial-time. Our algorithm is based on a structural characterization showing that many such graphs are not~$3$-colorable. In particular, we show that~$C_4$-free graphs of diameter-$2$ without universal vertices, where the maximum degree is at least~$17$, are not~$3$-colorable.

0

cs.CC 2026-06-30

Rule class decides if finding period-k attractors is easy or hard

by Alexander Drobyshev, Grigoriy Bokov

Cyclic Attractor Detection in Boolean Network Dynamics under Local Logical Constraints

Post lattice gives full dichotomy for fixed k: majority-like self-dual rules yield NP-completeness, affine rules stay polynomial.

abstract click to expand

Boolean networks are finite discrete nonlinear systems whose long-term behaviour is organised by fixed-point and cyclic attractors. Detecting such recurrent states is important in applications ranging from gene regulation and neural computation to complex-network models, but the computational boundary between tractable and intractable attractor analysis is still not fully understood. We study that boundary from the perspective of local logical rules. We consider Boolean networks under parallel update whose coordinate functions are given by circuits over a fixed finite basis of a closed Boolean-function class, and ask whether the network has a cyclic attractor of prescribed exact period $k$. For every fixed $k\ge 2$, we obtain a complete complexity dichotomy over Post's lattice. The problem is $\mathrm{NP}$-complete whenever the local rule class contains majority-like self-dual rules or one of the two mixed conjunctive-disjunctive monotone families. In all remaining Post classes it is polynomial-time solvable, with affine rules and pure conjunctive or pure disjunctive rules with constants providing the boundary tractable cases. The results show that exact attractor detection is governed not only by the network architecture but also by the logical mechanism of local update: affine and one-sided rules preserve algebraic or order structure, whereas majority-like and mixed monotone rules can encode global Boolean consistency constraints.

0

cs.DM 2026-06-30

Tropical polynomials coordinate multisets of any n points in r dimensions

by Susumu Kubo

Stable complete coordinates for multisets of points via basic r-symmetric tropical polynomials

Binomial(n+r,r) basic r-symmetric ones of degree at most n separate all S_n orbits and form a bi-Lipschitz map.

abstract click to expand

A multiset of $n$ unordered points in $\mathbb{R}^r$ -- a point cloud, or, for $r=2$, a persistence barcode of birth-death pairs -- is a point of the orbit space $\mathbb{R}^{nr}/S_n$ for the symmetric group $S_n$ permuting the rows of an $n \times r$ matrix; a separating family of invariants on this space is exactly a complete set of permutation-independent coordinates. We provide one that is explicit, small, and stable, in the max-plus (tropical) setting: for all $n \geq 1$ and $r \geq 1$, the $\binom{n+r}{r}$ basic $r$-symmetric tropical polynomials, of degree at most $n$, separate the orbits of $S_n$ on $\mathbb{R}^{nr}$. This settles in full a problem left open in [Kubo, J. Pure Appl. Algebra 223 (2019) 72-85], where separation was known only for $r=2$ and special cases of $r \geq 3$, and yields a family far smaller and of lower degree than the general separating sets from Derksen's recent theory of tropical invariants for permutation actions ($nr + (nr)!/n!$ invariants of degree $O(n^2 r^2)$). The proof is elementary and constructive: the basic values are identified with a transportation problem, and the multiset is recovered from the dual by an explicit algorithm. We further show the coordinate map is a bi-Lipschitz embedding for all $n$ and $r$, being an injective max filter bank (via the bi-Lipschitz theory of max filtering), with an explicit Lipschitz constant for the forward bound and a fully explicit, dimension-free distortion when $r=1$. Finally we determine when the pairwise values suffice (exactly $n \leq 3$) and show that invariants on at least three columns and of degree less than $n$ are necessary in general, the obstruction being a standard non-uniqueness configuration from discrete tomography.

0

cs.GT 2026-06-30

Discounted i.i.d

by Jung-Hun Kim, Vianney Perchet

I.i.d. Prophet Inequalities with Discounted Rewards: As Hard as the Non-i.i.d. Case

Even structured multiplicative discounting over phases erases the usual i.i.d. advantage and matches non-i.i.d. hardness.

abstract click to expand

We study prophet inequalities with discounted rewards, where i.i.d. base rewards are multiplicatively discounted over time. Our main message is that even this structured and arbitrarily weak form of nonstationarity can erase the classical advantage of the stationary i.i.d. setting. Focusing on single-quantile threshold policies, we show that the competitive ratio transitions from the classical $1-1/e$ guarantee to a fundamental $1/2$ barrier as discounting accumulates over many phases in a canonical regime with a common-decay factor and equal-length phases. We further show that, in the same regime, the $1/2$ barrier persists even for arbitrary stopping rules. Consequently, i.i.d. base rewards under discounting can be as hard as the fully non-i.i.d. case. On the algorithmic side, we design single-quantile threshold rules that attain the tight bounds by calibrating acceptance decisions to an effective horizon induced by discounting, and we extend this calibration to heterogeneous decay factors and unequal phase lengths. We further show that a similar discontinuous breakdown persists in an infinite-horizon continuous-decay benchmark, where arbitrarily weak decay collapses the stationary benchmark from $1$ to $1/2$.

0

cs.DM 2026-06-30

Triangulations pack at least floor(n/5) three-vertex paths

by Prosenjit Bose, Anil Maheshwari +2 more

3-packings in Triangulations: Algorithms, bounds, and Complexity

The bound holds for any triangulation and is asymptotically tight, while induced edge-isolated-vertex packings reach floor(n/3)-2 via a fast

abstract click to expand

We study $H$-packings in plane triangulations for the three-vertex graphs $H\in\{P_3,K_3,P_2\cup P_1\}$. For a graph $H$, let $\lambda_H(G)$ denote the maximum size of an $H$-packing in $G$, with the convention that for $H=P_2\cup P_1$ the copies are required to be induced. For $P_3$-packings, we prove that every triangulation $G$ on $n$ vertices satisfies $\lambda_{P_3}(G)\ge \left\lfloor \frac n5\right\rfloor$, and show that this lower bound is asymptotically tight. We also study triangle packings in triangulations and provide lower bounds for $\lambda_{K_3}(G)$ in terms of the maximum degree and the degree sequence. We give a face-path characterization of triangle factors in $4$-connected plane triangulations using a hamiltonian cycle and the weak duals of the two associated maximal outerplanar graphs. Finally, for induced packings by $P_2\cup P_1$, we prove that every plane triangulation $T$ on $n$ vertices satisfies $\lambda_{P_2\cup P_1}(T)\ge \left\lfloor \frac n3\right\rfloor-2$, and show that such a packing can be found in polynomial time.

0

math.PR 2026-06-29

Rational function in three variables has no finite-automata factory

by Renato Paes Leme, Jon Schneider

Note on Finite-Automata Bernoulli Factories for Rational Functions

Mossel-Peres equivalence fails for multiple variables; a concrete counterexample admits a general factory but not a finite one.

abstract click to expand

Mossel and Peres (2005) established a comprehensive framework for designing Bernoulli factories. Notably, they demonstrated that a single-variable function admits a finite-automata Bernoulli factory if and only if it is a rational function. Their Theorem 2.9 claims an extension of this result to multivariable functions, but it contains a subtle technical oversight in the application of P\'olya's Theorem. We provide a direct counterexample: a rational function in three variables that admits a general Bernoulli factory but cannot be implemented by a finite-automata Bernoulli factory.

0

math.CO 2026-06-29

Annihilation number bounded by ((Δ+1)/2) times Caro-Wei sum

by Chakshu Gupta

An annihilation-number Caro-Wei bound: a TxGraffiti conjecture and an independence-number bracket

The inequality proves α ≥ (a + R)/Δ for connected graphs except the single edge and places α between R and a within factor (Δ+1)/2.

abstract click to expand

Automated conjecturing programs scan collections of graphs for inequalities between invariants that no stored graph violates, then offer the survivors for proof or refutation. TxGraffiti, one such program, conjectured that every nontrivial connected graph $G$ satisfies $\alpha(G) \ge \bigl(a(G) + R(G)\bigr)/\Delta(G)$, where $\alpha$ is the independence number, $a$ the annihilation number, $R$ the residue, and $\Delta$ the maximum degree. Established only for two special families of graphs, the conjecture has otherwise remained open. The note proves the degree-sequence inequality $a \le \tfrac{\Delta+1}{2}W$, where $W$ is the Caro-Wei sum; the same inequality is known for the independence number in place of $a$. Combined with the classical lower bounds $\alpha \ge R$ and $\alpha \ge W$, it proves the conjecture for every connected graph of maximum degree at least three, and a direct argument settles maximum degree two; the conjecture fails only for the single edge, of maximum degree one. The inequality also brackets the independence number between the polynomial-time quantities $R$ and $a$, within a factor $(\Delta+1)/2$. The conjecture's bound is sharp, with equality attained, for instance, by the complete graph on four vertices.

1 0

0

cs.DM 2026-06-29

Average specification number of threshold functions is at most 2n

by Martin Anthony

Chamber geometry and specification numbers of Boolean threshold functions

Chamber geometry shows the average equals the mean facet count and is therefore linear in the number of variables.

abstract click to expand

The specification number $\sigma_n(f)$ of a Boolean threshold function $f$ on $n$ variables is the least number of points whose $f$-values determine $f$ uniquely among all threshold functions. Its essential points form the unique minimum such set. We develop Zuev's geometric interpretation: the threshold functions are the chambers of a central hyperplane arrangement in the $(n+1)$-dimensional space of weights and thresholds, and the essential points of a function correspond exactly to the facets of its chamber, so the specification number is the chamber's facet number. The lower bound $\sigma_n(f)\ge n+1$ becomes the fact that a pointed full-dimensional cone has at least $n+1$ facets, with equality for simplicial chambers. The average specification number $\overline\sigma_n$ becomes an average facet count. We evaluate this average exactly via the resonance arrangement and bound it through a theorem of Fukuda, Tamura, and Tokuyama, obtaining $\overline\sigma_n\le 2n$; hence $\overline\sigma_n=\Theta(n)$. This settles a question of Gutekunst, M\'esz\'aros, and Petersen. The method also extends to polynomial threshold functions. The same geometry links threshold functions with a threshold zonotope, whose vertices are modified Chow vectors. Its one-skeleton is the one-inclusion graph, and a vertex's degree is the specification number of that function. Finally, we treat the operations of Lozin et al. on functions of minimum specification number. Adding a variable and extending on a variable both take the product of a chamber closure with a half-line, preserving simpliciality. For the symmetric-variables extension we give an exact thresholdness criterion and show that minimum specification number is preserved whenever the extension is a threshold function. We also resolve a question they pose concerning a fourth operation.

0

math.CO 2026-06-29

KKL theorem transfers from links to any simplicial complex

by Max Hopkins

Toward a KKL Theorem for any HDX

Local-to-global method proves the result whenever links satisfy it, plus a weaker version for any expanding complex.

abstract click to expand

The KKL Theorem, a seminal result in boolean function analysis, characterizes the structure of low-influence (non-expanding) functions on the hypercube. While recent years have seen breakthrough results across a variety of areas relying on analogs of the KKL Theorem beyond the cube (e.g., on product spaces, Grassmann graphs), further progress has been inhibited by our poor understanding of the phenomenon across more general domains. Motivated in this context, Bafna, Hopkins, Kaufman, and Lovett (STOC 2022) and Gur, Lifshitz, and Liu (STOC 2022) proved a generalized KKL-type Theorem for spectral high dimensional expanders (HDX). Their results, however, remain highly restricted due to strong quantitative expansion requirements on the underlying complex. In this work, we introduce a simple local-to-global method for analyzing low influence functions on simplicial complexes. Using this method we prove a local-to-global KKL-type Theorem: any simplicial complex whose links satisfy a KKL-Theorem also satisfies such a result globally. Building on Gotlib and Kaufman (RANDOM 2023), we also prove a weaker dimension-dependent KKL-type Theorem for simplicial complexes with any non-trivial (two-sided) expansion. As concrete applications of our framework, we give the first characterization of non-expanding functions on `combinatorial' HDX such as dense clique complexes and a corresponding Kruskal-Katona Theorem, as well as a small-set expansion theorem for the Ramanujan Complexes of Lubotzky, Samuels, and Vishne (EJC '05).

0

math.CO 2026-06-29

Unit disk graphs obey γ at most 16ρ

by Juan Gutiérrez, Kaustav Paul

Improved Domination--Packing Bounds in Claw-Free Cubic Graphs and Unit Disk Graphs

Bridgeless claw-free cubic graphs obey γ at most (7/4)ρ + 5/6, improving prior constants of 32 and 2.

abstract click to expand

Given a graph $G$, the domination number $\gamma(G)$ is the minimum cardinality of a dominating set in $G$, and the packing number $\rho(G)$ is the maximum cardinality of a set of vertices that are pairwise at distance at least $3$. The ratio between these parameters has been widely studied in several graph classes. It is known that $\gamma(G) \le 2\rho(G)$ for claw-free subcubic graphs, up to finitely many exceptions, and that $\gamma(G) \le 32\rho(G)$ for unit disk graphs. In this paper, we improve the latter bound by showing that $\gamma(G) \le 16\rho(G)$ for a unit disk graph $G$. For the former bound, we show that it can be improved in the cubic bridgeless setting; more precisely, every bridgeless claw-free cubic graph $G$ satisfies $\gamma(G) \le \frac{7}{4}\rho(G) + \frac{5}{6}$. These results are not tight. In fact, we give example of an infinite family of bridgeless cubic graphs $G$ with $\gamma(G) = 5\rho(G)/4$ and an infnite family of unit disk graphs $G$ in which $\gamma(G) = 3\rho(G)$.

0

cs.DM 2026-06-29

Optimal Knight Exchange is NP-hard

by Henry Siegel

The Optimal Knight Exchange Puzzle is NP-Hard

A polynomial reduction from connected Knight's Tour shows the shortest-swap version is intractable.

abstract click to expand

This paper explores the hardness of two popular recreational chess puzzles: The Knight's Tour and the Knight Exchange (Swap). The problem of finding a Knight's Tour is known to be NP-hard for any chessboard with holes and constant-time decidable for rectangular chessboards, so a natural direction is to explore the hardness of the problem for intermediate chessboard restrictions. In this paper, we show that Knight's Tour is NP-hard for connected boards. We also give a short polynomial-time reduction between the two problems, showing that the optimality version of Knight Exchange is NP-hard.

0

cs.DM 2026-06-29

Unions of 1D intersecting affine modules learnable with k log(2|x|) + 2k queries

by Eva González, Montserrat Hermo +1 more

Learning Unions of Intersecting Affine Modules in One Dimension with Queries

Equivalence and subset queries identify the minimal representation; membership queries work when a shared element is known.

abstract click to expand

We study the exact learnability of finite unions of intersecting affine modules in one dimension. An affine module is a set of the form $a+\sum_{j=1}^{s}b_j \mathbb{Z}$, where $a,b_1,\ldots,b_s\in\mathbb{N}$. We say that a set definable as a finite union of affine modules is a union of intersecting affine modules if it admits a representation in which all modules have a non-empty intersection. We show that this class is efficiently exactly learnable using equivalence and subset queries. Moreover, subset queries can be replaced with membership queries when a common element is known. Our algorithm requires at most $k\log(2|x_\ell|)+2k$ counterexamples, where $k$ is the number of affine modules in the smallest representation and $x_\ell$ is the largest counterexample. This implies polynomial-time learnability in the binary representation.

0

cs.DM 2026-06-29

Penalty conditions force QUBO local minima to be binary and feasible

by Cheng-Han Huang, Yongliang Sun +3 more

Local Minima in Quadratic-Penalty Relaxations of Binary Linear Programs

Modified quadratic terms for knapsack, TSP and mining problems let gradient descent recover valid solutions without spurious optima.

abstract click to expand

Many combinatorial optimization problems admit quadratic unconstrained binary formulations (QUBO) which can often be relaxed to the box $[0,1]^n$ and optimized using scalable gradient-based methods. However, the resulting non-convex landscape can often contain local optima that are spurious or infeasible. In this paper, we establish sufficient structural conditions on quadratic penalties that rule out these failures, guaranteeing that every local minimizer of the relaxed problem is both binary and feasible. For each problem we study, we examine existing QUBO formulations when available, identify why they fail when they do, and propose alternative relaxed QUBOs that satisfy our conditions. We show for several common combinatorial problems, including open-pit mining, 0--1 knapsack, and traveling salesman formulations, that these constructions allow gradient-based methods such as projected gradient descent and Adam to be safely applied to obtain valid binary solutions. Our results clarify when differentiable optimization is a reliable local solver for quadratic combinatorial objectives.

0

math.CO 2026-06-29

Edge open packing solved in poly time on distance-hereditary graphs

by Sriram Bhyravarapu, Gautam K. Das +1 more

Algorithms for the Maximum Edge Open Packing Problem

Twin-set decomposition yields the algorithm; the result also holds on biconvex bipartite graphs despite NP-hardness on Eulerian bipartite gr

abstract click to expand

Packing problems form a central theme in graph theory, owing to their relevance in modeling conflict-free resource allocation, network design, and communication constraints. Motivated by applications in wireless networks where each device can participate in at most one communication at a time and simultaneous links must avoid interference we consider a generalization of induced matching known as \emph{edge open packing}. Two edges of a graph are said to conflict if a third edge connects one endpoint of each; an \emph{edge open packing set} is a set of edges containing no such conflicting pair. The largest cardinality of such a set is the \emph{edge open packing number} of a graph. In this work, we study the computational complexity of the Maximum Edge Open Packing Problem. We give a polynomial-time algorithm for the problem in \emph{distance-hereditary graphs}, exploiting their canonical decomposition via twin-set interactions. We further show that the problem remains polynomial-time solvable on \emph{biconvex bipartite graphs}, thereby identifying a tractable subclass within bipartite graphs, in contrast to the known NP-hardness of the problem on Eulerian bipartite graphs. Finally, we initiate the parameterized complexity study of the problem and present a fixed-parameter tractable algorithm for \emph{chordal graphs}, parameterized by the clique number $\omega$, running in $O(2^{\omega}\cdot\mathrm{poly}(n))$ time.

0

cs.DM 2026-06-29

Latin rectangles gain reflection symmetry at λ=1 only for powers of two

by Enrico Iurlano, Günther R. Raidl

Pairwise Reflection Symmetry in Generalized Latin Rectangles

The minimal multiplicity works precisely when n is a power of two, with constructions supplied for those sizes and existence proved for larg

abstract click to expand

Many combinatorial designs ask for equal distribution of given symbols across the entries of a matrix. The paramount examples are Latin squares, where each symbol from $\{1,\dots,n\}$ appears once per row and column of an $n\times n$ matrix. Generalized Latin rectangles extend this to $\lambda n \times n$ matrices with repeated symbols under controlled column frequencies. In this more general setting, we examine structural properties of pairwise reflection-symmetry, which requires that, on every pair of columns, each ordered symbol pair $(p,q)$ occurs as often as its reversal $(q,p)$. This order-balance is precisely what makes head-to-head comparisons unbiased, i.e., no symbol gains a systematic advantage from the position it occupies relative to another, a fairness demand arising for instance when scheduling tournaments or laying out comparative trials. Existence of such objects for odd $\lambda$ turns out to be remarkably more subtle than for even $\lambda$. After showing that existence holds also for sufficiently large odd $\lambda$, we initiate the search for the smallest possible value of $\lambda$ in this setting. We obtain the insight that a column multiplicity of $\lambda=1$ can be achieved if and only if $n$ is a power of two. We complement the existence results with a direct product construction and add several further observations on the property. Finally, we propose and evaluate a quadratically constrained integer program to computationally search for these objects. The resulting experiments reveal that many of them possess an underlying group-theoretic structure which, as we conjecture, may even be unavoidable in certain settings.

0

cs.DS 2026-06-29

Planar max-cut algorithm gives upper bounds for toroidal graphs

by Mark Glass, Meir Feder

Maximum Cut Algorithms and Upper Bounds for Planar and Toroidal Graphs

The reduction adapts a 1975 algorithm to negative weights and shows some GSet toroidal solutions are optimal.

abstract click to expand

We demonstrate that the problem of finding the maximum cut of a planar graph with arbitrary weights can be easily mapped to a minimum T-join problem in the absolute dual graph - the dual graph with absolute weights, as opposed to the known mapping to a maximum T-join problem with an empty set in the dual graph. By enabling the use of the shortest paths, this approach allows for the straightforward adaptation of the first efficient Max-Cut algorithm, designed by Hadlock in 1975 for planar graphs with non-negative weights, to handle the general case of planar graphs with arbitrary weights. Furthermore, we prove that applying a planar Max-Cut algorithm to a higher genus graph, such as a toroidal graph, while disregarding its topology, provides an upper bound for its maximum cut. Employing this methodology, we derive upper bounds for the maximum cut across all toroidal graphs within the GSet benchmark. We report that the known maximum cut values for part of those GSet toroidal problems including the three largest instances, which were previously documented in the literature, are the maximum possible because they match their upper bound values. Additionally, we introduce a novel heuristic algorithm for finding Max-Cut of toroidal graphs, which is based on the planar graph algorithm. Applying this algorithm to all seventeen toroidal Max-Cut problems in the GSet benchmark successfully reproduces all the best-known results, and for problem #62, it yields a new, previously unknown best Max-Cut value.

0

math.MG 2026-06-29

ℓ1 sparsifiers for matrices need only O(n/ε² log(1/ε)) rows

by Victor Reis, Thomas Rothvoss

Linear-size ell₁ sparsifiers

The new bound replaces the prior log n factor with log(1/ε) and gives linear-size zonotope approximations.

abstract click to expand

We prove that for any matrix $A \in \mathbb{R}^{m \times n}$ and any $\varepsilon \in (0, 1/2]$ there is a diagonal matrix $D \in \mathbb{R}_{\geq 0}^{m \times m}$ with at most $O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))$ nonzero entries so that \[(1-\varepsilon) \|Ax\|_1 \leq \|DAx\|_1 \leq (1+\varepsilon)\|Ax\|_1 \quad \forall x \in \mathbb{R}^n.\]In particular, for any zonotope $Z \subseteq \mathbb{R}^{n}$ there exists a zonotope $Z' \subseteq \mathbb{R}^{n}$ generated by at most $O(\frac{n}{\varepsilon^2} \log(\frac{1}{\varepsilon}))$ segments so that $(1-\varepsilon) Z \subseteq Z' \subseteq (1+\varepsilon) Z$. Previously, the best known bound was $O(\frac{n}{\varepsilon^2} \log n)$ due to Talagrand (1990).

0

math.NT 2026-06-29

Transversals in (Z/p²Z)² have difference sets of size at least 3p²-p-1

by Mugurel Barcau, Vicenţiu Paşol +1 more

Transversal Difference Numbers in Finite Abelian Quotients

For odd primes p the minimal size is conjectured to be exactly (2p-1)², supported by small-prime checks and polynomial evidence.

abstract click to expand

Given $H\leq G$ finite abelian groups, a transversal $T\subseteq G$ for $G/H$ has fixed size $|G/H|$, but its ambient difference support $D(T)=T-T$ can vary with the embedding of $H$ in $G$. We call $ \delta(G,H)=\min_T |D(T)| $ the transversal difference number of the pair $(G,H)$. This invariant is related to finite abelian factorisation, tiling complements, and small-sumset questions, and is motivated by recent work regarding ambient Galois labels in CRT transforms for cyclotomic-subfield homomorphic encryption. We prove various results regarding this invariant, including a general lower bound $\delta(G,H)\geq 2|G/H|-m(G,H), $ where $m(G,H)$ is the largest order of a subgroup of $G$ disjoint from $H$. The bound is sharp for cyclic quotients, and Kneser's theorem gives a cross-transversal estimate leading to exact product families with one nonsplit cyclic coordinate and arbitrary split factors. These results isolate the first genuinely new residual obstruction, namely the same-prime square plane \[ G=(\mathbb Z/p^2\mathbb Z)^2,\qquad H=pG. \] For odd $p$, this case is the technical core of the paper. Here transversals are graphs of functions $\mathbb F_p^2\to \mathbb F_p^2$, and $D(T)$ decomposes into carry-corrected finite-field derivative images. We conjecture that \[ \delta(G,H)=(2p-1)^2 \] for all odd primes $p$, prove the unconditional lower bound $3p^2-p-1$, and give small-prime, probabilistic, and fixed-polynomial evidence for the conjecture.

0

cs.CG 2026-06-26

Two non-planar drawings suffice to unbend every edge

by Therese Biedl

Unbent collections of non-planar s-grid-drawing

Any graph has two s-grid drawings where each edge is straight in at least one, improving on the three needed for planar cases.

abstract click to expand

In a recent paper, Anti\'{c} et al.~studied collections of planar orthogonal drawings of a graph where every edge is unbent in at least one drawing. This paper generalizes this concept to non-planar drawings, and shows that then two drawings always suffice (for planar drawings three drawings are sometimes needed). The results can also be generalized to $s$-grid drawings for $s\geq 3$.

0

math.CO 2026-06-26

Deciding existence of k totally disjoint diametral paths is NP-complete

by T{i}naz Ekim, Arthur Farley

Totally Disjoint Diametral Paths

The problem is hard in general but admits linear-time and polynomial-time solutions on 2-paths and threshold graphs respectively.

abstract click to expand

In this paper, we study totally disjoint diametral paths in simple connected graphs. A diametral path in a graph is a shortest path that connects two vertices whose mutual distance is equal to the diameter of the graph. Totally disjoint paths are paths that have no vertices in common, including their end vertices. We show that the problem of deciding whether a graph $G$ has $k$ totally disjoint diametral paths is NP-complete. We consider restricted classes of graphs for which the problem of determining the maximum size of a set of totally disjoint diametral paths is readily solved. We then give a linear-time algorithm for a subclass of maximal outerplanar graphs called 2-paths, define a polynomial-time algorithm for threshold graphs, and establish a structural bound for proper interval graphs. Finally, we define classes of extremal graphs with $k$ totally disjoint diametral paths of length $d$ having the fewest possible number of edges.

0

cs.IT 2026-06-26

Reed-Muller codes match write-cost bound in code conversion

by Anina Gruica, Benjamin Jany +1 more

Linear Code Conversion in the Merge Regime: General Bounds and Reed-Muller Constructions

General bounds refined by generalized Hamming weights are attained by the construction for natural parameters and recover prior results in s

abstract click to expand

Erasure codes are a core component of most existing large-scale distributed storage systems, ensuring reliability against node failures. Recent work has shown that adapting code parameters to changing node failure rates can lead to significant storage savings. The default approach is to re-encode the data under a new code, which consumes substantial system resources. Code conversion was introduced to reduce this cost. However, existing work has mainly focused on conversions within specific classes of codes. In this paper, we study scalar linear code conversion in the merge regime for arbitrary linear codes. We derive universal lower bounds on the write and read costs in terms of unchanged and read symbols. The bounds are refined using generalized Hamming weights, which capture support-growth properties of subcodes and can give sharper estimates than minimum-distance-only arguments. We show that the framework recovers known bounds for important special cases and can be strictly stronger when the final code has nontrivial jumps in its generalized Hamming weight hierarchy. We then apply the framework to Reed-Muller codes and construct explicit Reed-Muller convertible codes using the Plotkin decomposition. For a natural Reed-Muller parameter regime, the construction attains the derived write-cost lower bound. For the read cost, the generalized-Hamming-weight analysis is sharp for one initial block, while a gap remains for the other block.

0

math.CO 2026-06-26

Equitable k-colorings counted in poly time for fixed k on bounded clique-width

by Holger Dell, Thore Husfeldt +1 more

Counting equitable k-colorings in graphs of bounded clique-width

Given a clique-width expression the count is polynomial-time computable, with SETH-tight dependence on the width parameter.

abstract click to expand

For a graph $G$, a proper $k$-coloring of $G$ is \emph{equitable} if the sizes of any two color classes differ by at most one. The \textsc{Equitable $k$-Coloring} problem asks, for a given graph $G$ and integer $k$, whether $G$ admits an equitable $k$-coloring. Bodlaender and Fomin showed that it is polynomial-time solvable on graphs of bounded treewidth, while it remains $\NP$-hard on cographs, and thus on graphs of constant clique-width. Fellows et al. showed that the problem becomes $\mathsf{W[1]}$-hard when parameterized by tree-width (and hence clique-width) plus the number of colors~$k$. We first show that, for every fixed $k$, counting equitable $k$-colorings is polynomial-time solvable on graph classes of bounded clique-width, given a clique-width expression. We then show that, under $\mathsf{SETH}$, the dependence on clique-width in this algorithm is essentially optimal. As a consequence, our results provide a fairly tight picture of the complexity of \textsc{Equitable $k$-Coloring} with respect to the combined parameter $k$+clique-width. Second, we refine our clique-width algorithm for the linear setting. We show that there exists an algorithm, given an integer $k\ge 1$ and an $n$-vertex graph $G$ together with a linear $w$-expression constructing $G$, computes the number of equitable $k$-colorings of $G$ in time $\max\{1,2^k-2\}^w\cdot n^{k+O(1)}$. Third, we consider a different structural restriction, namely the class of $P_t$-free graphs. A graph is called $P_t$-free if it does not contain the path on $t$ vertices as an induced subgraph. This is a different setting from bounded clique-width; in particular, already $P_5$-free graphs have unbounded clique-width. Nevertheless, we show that for every $P_t$-free graph $G$, the number of equitable list $3$-colorings of $G$ can be computed in subexponential time.

0

cs.DM 2026-06-26

Pinwheel schedules exist for all densities up to 5/6

by Akitoshi Kawamura

Proof of the Density Threshold Conjecture for Pinwheel Scheduling

Fractional-period reduction collapses the 1993 conjecture to a finite computer check.

abstract click to expand

In the pinwheel scheduling problem, each task $i$ is associated with a positive integer $a_i$ called its period, and we want to (perpetually) schedule one task per day so that each task $i$ is performed at least once every $a_i$ days. An obvious necessary condition for schedulability is that the density, defined as the sum of execution rates $1/a_i$, does not exceed $1$. We prove that all instances with density not exceeding $5/6$ are schedulable, as was conjectured by Chan and Chin in 1993. Like some of the known partial progress towards the conjecture, our proof involves computer search for schedules for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (non-integer) periods in an appropriate way. As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most $1$ is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with approximation ratio $4/3$.

0

cs.CC 2026-06-26

Equivalence links weighted uniform and primal non-uniform crossing gates

by Pablo Concha-Vega, Antonin Loubière +1 more

Non-Uniform and Weighted Crossing Gates in Two-Dimensional Sandpiles

This makes crossings possible in 2D sandpiles that were blocked on uniform grids and shows where the link fails in broader cases.

abstract click to expand

Determining whether predicting two-dimensional sandpiles lies in $\mathbf{NC}$ or is $\mathbf{P}$-complete has been open for decades. Moore and Nilsson proved $\mathbf{P}$-completeness for the three dimensional case by encoding Boolean circuits into sandpiles, but this method fails in two dimension due to the impossibility of crossing gates. In this work, we study the existence of crossing gates on non-uniform and weighted grids. We establish an equivalence between uniform weighted crossing gates and a class of simple non-uniform crossing gates, which we call primal. We also exhibit a crossing gate that inherently requires more than one crossing, rather than a single crossing as in standard constructions. Finally, we show that the equivalence between uniform weighted and primal crossings breaks down in more general settings.

0

cs.FL 2026-06-26

Factorial bound limits Langton's ant in squares

by Kossi Roland Etse

How Long Can the Escaping Ant Be Confined?

Linear upper bounds proven tight for height two and three rectangles via column analysis.

abstract click to expand

Langton's ant is a simple two-dimensional cellular automaton whose long-term behavior exhibits remarkable complexity. While it is known that the ant eventually escapes any finite connected region of the grid, the quantitative aspects of this escape remain poorly understood. In this paper, we study the escaping time of Langton's ant, defined as the maximum number of steps the ant can perform within a finite connected domain before leaving it. We establish general upper bounds on the escaping time as a function of the domain size, and derive improved bounds for rectangular domains. In particular, we obtain a factorial upper bound for square domains via an inductive decomposition argument. We also obtain linear upper bounds for rectangular domains of height two and three via a column-by-column analysis. More generally, for rectangular domains with a fixed height, we establish a polynomial upper bound in the number of columns. These results are complemented by exact values computed through an optimized simulation algorithm that exploits the geometric symmetries of the grid and employs a backtracking branching strategy to avoid exhaustive search over all color configurations. We also provide lower-bound constructions, proving that the linear upper bounds for rectangular domains of heights two and three are asymptotically optimal.

0

cs.DS 2026-06-26

k-core MinRSs enumerated in O((n+m) log n) time

by Kan Shota, Kazuya Haraguchi

Fast Enumeration of Minimal Removable Sets in Monotone Systems with Application to Core Collapse Analysis

The in-dominating seed property reduces enumeration from quadratic to near-linear time for core-collapse analysis.

abstract click to expand

In network vulnerability analysis, it is crucial to evaluate the robustness of $k$-cores against vertex removals. A $k$-core is often fragile since removing a few vertices can trigger a large reduction in the core size, a phenomenon known as core collapse. In this paper, we study the problem of enumerating all minimal removable sets (MinRSs) of a given $k$-core, where a MinRS is a minimal nonempty set of vertices whose removal results in a smaller $k$-core graph. We consider this problem within a general mathematical framework based on monotone systems. We show that, for a monotone system that is given with an underlying graph $G=(V,E)$, all MinRSs of a solution can be enumerated in $O((n+m)n\tau_\omega)$ time, where $n=|V|$, $m=|E|$ and $\tau_\omega$ denotes the computation time of evaluating the monotone function of the system. Furthermore, if the system satisfies the newly defined in-dominating seed property, the complexity drops to $O((n+m) \log n \cdot \tau_\omega)$ time. We prove that standard $k$-cores in undirected graphs satisfy this property, enabling MinRS enumeration in $O((n+m)\log n)$ time, a significant improvement over the baseline. We also extend our framework to enumerate all solutions in a given monotone system. This yields an $O((n+m)\log n)$-delay algorithm for all $k$-core subgraphs, outperforming an algorithm given by [Boley et al., Theoretical Computer Science, 2010]. Our framework is applicable to various $k$-core extensions, including weighted $k$-cores, multi-layer $\boldsymbol{k}$-cores, and $(k,\ell)$-cores.

0

math.CO 2026-06-25

Every planar graph has a conflict-free 4-coloring

by Petr Hliněný, Lukáš Málik

Conflict-Free Coloring Planar Graphs with 4 Colors

The bound is tight and the proof is equivalent in strength to the Four Color Theorem.

abstract click to expand

We efficiently conflict-free color every planar graph with 4 colors. An (open-neighborhood) conflict-free coloring assigns colors to vertices in a way that every vertex v has a neighbor w such that the color of w is distinct from the colors of the other neighbors of v (i.e., the color of w is unique in the open neighborhood of v). A previous best upper bound on the conflict-free chromatic number of planar graphs was 5, and it is known that 4 colors are sometimes necessary. Deciding whether, e.g., a planar graph admits a conflict-free coloring with 3 colors is NP-complete. Our approach uses a refined variant of the classical Gallai-Edmonds decomposition and the Four Color Theorem. In fact, our result is equivalent to the Four Color Theorem.

0

math.CO 2026-06-24

Formulas derived for Betti numbers of generalized split-join graphs

by Bilal Ahmad Rather

Graded Betti numbers of generalized split--join graphs and applications

Decomposition of independence complexes produces explicit expressions for all graded Betti numbers and resolution properties.

abstract click to expand

We determine the full graded Betti tables of graph families that subsume several classes studied recently in the literature, namely the generalized multiple complete split-like graphs and the generalized clique-star graphs with arbitrary clique block sizes. The method combines Hochster's formula with a precise decomposition of the associated independence complexes into disjoint unions of simplices and iterated joins of discrete complexes. This reduces every graded Betti number to an explicit coefficient extraction formula and yields closed expressions for the linear strand, higher strands, Hilbert series, regularity, projective dimension, and extremal Betti numbers. In particular, we prove a sharp criterion for $2$-linear resolution and identify the regularity corner in terms of the number of nontrivial clique blocks. As applications, we recover and extend earlier results on equal-block split-like graphs, obtain complete formulas for pineapple graphs, and derive consequences for power graphs of cyclic groups, elementary abelian groups, and prime-power dihedral groups.

0

math.CO 2026-06-24

Conditions make P3-convexity geometric for oriented graphs

by Júlio Araújo, Mitre C. Dourado +3 more

Convex geometries and directed paths on three vertices

The P3 variant allows polynomial-time checks while P3* is coNP-complete except on acyclic indifference graphs.

abstract click to expand

A convexity space is an ordered pair $(V,\mathcal{C})$, where $V$ is an arbitrary set and $\mathcal{C}$ is a family of subsets of $V$, called convex, which contains $\{\emptyset,V\}$ and is closed under intersections and nested unions of its elements. For any $S\subseteq V$, the convex hull of $S$ is the inclusion-wise minimum convex set $C\in \mathcal{C}$ such that $S\subseteq C$. For a convex set $C\in \mathcal{C}$, an element $p\in C$ is an extreme of $C$ if $p$ does not belong to the convex hull of $C\setminus\{p\}$. A convexity $\mathcal{C}$ defined over $V$ is a convex geometry if any convex set $C\in \mathcal{C}$ is the convex hull of its extreme elements. Given an oriented graph $D = (V,A)$, the family $\mathcal{C}$ of subsets of $V$ is the $\overrightarrow{P_3}$-convexity defined over $D$ if $\mathcal{C}$ is formed by all (convex) sets $C\subseteq V$ such that no vertex $v\in V\setminus C$ is the central vertex of a directed path $P=(u,v,w)$ with $\{u,w\} \subseteq C$, while in the $\overrightarrow{P_3^*}$-convexity defined over $D$, we have that no vertex $v\in V\setminus C$ is the central vertex of a directed path $P=(u,v,w)$ such that $\{u,w\} \subseteq C$ and $(u,w)\notin A$. In this work, we present necessary and sufficient conditions over an oriented graph $D$ so that the $\overrightarrow{P_3}$-convexity over $D$ is geometric, or the $\overrightarrow{P_3^*}$-convexity over $D$ is geometric. While the first case implies a polynomial-time algorithm to decide whether the $\overrightarrow{P_3}$-convexity over $D$ is a geometric, we show that it is coNP-complete to decide whether the $\overrightarrow{P_3^*}$-convexity over $D$ is a convex geometry. We also present a family termed acyclic indifference oriented graphs and demonstrate that deciding whether the $\overrightarrow{P_3^*}$-convexity in this class is geometric can be solved in polynomial-time.

0

cs.DM 2026-06-24

DFS congestion number bounds tree-width by one

by Codaline Bourotte, Gwendal Ducloz +2 more

A Congestion Parameter for Depth-First Graph Traversals

KLX is the min over traversals of max open back edges; the bound TW ≤ KLX + 1 plus MSO2 expressibility gives linear-time checks for each fix

abstract click to expand

We explore a new graph parameter, the KLX number, which quantifies the minimum edge congestion of depth-first search (DFS) traversals of a given graph. Originally motivated by a problem in RNA nanostructure design, this parameter is also of independent theoretical interest. Informally, the KLX number of a graph is defined as the minimum, over all its DFS traversals, of the maximum number of back edges that are simultaneously open during the traversal. We provide full characterisations and linear-time recognition algorithms for graphs with KLX numbers 0, 1 and 2. We also relate KLX to tree-width, proving that any graph satisfies $\mathrm{TW} \le \mathrm{KLX}+1$. Furthermore, we show that the property $\mathrm{KLX} \le k$ is $\mathrm{MSO}_2$-expressible for every fixed $k$. Combined with the tree-width bound, this result implies that determining whether a graph has KLX number at most $k$ can be achieved in linear time for any constant $k$.

0

cs.DM 2026-06-24

Phylogenetic networks from triples built in polynomial time

by Patricia A. Ebert, Anna Lindeberg +1 more

Novel Triple-Based Problems for the Construction of Phylogenetic Networks via Least Common Ancestors

LCA-constraint reduction solves consistency for rooted and anchored triples and constructs the network efficiently

abstract click to expand

Evolutionary histories are often represented by rooted phylogenetic networks, whose leaves correspond to extant taxa and whose internal vertices represent ancestral lineages. Since such histories must usually be inferred from incomplete data, in particular from genomic sequences of present-day taxa, one often obtains only local information about relative evolutionary proximity. For instance, sequence data may suggest that two taxa $x$ and $y$ are more closely related to each other than either is to a third taxon $z$. This information is classically encoded by a rooted triple $xy|z$. In this paper, we study rooted triples in phylogenetic networks under an ancestor-based interpretation: $xy|z$ is displayed if the unique least common ancestor (LCA) of $x$ and $y$ lies strictly below the unique LCA of $x$ and $z$, respectively of $y$ and $z$, and the latter two LCAs coincide. We also introduce anchored triples $\underline{x}y|z$, which retain only the asymmetric comparison that the LCA of $x$ and $y$ lies below the LCA of $x$ and $z$. This relaxation is natural in networks, where different pairwise ancestral relationships need not behave as they do in trees. We consider several variants of consistency problems for ordinary and anchored triples, both with and without forbidden triples. Somewhat surprisingly, these ancestor-based consistency questions for triples in phylogenetic networks do not appear to have been addressed before despite their direct biological interpretation and the fact that such constraints can be inferred naturally from genomic sequence data. By translating these questions into realization problems for required and forbidden LCA-constraints, we show that all resulting problems can be solved in polynomial time. Moreover, whenever a solution exists, a suitable realizing DAG and phylogenetic network can be constructed within the same time bound.

0

math.CO 2026-06-24

Finitely many minimal minor-closed classes exceed any density below 3/2

by Antonios Kominatos, Reem Mahmoud +1 more

Obstructions for Minor-Closed Classes of limiting Densities Below 3/2

The finiteness yields a 2^{poly(n)}-time algorithm that computes the exact limiting density of any minor-closed class given its forbidden mi

abstract click to expand

Given a graph class $\mathcal{G}$, the limiting density of $\mathcal{G}$ is defined as $\delta(\mathcal{G})=\lim_{n\to\infty} \mathsf{ex}(\mathcal{G},n)/n$ where $\mathsf{ex}(\mathcal{G},n)$ is the maximum number of edges of a graph in $\mathcal{G}$ on $n$ vertices. The limiting density $\delta(\mathcal{G})$ is known to be a rational number when $\mathcal{G}$ is a minor-closed graph class. For every $\delta\in[0,\frac{3}{2})$, we prove that the set of $\subseteq$-minimal minor-closed graph classes with densities $>\delta$ is finite and we identify it completely. A consequence of our results is an algorithm that, given a finite set of graphs $\mathcal{Z}$, of total size $n$, either outputs the value of $\delta(\mathsf{excl}(\mathcal{Z}))$ or reports that $\delta(\mathsf{excl}(\mathcal{Z}))\geq \frac{3}{2}$, where $\mathsf{excl}(\mathcal{Z})$ is the class of graphs excluding the graphs in $\mathcal{Z}$ as minors. The algorithm runs in $2^{\mathsf{poly}(n)}$ time.

0

math.CO 2026-06-23

Equal sides uniquely maximize spanning trees in grid products at perfect powers

by Jiechen Zhang

Extremal Spanning Trees in Product Grid Graphs

Pairwise balancing theorems strengthened by heat-trace Schur-concavity give unique maximizers for free and periodic boundaries.

abstract click to expand

We study how fixed-volume spanning-tree extremality changes when product-grid boundary factors are free, periodic, or mixed. In two dimensions, extremality depends sharply on the boundary type. The free/free and periodic/periodic products both obey a closest-to-square principle: among fixed-area rectangles, $P_r\square P_s$ and $C_r\square C_s$ are maximized by the closest-to-square admissible side lengths. The mixed free/periodic cylinder $P_r\square C_s$ is different: closest-to-square fails, and in the divisor-rich case the optimizing cyclic circumference has scale $N^{1/3}$ when the area is $N=rs$. In arbitrary dimension we prove pairwise balancing theorems for pure free products and pure periodic products, and then strengthen them by a heat-trace Schur-concavity theorem in logarithmic side lengths. At perfect-power volume this gives the unique maximizers $P_n^{\square d}$ and, for $n\ge3$, $C_n^{\square d}$. These product-grid comparisons motivate perfect-power conjectures for connected induced lattice subgraphs and periodic analogues.

0

cs.DM 2026-06-23

Poly-time Free Flood-It on 128 jewel-free graph classes

by Martin Darmüntzel, Christian Rosenke +1 more

Flood-It with Jewelry -- Characterizing the Game Complexity for Cograph Generalizations

NP-completeness on thin-spider graphs covers 256 more, fixing complexity for 896 of 1024 cograph generalizations

abstract click to expand

Flood-It is a single-player game played on a precolored graph $G$, where the objective is to make $G$ monochromatic using as few flooding moves as possible. In each move, a color $c$ is selected and all vertices reachable from a fixed pivot vertex via a monochromatic path are recolored with $c$. In the free variant, the pivot may be chosen anew in every move. Deciding whether a graph can be made monochromatic in at most $k$ moves is NP-complete for both variants, fixed and free. This hardness persists even under strong structural restrictions such as split graphs and trees. The Free Flood-It variant is generally considered more difficult than its fixed-pivot counterpart, as it remains hard on several graph classes where the latter becomes tractable, including co-comparability and AT-free graphs. Cographs, that is, $P_4$-free graphs, are among the few classes on which even Free Flood-It is solvable in polynomial time and therefore serve as our starting point. We consider the ten natural one-vertex extensions of $P_4$ -- referred to as jewels -- and study the complexity of both flooding games on the $1024$ graph classes obtained by forbidding subsets of these graphs as induced subgraphs. Our main contribution is a polynomial-time algorithm for Free Flood-It on graphs that are free of the three jewels bull, gem, and $P_5$, covering $128$ of the $1024$ classes. In addition, we prove that both variants remain NP-complete on thin-spider graphs, which exclude the eight jewels banner, co-banner, chair, gem, house, kite, $P_5$, and $C_5$, thereby establishing hardness for $256$ additional classes. Combined with known algorithms and hardness results, our work determines the complexity of both Flood-It variants for $896$ of the $1024$ considered graph classes.

0

math.CO 2026-06-22

Polynomials count low-degree vertices in Miura-ori flip graph

by Chakshu Gupta

Height functions on the m times n Miura-ori flip graph: degree sequence and diameter

Diameter bounds follow from extrema counts and an inequality on 1-Lipschitz height functions on the grid.

abstract click to expand

The state space of an origami crease pattern forms a flip graph, whose vertices are the flat-foldable mountain-valley assignments and whose edges join assignments differing by a single face flip. For the $m \times n$ Miura-ori, the degree sequence and diameter of this graph are known only for two rows. Each assignment maps to an integer height function on the grid, under which a vertex's degree equals its number of local extrema. In this model the vertices of each degree up to five are counted by an explicit polynomial in $m$ and $n$, valid once both exceed a bound that grows with the degree, and the height functions realizing those degrees are described explicitly. A closed-form lower bound for the diameter holds for all $m$ and $n$, and the matching upper bound reduces to an extremal inequality for $1$-Lipschitz functions on the grid, recovering the two-row distance at $m=2$. Since each invariant is read from the extrema or height differences of a grid function, the same reduction applies to any flip-graph quantity expressible in those terms.

0

math.CO 2026-06-22

Lacunary 2D distance graphs need only finitely many colors

by Nabh Singh

Proof of the Finiteness of the Chromatic Number of Two-Dimensional Lacunary Distance Graphs

A matrix theorem supplies a multiplier vector that supports a geometric coloring with a bounded palette.

abstract click to expand

We extend the one-dimensional lonely set method to two dimensions for the purpose of studying the chromatic number of integer distance graphs in two dimensions. Given a lacunary sequence of displacement vectors in $Z^{2}$, we use a lacunary matrix theorem given by Broderick, Fishman and Kleinbock, to prove the existence of a satisfactory multiplier vector. We then give an explicit geometric colouring argument. This proves that any integer distance graph generated by a lacunary sequence of vectors in two dimensions has finite chromatic number.

0

math.CO 2026-06-22

Bounded VC-dimension yields sub-linear twin-width

by Therese Biedl, Taite LaGrange +1 more

The Twin-Width of Graphs of Bounded VC-Dimension

A neighbourhood-partition contraction tool shows twin-width stays below linear once certain induced subgraphs are forbidden.

abstract click to expand

In this paper, we investigate which hereditary classes of graphs admit sub-linear (in the number of vertices) bounds on twin-width. By modifying conference graphs, we can show that split, bipartite, and co-bipartite graphs can all have linear twin-width. However, excluding an induced subgraph of each of these three types is equivalent to the class of graphs having bounded VC-dimension, as shown by Bousquet, Lagoutte, Li, Parreau and Thomass\'e. Graphs of bounded VC-dimension can have unbounded twin-width, but whether it can be linear was an open question. In this paper, we first present a tool for obtaining twin-width bounds in general by contracting a graph based on a partition by distinct neighbourhoods. Then, using this tool, we prove that graphs with bounded VC-dimension have twin-width at most sub-linear. We also obtain a separate, tighter upper bound for the class of interval graphs, as well as a lower bound.

0

cs.DM 2026-06-22

Permutation families of size nearly 4^n can be made setwise distinguishable

by Ishay Haviv

Setwise Distinguishable Permutations

Explicit construction reaches this size, matches the information-theoretic upper bound up to lower-order terms, and tightens kernelization b

abstract click to expand

A family of permutations of $[n]$ is called setwise distinguishable if for every permutation in the family there exists a subset of $[n]$ whose image under this permutation differs from its image under any other permutation in the family. We prove that there exists a setwise distinguishable family of $2^{(2-o(1)) \cdot n}$ permutations of $[n]$. The result is optimal up to the $o(1)$ term in the exponent and is achieved through an explicit construction. As an application, we obtain nearly tight conditional lower bounds on the kernelization complexity of graph coloring problems parameterized by the vertex-deletion distance to split graphs. This improves a result of Jansen and Kratsch (Inf. Comput., 2013).

0

math.CO 2026-06-19

Edge-to-level correspondence solves stair-climbing game on graphs

by Ricky Xiao-Feng Chen

Network pearls climb stairs: a new game on graphs and its optimal solution

The mapping computes the highest level each vertex can reach while meeting the two neighbor-count rules for any a and b.

abstract click to expand

Let $G$ be a graph, and $a$ and $b$ be integers. Suppose there are infinite number of stairs, numbering level $0$, level $1$, etc. How do you place every vertex of the graph $G$ on a level as high as possible such that a vertex placed on level $i$ should have at least $i-b$ neighbors among the vertices placed on level $i$ and above while have at least $i$ neighbors among the vertices placed on level $i-a$ and above? This new game on graphs is referred to as ``network pearls climb stairs". In this paper, we develop a more general theory, notably a correspondence between structure and dynamics, which particularly leads to the optimal solution of the game. Moreover, as $a$ and $b$ vary, the corresponding level numbers for a vertex obviously provide a structural profile (or spectrum) for the vertex the applications of which are worthy of further study.

0

math.CO 2026-06-18

Exchange distance of matroid bases equals polyhedron diameter

by Kolja Knauer, Luis Pedro Montejano

Embracing exchange sequences and oriented matroid polyhedron diameter

Reduction disproves two conjectures and proves 2r^{log_2 r +3} and r-step bounds for Lawrence cases.

abstract click to expand

We reduce the embracing exchange distance of bases of oriented matroids to the metric of oriented matroid polyhedra. This allows us to disprove recent conjectures of Caoduro, Khodamoradi, Paat, and Shepherd and of B\'erczi and N\'ador. On the other hand, we show that any two embracing bases of an oriented matroid of rank $r$ can be transformed into each other in at most $2r^{\log_2(r)+3}$ steps and in at most $r$ steps in a Lawrence oriented matroid, thus confirming the conjecture in this case.

0

cs.LO 2026-06-18

Twin-width boundedness equals expandability by bounded-independence oriented graph

by Hector Buffière, Yuquan Lin +1 more

Monadic dependence from reducts, and applications to twin-width of oriented graphs

The equivalence implies fixed-parameter tractability of first-order model checking on the expanded structures and bounds twin-width for orie

abstract click to expand

We study monadic dependence of binary relational structures including at least one antisymmetric relation. Our cornerstone result gives sufficient conditions for proving that a structure is monadically dependent by only considering some of its reducts, assuming they are structurally well-behaved and compatible enough. As an application, we consider some reorientation rules preserving monadic dependence of binary structures, as well as replacement of one antisymmetric relation with bounded independence number by another. Then, we apply our main (technical) result to the study of twin-width in two ways. First, generalizing the fact that twin-width boundedness is equivalent to being expandable by a linear order into a monadically dependent class, we prove that it is also equivalent to being expandable by an oriented graph with bounded independence number (for instance by a poset with bounded width or by a tournament), and that FO-model checking is fixed-parameter tractable on such an expansion. Second, we show delineation by twin-width for some new classes of oriented graphs, including oriented split graphs and local tournaments. In all these cases, we also obtain fixed-parameter tractability of FO-model checking.

0

math.PR 2026-06-18

Preferential attachment graphs have cliques of size t to power (1-p)/(2-p) over log

by Carlo De Ambroggio, Umberto De Ambroggio

Very large cliques in a scale-free random graph

The bound removes the epsilon loss from earlier work and holds with high probability for any slow diverging log factor.

abstract click to expand

In this short article we consider a preferential attachment random graph model with edge steps, studied by Alves, Ribeiro and Sanchis. Starting with an initial graph $\mathbb{G}_1$ formed by a vertex with a self-loop attached to it, the model evolves as follows. At every subsequent (discrete) time step, either with probability $p$ we add a vertex to the graph and connect it to exactly one of the older vertices selected with probability proportional to its degree, or with probability $1-p$ we add one edge between two existing vertices, both selected (independently) with probability proportional to their degrees. Let $\omega(\mathbb{G})$ be the clique number of a graph $\mathbb{G}$, i.e.\ the number of vertices in a largest complete subgraph of $\mathbb{G}_{}$. Alves, Ribeiro and Sanchis showed that, for any given $\varepsilon>0$, we have $\omega(\mathbb{G}_{2t})\geq t^{\frac{1-p}{2-p}(1-\varepsilon)}$ with high probability (i.e.\ with probability tending to $1$ as $t\rightarrow \infty$). Here we strengthen this bound by showing that, for any function $f:\mathbb{N}\mapsto \mathbb{N}$ that satisfies $f(t)\rightarrow \infty$ as $t\rightarrow \infty$, with high probability \[\omega(\mathbb{G}_{2t}) = \Omega\left(t^{\frac{1-p}{2-p}}\Big(\log^{\frac{1}{2-p}}(t)f(t)\Big)^{-1}\right).\]

0

math.CO 2026-06-18

New metric packs spheres perfectly in Boolean spaces of any dimension

by Tigran Soghomonyan, Zhirayr Margaryan

Perfect Sphere Packing In The Boolean Space

It removes the strict dimensional limits that confined classical Hamming codes to special cases.

abstract click to expand

Perfect sphere packing in the Boolean space is a fundamental and complex problem with significant implications for coding theory, cryptography, and discrete mathematics. The classical solution to the perfect sphere packing problem was provided by Hamming via his well-known perfect codes. However, a major limitation of the traditional Hamming metric is its strict applicability, as it allows perfect partitioning only for spaces with specific, highly constrained dimensions. To address this structural limitation, this article introduces a novel distance metric specifically designed for Boolean hypercubes. The proposed metric modifies the topological properties of the space, making it mathematically viable to partition a Boolean space of any arbitrary dimension into disjoint, perfect spheres. We rigorously define the algebraic properties of this new distance function and demonstrate its consistency across various dimensions. Furthermore, we explore the structural characteristics of the resulting packings. This approach bypasses the classical dimensional constraints of Hamming codes, potentially opening new avenues for designing error-correcting codes and cryptographic primitives in non-traditional dimensions.

0

math.CO 2026-06-17

Uncrowded hypergraphs match shattering threshold

by Abhishek Dhawan, Abhishek Methuku +1 more

The independence number of uncrowded hypergraphs: bounds matching the shattering threshold

Independence number bound reaches optimal constant from CSP geometry for pseudorandom hypergraphs and yields efficient algorithms

abstract click to expand

A foundational theorem of Ajtai, Koml\'os, Pintz, Spencer, and Szemer\'edi asserts that every $n$-vertex $k$-uniform uncrowded hypergraph with maximum degree $\Delta$ contains an independent set of size $c_k n{\left(\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}}$, for some constant $c_k>0$. Determining the optimal leading constant $c_k$ in this bound is a major open problem. A natural target is the so-called shattering-threshold constant $\left(\frac{1}{k-1}\right)^{\frac{1}{k-1}}$, which appears in the solution-space geometry of random constraint satisfaction problems, in average-case complexity theory, and in statistical physics, among other areas. We prove that uncrowded hypergraphs attain this threshold. More precisely, for every $\epsilon>0$ and $k\geq 2$, every $n$-vertex $k$-uniform uncrowded hypergraph of sufficiently large maximum degree $\Delta$ contains an independent set of size at least $(1-\epsilon) n {\left(\frac{1}{k-1}\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}}$. Consequently, we obtain the first pseudorandom class of hypergraphs whose guaranteed independence number matches the shattering threshold, resolving a folklore conjecture. Moreover, as another direct consequence, we resolve a conjecture of Verstra\"ete and Wilson by proving that there exists a constant $c_k=1-o_k(1)$ such that every $n$-vertex $k$-uniform linear hypergraph of maximum degree $\Delta$ has independence number at least $c_k n\left(\frac{\log \Delta}{\Delta}\right)^{\frac{1}{k-1}}$. Our techniques are constructive yielding efficient algorithms for both static and distributed settings. Specifically, we provide an $\tilde O(n\Delta)$-time randomized static algorithm and an $\tilde O(1)$-round randomized $\textsf{LOCAL}$ algorithm to find an independent set in uncrowded hypergraphs at the shattering threshold. These results extend seamlessly to the the setting of linear hypergraphs.

0

cs.DM 2026-06-17

Linear notation defines finite graphs up to isomorphism

by Maxim Nazarov

An alternative way of defining finite graphs

A canonical-form-style string replaces edge lists, easing symmetric drawings and isomorphism checks while carrying colorings and paths.

abstract click to expand

In this paper we introduce "graph linear notation" -- a complete graph invariant -- which is positioned as an alternative definition for the finite graphs. This invariant is constructed using an algorithm similar to the algorithm of finding canonical forms of graphs. Storing graph linear notation instead of a regular graph allows us to greatly simplify two major problems: the construction of illustrations for graphs with regards to possible graph symmetries, and the comparison of two graphs for isomorphism. We also demonstrate the transferability to the graph linear notations such classical graph theory concepts as colourings and graph paths.

0

cs.CG 2026-06-17

Rectangles require at least twice as many piercers as disjoint sets allow

by Deepak Ajwani, Rishikesh Gajjala +2 more

A Counterexample to Wegner's Conjecture for Axis-Parallel Rectangles

Explicit construction yields a triangle-free family with τ at least 2ν, disproving the 1965 bound.

abstract click to expand

In 1965, Wegner conjectured that every finite family $\mathcal R$ of axis-parallel rectangles in the plane satisfies $\tau(\mathcal R) \le 2\nu(\mathcal R)-1$, where $\tau(\mathcal R)$ denotes the minimum number of points needed to pierce all rectangles in $\mathcal R$, and $\nu(\mathcal R)$ denotes the maximum size of a pairwise disjoint subfamily. Over the last six decades, the conjecture has motivated a long line of work: it has been verified for several special classes of rectangle families, and the best known general upper bounds have been progressively improved, but the conjecture itself had remained open. We give an explicit counterexample. More precisely, we construct a triangle-free rectangle-intersection graph on $n$ vertices whose independence number is at most $n/4$. Since the graph is triangle-free, no point of the plane can lie in three rectangles; hence every piercing point hits at most two rectangles. Consequently, $\tau(\mathcal R) \ge n/2 \ge 2\nu(\mathcal R)$, contradicting Wegner's conjectured bound. We also give a slightly more general construction for which $\tau(\mathcal R) \ge 2.21\nu(\mathcal R)$. This shows that the standard point relaxation, equivalently the clique relaxation, for the Maximum Independent Set of Rectangles problem has integrality gap at least $2.21$.

0

math.OC 2026-06-17

Adaptive algorithm approximates parametric problems with negative dependencies

by Levin Nemesch, Stefan Ruzika +2 more

An Adaptive Algorithm for the Approximation of General Linear-Parametric Optimization Problems

Generalizes prior methods to arbitrary parameter sets and shows non-negativity alone does not guarantee approximability.

abstract click to expand

Linear-multi-parametric optimization problems are a widely studied class of optimization problems. The objective function in such a problem is affine linear dependent on a parameter vector, and the goal is to compute a set of solutions that contains an optimal solution for every fixed parameter vector. However, this is known to be computationally challenging: The underlying non-parametric problem might be NP-hard, and, in addition, optimal solution sets might have exponential cardinality. Parametric approximation aims at providing polynomial-time algorithms that overcome these challenges. Instead of computing an optimal solution set, the goal is to compute an approximation set that contains only an approximate solution for every fixed parameter vector. Several new parametric approximation algorithms have been developed in recent literature. However, all of these share a common set of assumptions, which limits the class of parametric optimization problems that can be approximated. Namely, they do not allow negative parameter dependencies and have their parameter sets fixed to the positive orthant. We present a new adaptive approximation (and, also, exact) algorithm that can be applied to a wider class of linear-multi-parametric optimization problems. Our algorithm builds upon existing algorithms from both the fields of parametric and multi-objective optimization and generalizes these algorithms. In addition, we provide structural results for the transformation of parameter sets, and demonstrate that, for linear-multi-parametric maximization problems, the assumption of non-negative optimal objective values over the whole parameter set is not sufficient to ensure approximability.

0

cs.DM 2026-06-16

Decomposition framework bounds clique width in C4-free graph classes

by Cléophée Robin, Alexandre Talon

A program to find families of graphs in Free\{C₄,4K₁\} with bounded clique width

It identifies subclasses of Free{C4, 4K1} with the property and shows unbounded width for supergraphs of 3-clique-coverable graphs.

abstract click to expand

In this paper we study the class of graphs without cycles of size 4 and independent sets of size 4 as induced subgraphs: $\mathop{Free}\{C_4, 4K_1\}$. This is one of the three minimal minimal open cases for the complexity of the colouring problem when restricted to classes defined by excluding induced subgraphs of order 4. We investigate the clique width of some subclasses of $\mathop{Free}\{C_4, 4K_1\}$. We introduce a new framework: the $(k,l,m)$-decomposition and prove that if all the graphs of a class $\cal G$ are $(k,l,m)$-decomposable, then graphs in $\cal G$ have bounded clique width. We give a few examples of such class, found with the help of a program we designed. We also show, for any graph $G \in \mathop{Free}\{C_4, 4K_1\}$ that is 3 cliques coverable, an infinite family in $\mathop{Free}\{C_4, 4K_1\}$ of supergraphs of $G$ which have unbounded clique width.

0

cs.DC 2026-06-16

Local switch rule splits Gaussian network edges into two Hamiltonian cycles

by Bader Albader

A Unified Constant-Time Switch Rule for Constructing Edge-Disjoint Hamiltonian Cycles in Gaussian Networks

One closed-form construction works for every generator and lists the cycles in linear time.

abstract click to expand

Gaussian networks are degree-four symmetric interconnection networks defined over residue classes of Gaussian integers. Earlier work showed that when the generator $\alpha=a+bi$ satisfies $\gcd(a,b)=1$, the real and imaginary dimensions directly form two edge-disjoint Hamiltonian cycles. A later construction extended the result to the non-coprime case $\gcd(a,b)=d>1$, but its proof used long node-sequence tables and separate odd/even cases for $d$. This paper gives a unified closed-form construction that covers both $d=1$ and $d>1$, and also covers both odd and even $d$, without separate case tables. In the rectangular representation with $d$ rows and $r=(a^2+b^2)/d$ columns, the construction uses a constant-time local switch rule for each $q=1,2,\ldots,d-1$ at column $a_q=q-1$. Each switch removes two horizontal edges and inserts two vertical edges. The switched horizontal structure forms the first Hamiltonian cycle, while its edge-complement in the Gaussian network forms the second Hamiltonian cycle. Thus, the full edge set is partitioned into two edge-disjoint Hamiltonian cycles. The construction requires $O(d)$ switch-generation time and $O(N)$ time to list the two cycles, where $N=a^2+b^2$. Exhaustive validation for all $1\leq a\leq b\leq 100$, excluding only the degenerate $N=2$ network, and large-scale validation up to $N=3{,}250{,}000$ confirm the construction.

0

math.CO 2026-06-16

Half the middle layer avoids balanced subfamilies up to size 2k

by Sa'ul A. Blanco

On balanced subfamilies of maximum complement-free families in the middle layer of the Boolean lattice

For any k the construction yields size (1/2) binom(2n,n) with the smallest balanced subfamily exactly at 2k+2 for large n.

abstract click to expand

We study balanced subfamilies of the middle layer $\binom{[2n]}{n}$ of the Boolean lattice $2^{[2n]}$. A family $\mathcal{F}\subseteq\binom{[2n]}{n}$ is said to be balanced if every element in $[2n]$ appears in the same number of members of $\mathcal{F}$. A balanced subfamily of size 2 is exactly a complementary pair $\{A,[2n]\setminus A\}$, and therefore a family with no balanced subfamily of size $2$ has at most $\frac{1}{2}\binom{2n}{n}$ members. We show that for every $k\geq 1$ and all sufficiently large $n$, this maximum size is compatible with delaying the smallest size of a balanced subfamily until $2k+2$. More precisely, there exists a family $\mathcal{F}\subseteq\binom{[2n]}{n}$ of size $\frac{1}{2}\binom{2n}{n}$ with no balanced subfamilies of sizes $2,4,\ldots,2k$, but with a balanced subfamily of size $2k+2$. The proof is constructive and is obtained by lifting Taylor-Zwicker trade-robust magic-square games to self-dual selectors in the middle layer. This proves a recent conjecture of Moss and Pedersen.

0

math.CO 2026-06-15

Saturation number of trees bounded between 1/4 H and 3/2 H

by Chakshu Gupta

Sharp bounds between the saturation number and the harmonic index

Both constants are sharp, allowing the easily computed harmonic index to bound the NP-hard saturation number on trees.

abstract click to expand

The saturation number $\mu^*(G)$ of a graph $G$ is the minimum cardinality of a maximal matching, and $H(G)$ is its harmonic index. TxGraffiti conjectured in 2023 that $\mu^*(G) \le H(G)$ for every nontrivial connected graph $G$, and B{\i}y{\i}ko\u{g}lu refuted this by showing that the ratio $\mu^*(G)/H(G)$ can be made arbitrarily large. Restricting to trees bounds the ratio sharply. Every nontrivial tree $T$ satisfies $\mu^*(T) < \frac{3}{2} H(T)$, with the constant $3/2$ best possible. A complementary bound $H(G) < 4\mu^*(G)$ holds for every graph with an edge, so on a nontrivial tree the saturation number is pinned to $\frac{1}{4} H(T) < \mu^*(T) < \frac{3}{2} H(T)$, both constants best possible. The friendship graph $F_4$ is a smallest counterexample to the conjecture, on nine vertices, and the smallest tree counterexample is the subdivided star on eleven vertices. For each positive integer $m$ a family of graphs with $m$ hubs has ratio approaching $m+1$, while the conjecture holds whenever all vertices have equal degree. Both invariants arise in applications, the harmonic index as a molecular descriptor and the saturation number as a measure of adsorption inefficiency, and the bounds estimate the latter, which is NP-hard to compute, by the former, which is computable in linear time.

0

cs.DM 2026-06-12

Permutation pairs generate complete torus knot list to 8 crossings

by Alexander Omelchenko

Exhaustive Generation of Genus-One Knot and Link Diagrams via Maps on the Torus

Method yields first exhaustive tabulation of more than 33,000 types plus bounds on bigons and bracket span

abstract click to expand

We present an algorithmic framework for the exhaustive generation and tabulation of knot and link diagrams on the thickened torus T^2 x I, based on the theory of maps on surfaces. Cellular 4-regular torus projections are encoded by permutation pairs (alpha, sigma), and unsensed equivalence classes are enumerated completely and without duplication via canonical representatives. Crossing assignments, local diagram-level reductions, and the generalized Kauffman-type bracket are formulated entirely within the same permutation model. The pipeline is validated against published genus-one classifications for crossing numbers N <= 5 and then extended to N = 6, 7, 8, producing, to our knowledge, the first complete genus-one tabulation at these crossing numbers under the stated comparison conventions. The resulting dataset contains more than 33,000 knot and link types. Besides the tables, the computation yields proved structural facts, including a parity statement for the a-span of the bracket and a sharp upper bound N-1 for the number of bigon faces in a 4-regular torus map. It also suggests several conjectures, among them a formula for the maximum number of straight-ahead components, the absence of equi-quadrilateral knot projections, and a 4N upper bound for the genus-one bracket span.

0

cs.DM 2026-06-12

Reversible rule 115 cellular automaton cycles on finite patterns

by Enrico Formenti (Université Côte d'Azur, France) +6 more

The Curious Case of Reversible Elementary Second Order Cellular Automaton 115

The second-order automaton returns every bounded starting state to itself after finite steps, with explicit periods for selected families.

abstract click to expand

We prove that the reversible elementary second order cellular automaton rule 115 is periodic when started on finite initial configurations. We also study some families of finite configurations that have interesting period functions.

0

cs.DM 2026-06-12

Formulas give longest known count of Z-convex polyominoes by area

by Luca Castelli (University of Insubria), Paolo Massazza (University of Insubria)

On the Counting Sequence of Z-convex Polyominoes

Equations implemented in a program extend the enumeration sequence for shapes with convexity degree at most 2.

abstract click to expand

The degree of convexity of a convex polyomino P is the smallest integer k such that any two cells of P can be joined by a monotone path inside P with at most k changes of direction. In this paper, we present a set of formulas and equations that are the basis of a C++ program that allows you to compute the longest counting sequence known to date (with respect to the area) of convex polyominoes of degree of convexity at most 2

0

cs.DM 2026-06-12

Recycling random bits samples k-subsets near entropy limit

by Olivier Bodini (Université Sorbonne Paris-Nord), Francis Durand (Université Sorbonne Paris-Nord)

Entropic Generation of Binary Words

Generates fixed-weight binary words in linear time while using almost the minimum random bits required by information theory.

abstract click to expand

The uniform generation of k Hamming weight binary words, equivalent to sampling k-subsets from n elements, relies on random bits, which can be expensive. We introduce a novel paradigm, random bit recycling, and use it to generate such binary words in linear time while consuming as few random bits as possible. The resulting algorithm is nearly optimal in terms of random bit consumption, meaning that it closely matches the Shannon entropic lower bound coming from information theory.

0

cs.DM 2026-06-12

Formulas give maximum areas of snake polyominoes for heights up to 5

by Alexandre Blondin Massé (LACIM, Université du Québec à Montréal) +2 more

Snake Polyominoes of Maximal Area in a Rectangle

An algorithm lists every chain polyomino in an h by w rectangle and produces closed-form maxima when height is at most 5.

abstract click to expand

Given a discrete rectangle R of dimensions h x w, let W be the set of snake-like polyominoes contained in R represented as binary matrices, i.e. polyominoes whose underlying simple graph is a chain with respect to the 4-adjacency relation. We present an algorithm that generates W for any h and w. Also, let a be the maximal area that can be realized by an element of W. We provide exact formulas of a for h <= 5 and any w.

0

cs.DS 2026-06-12

Linear-time sampler produces random k-coloured Motzkin paths

by Elena Barcucci (University of Florence), Antonio Bernini (University of Florence) +2 more

Random Generation of k-coloured Motzkin Paths

The procedure uses a direct mapping to prefixes ending at odd height to avoid rejection sampling.

abstract click to expand

We study k-coloured Motzkin paths, namely Motzkin paths in which horizontal steps can be coloured in k different ways, and investigate their connection with the number of prefixes ending at odd height from both an analytical and a combinatorial point of view. Moreover, the combinatorial approach provides a random generation algorithm for k-coloured Motzkin paths in linear-time.

0

math.CO 2026-06-12

Every 3-connected 2-outerplanar disc has two CISTs

by Toru Araki

Completely Independent Spanning Trees in k-Outerplanar Triangulated Discs

The trees keep paths between any vertex pair openly disjoint, guaranteeing multiple vertex-disjoint routes in these planar graphs.

abstract click to expand

Let $T_{1}, T_{2}, \dots, T_{k}$ be $k$ spanning trees of a graph $G$. For any pair of vertices $u$ and $v$, if the $u$--$v$ paths in the $k$ spanning trees are pairwise openly disjoint, then the spanning trees are called completely independent spanning trees (CISTs) of $G$. In this paper, we first prove that every 3-connected 2-outerplanar triangulated disc has two completely independent spanning trees. Next, for a 3-connected 3-outerplanar triangulated disc $G$, we provide sufficient conditions for $G$ to have two completely independent spanning trees. We provide an example of a 3-connected 4-outerplanar triangulation that does not have two completely independent spanning trees.

0

cs.DS 2026-06-11

Softmax bias yields expected 1/2-ε matching approximation

by Ahmed M. Alzuhair (1), Ahmed Alherz (1) ((1) Department of Information +5 more

Random Proposals: A Softmax-Based Local-Improvement Framework for Maximum Weighted Matching

Random local improvements converge in O(m log 1/ε) time under mild bias conditions.

abstract click to expand

We propose a randomized local-improvement algorithm for the Maximum Weighted Matching (MWM) problem. Our method introduces a softmax-based biased sampling mechanism that achieves local $\varepsilon$-dominance and yields an expected $\frac{1}{2}-\varepsilon$ approximation ratio. We prove convergence guarantees and show that the algorithm runs in $O\!\left(m\log(1/\varepsilon)/p_{\min}\right)$ time, where $p_{\min}$ is the minimum softmax proposal probability over all edges; under mild conditions on the bias parameter and weight range, this simplifies to $O(m\log(1/\varepsilon))$. The framework provides a tunable tradeoff between convergence speed and approximation quality.

0

cs.DM 2026-06-11

Simplex relaxation complexity is O(log d)

by Simon Keil, Stefan Weltge

The relaxation complexity of the standard simplex is logarithmic

Explicit construction shows O(log d) facets suffice to isolate the standard simplex integer points, matching the lower bound.

abstract click to expand

For a set $X$ of integer points, the relaxation complexity $\operatorname{rc}(X)$ is the smallest number of facets of any polyhedron $P$ such that $P \cap \mathbb{Z}^d = X$. In this paper, we focus on the case where $X$ is the discrete standard simplex $\Delta_d = \{\mathbf{0}, \mathbf{e}_1, \dots, \mathbf{e}_d\}$. We show that $\operatorname{rc}(\Delta_d) = O(\log d)$ by an explicit, elementary construction. This improves upon the previously best-known upper bound $\operatorname{rc}(\Delta_d) = O(d / \sqrt{\log d})$ due to Aprile, Averkov, Di Summa, and Hojny (2024) and matches an asymptotic lower bound by Averkov and Schymura (2022).

0

cs.DM 2026-06-10

Poly-delay enumeration of k edge-disjoint spanning tree tuples

by Rahul CS, MIchal Wlodarczyk

Enumerating tuples of spanning trees

An inductive forest-pack decision tree traversed depth-first outputs every valid set without superpolynomial gaps.

abstract click to expand

Deciding whether a graph has k-edge-disjoint spanning trees is a well-studied problem. We consider the problem of enumerating all sets of spanning trees with polynomial delay. This work is based on the alternate proof of Tutte and Nash-Williams' characterization of graphs with k edge-disjoint spanning trees by Kaiser [1]. The idea is to maintain a decision tree for all forest-packs and perform a Depth-First Search over it. We build this decision tree inductively by computing each node's children using a variant of Kaiser's technique [1].

0