Matching works

6 works

cs.CC — Computational Complexity

Which Fine-Grained Lower Bounds Survive the Refutation of 3SUM and APSP?

Contributed by Tejasvi Singh Tomar

Alman and Vassilevska Williams have refuted the 3SUM and APSP hypotheses. Their algorithms rest on counting the triangles through prescribed edges of lopsided tripartite graphs, whose middle part has nεn^{\varepsilon} vertices for a small ε\varepsilon. Majdoddin extended the method to every ε<ln⁡4/(5ln⁡5)≈0.172\varepsilon<\ln4/(5\ln5)\approx0.172. We determine which of the main conditional lower bounds derived from the refuted hypotheses survive. We also prove that the method extends to every ε<0.17843\varepsilon<0.17843 when the prescribed edges are known in advance and there are at most n2−ε/2n^{2-\varepsilon/2} of them, which confirms Majdoddin's numerical estimate. Whether a bound survives depends mostly on the instances that its reduction produces. The reductions behind most bounds produce instances outside the range of the new algorithms: balanced graphs, or lopsided graphs with a larger middle part. Most of the set-disjointness, dynamic-graph and triangle bounds therefore follow from hypotheses that no known algorithm contradicts. These hypotheses, however, concern mainly such instances, and for several bounds the hypothesis is the bound itself, stated for these instances. Their evidence came largely from the refuted hypotheses. A few bounds are false, among them a lower bound of Goldstein, Lewenstein and Porat for Set Disjointness over small universes; the Strong SetDisjointness Conjecture also fails at small polynomial query times. Other bounds have lost their support, such as the Set Disjointness trade-offs of Kopelowitz, Pettie and Porat over small universes apart from constant query time. Finally, we collect the known obstacles to a larger closed-form range with a different base identity and use border-rank lower bounds to exclude several natural candidates.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.23716495

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202623 pages
PDFView work

math.CO — Combinatorics

A thrackle on n vertices has fewer than 4n/3 edges

Contributed by Tejasvi Singh Tomar

A thrackle is a drawing of a graph in the plane in which every two edges meet exactly once, either at a common endpoint or at a proper crossing. Conway conjectured that a thrackle with nn vertices has at most nn edges. We prove that a thrackle with n≥4n\ge4 vertices has at most 43(n−1)\frac43(n-1) edges, improving the bound 1813(n−1)\frac{18}{13}(n-1) obtained by Tóth and, independently, by Scoppetto. The proof combines Xu's discharging argument with two computer searches, by the method of Fulek and Pach, showing that two generalized dumbbells in the sense of Fulek and Pach are not thrackleable: DB(6,8,−1)\mathrm{DB}(6,8,-1) is a 66-cycle and an 88-cycle sharing one edge; DB(6,10,−3)\mathrm{DB}(6,10,-3) is a 66-cycle and a 1010-cycle sharing a path of three edges. A formal proof in Lean 4 derives the bound from five properties of thrackles and checks the computational facts it uses; Section 6 states what this proof trusts.

Author comments: Published on Zenodo: https://doi.org/10.5281/zenodo.24065370

A mix of human-written and AI-generated textHuman understanding: all parts
Nov 12, 202612 pages
PDFView work

cs.CC — Computational Complexity

A Sublinear Treewidth Exponent for Binary Constraint Satisfaction

Contributed by Troy Tri Nguyen

We give a deterministic algorithm for binary constraint satisfaction whose exponent in the input size is sublinear in treewidth on a class of graphs with unbounded treewidth. There are a class G of graphs of bounded maximum degree, a constant c, and a function f such that one algorithm correctly decides every binary CSP instance and, on instances I with primal graph G ∈ G, runs in time f(G) · ||I||^(c · tw(G) / sqrt(log tw(G))) . This contradicts the literal formulation of Conjecture 1.4 of Marx (2010). The algorithm follows from a domain-uniform counting bound: for every fixed maximum degree ∆, complete-table in- stances with k variables and domain size D ≥ 2 can be counted in time LO∆ (1)DO∆ (k/√log k) for sufficiently large k. The constants are independent of D and of the constraint relations. We obtain this bound from the tensor-network recursion of Claude (Anthropic), and use attributed graph foundations from OpenAI to construct the required expander family. Support pruning connects the counting routine to sparse tuple-list inputs without expanding the original domain. The algo- rithm, its native finite-alphabet machine implementation, and the conjecture counterexample are formalized in Lean 4.

Primarily AI-generated textHuman understanding: some parts
Nov 02, 202616 pages
PDFView work

math.CO — Combinatorics

A polynomial algorithm for general d-position in trees

Contributed by Daniel Adam Pyle

A vertex set is in general dd-position if no three of its vertices lie on a shortest path of length at most dd. We give an exact algorithm for an nn-vertex tree in O(n(D+2)4)O(n(D+2)^4) time and O(n(D+2)2)O(n(D+2)^2) space, where D=min⁡{d,n−1}D=\min\{d,n-1\}. In particular, the problem is polynomial-time solvable when the threshold is part of the input. This answers the tree-complexity question posed by Klav\v zar, Rall, and Yero in 2021 and retained in the August 2026 version of the general position survey. The dynamic program uses two truncated distances at each rooted boundary: the nearest selected vertex and the nearest far endpoint of an ancestor-comparable selected pair. These distances characterize every forbidden triple created by joining child subtrees. The algorithm reconstructs an optimal set and extends to signed vertex weights and exact counting of optimal sets. It also computes the full cardinality generating polynomial in O(n2(D+2)4)O(n^2(D+2)^4) coefficient operations. Exhaustive comparisons with direct subset enumeration support the implementation independently of the proof.

Primarily AI-generated textHuman understanding: no parts
Oct 22, 202610 pages
PDFView work

cs.DM — Discrete Mathematics

Fractional DAG treewidth controls DAG treewidth: profile reorientation and VC-dimension rounding

Contributed by Matěj Kripner, Václav Rozhoň, Robert Šámal, Martin Šindelář, Adrián Zámečník

For a nonempty finite graph, let FF be its fractional DAG treewidth, maximized over all acyclic orientations. Its DAG treewidth is at most 160F3ln⁡(16F)160F^3\ln(16F). This answers the boundedness question of Bressan, Lanzinger, and Roth. Reorienting the graph converts shattered source profiles into projective-plane obstructions, which bound their VC dimension by 5F25F^2. Classical epsilon-net rounding then converts fractional bag covers to integral ones without changing the decomposition.

Primarily AI-generated textHuman understanding: some partsDAG treewidthVC dimensionepsilon netsfractional hypertreewidthgraph homomorphisms
Oct 15, 202610 pages
PDFView work

cs.DS — Data Structures and Algorithms

A Lean Certificate for the Single Source Unsplittable Flow Cost Counterexample

Contributed by Arthur, David Barros Hulak, Ruy J. G. B. de Queiroz

We explain a standalone Lean 4 and Mathlib verification of the finite counterexample announced by Dmitry Rybin to the cost-preserving single-source unsplittable-flow conjecture. The instance has seven vertices, nine directed arcs, and three terminal demands. An exact rational path flow saturates every arc, has cost 58, and has largest demand 15. Exhaustive graph-path classification reduces every unsplittable routing to two choices per terminal. Three backbone-arc inequalities force any routing with load at most the fractional load plus 15 to use at least two paid routes, each costing 30. Thus every such routing costs at least 60, ruling out cost preservation even with a non-strict congestion bound. We present the numerical certificate, its graph realization, and the boundary between the pinned proved implementation and its statement-only verification interface. The contribution is an exposition of a source-based formal certificate; no new counterexample, first formalization, or general rounding algorithm is claimed.

Primarily AI-generated textHuman understanding: some partsGoemans cost conjectureLean 4MathlibRybin counterexamplefinite counterexampleformal verificationsingle-source unsplittable flow
Oct 01, 20266 pages
PDFView work

Advanced search

Text
Human understanding
Linked formalizations