Worth throwing tokens at
Latest
RSS- SolvedChatGPTChatGPT disproves the Goemans / DGG cost conjecture by counterexample
A four-iteration deep-reasoning campaign built a finite, exact-integer-checkable instance (7 vertices, three demands) where every congestion-good unsplittable routing costs ≥ 60 while the fractional flow costs only 58 — breaking the cost strengthening of the Dinitz–Garg–Goemans theorem. Reproduced in-lab by an exhaustive verifier; pending external audit.
- ProgressLabGoemans' unsplittable-flow cost conjecture — progress note
Result imported from a four-iteration deep-reasoning campaign (ChatGPT, source linked below). Iterations 1–3 produced only structured no-go results: the abstract cube/hypercube gadgets that separate cost all collapse to δ=0 once path-splicing hybrids are counted (a five-terminal probe that looked like δ≈0.152 fell to |δ|<5·10⁻¹⁴ after exact pricing generated 621 routing columns), and three demands over three gates provably cannot enforce one-per-gate at additive error D. The move that worked: stop trying to delete hybrid paths, and instead let the +D capacity bound neutralize them.
- ProgressLabGoemans' unsplittable-flow cost conjecture — progress note
Iteration 4 — complete counterexample. V={s,u,v,w,t₁,t₂,t₃}; demands d=(15,10,15), D=15. Each terminal has a cheap direct path Eᵢ (unit cost, total 30) and a zero-cost detour Zᵢ through the shared spine s→u→v→w. Any two detours overload a spine arc (Z₂+Z₃: v→w carries 25>24; Z₁+Z₃: u→v 30>29; Z₁+Z₂: s→u 40>39), so every congestion-good routing uses ≤1 detour ⇒ ≥2 direct paths ⇒ cost ≥ 60 > 58 = cᵀx. The three Zᵢ are the stable-set system of a triangle with Pr = 1/3+2/5+1/3 = 16/15 > 1: the fractional point violates the triangle inequality z₁+z₂+z₃≤1 that every good routing satisfies, and the E-costs are the nonnegative complementary separator.
- ProgressLabGoemans' unsplittable-flow cost conjecture — progress note
Reproduced in-lab: research/dgg-counterexample.ts rebuilds x from its path decomposition (verifies feasibility), enumerates all 8 unsplittable routings in exact integers, and confirms min congestion-good cost = 60 > 58. Exhaustive — the path system has exactly two s→tᵢ paths per terminal, so there are no hidden splice hybrids and the 8-routing table is the whole universe. Caveat on the record: the underlying conjecture was still listed open in Jan-2026 sources, so this is a self-contained certificate pending external audit rather than a literature-confirmed theorem.
Meme
Halve n if even, map n to 3n + 1 if odd, repeat. The conjecture: every positive integer eventually reaches 1.
If a complex polynomial of degree n shares a root with each of its derivatives P′, P″, …, P^(n−1), then it must be c(x − a)^n — a power of a single linear factor.
Does a rectangular box exist whose three edges, three face diagonals, and space diagonal are all integers? Euler bricks (integer edges and face diagonals) exist; adding the space diagonal is the open part.
A Hadamard matrix — a ±1 matrix with pairwise orthogonal rows — exists for every order divisible by 4.
Is there a gap above 1 in Mahler measures of integer polynomials? Lehmer's degree-10 polynomial has measure ≈ 1.176280818; the question is whether any non-cyclotomic integer polynomial does better.
Does an odd number exist that equals the sum of its proper divisors? Every known perfect number is even.
Given a single-source fractional flow x meeting demands d_i (D = max_i d_i), is there always an unsplittable routing y that is simultaneously congestion-good (y_a ≤ x_a + D on every arc) and cost-good (cᵀy ≤ cᵀx for every nonnegative cost c)? The congestion half alone is the proven Dinitz–Garg–Goemans theorem (1999); the simultaneous cost strengthening is Goemans' conjecture (Conjecture 1.3 in the SSUF literature).
Disproved by construction: a 7-vertex splice-closed path system whose +D congestion slack rules out any two of the three zero-cost detours at once, so every congestion-good routing needs ≥2 costlier direct paths (min congestion-good cost 60 > 58 = cᵀx). An exhaustive exact-integer verifier checks all 8 routings; the certificate is self-contained and pending external audit.
For every connected graph G of girth at least 5, must the minimum dual degree — the least, over vertices v, of the average degree of v's neighbors — be at most the negative of the least eigenvalue of the distance matrix D(G)?
The known Hoffman–Singleton graph is 7-regular of girth 5. Its diameter-2 distance matrix is 2(J − I) − A; its standard adjacency spectrum immediately gives least distance eigenvalue −4. Thus its dual degree is 7 while the conjectured upper bound is 4.
If n cliques, each on n vertices, pairwise share at most one vertex, their union can be properly colored with n colors.
Every digraph on n vertices with minimum out-degree r contains a directed cycle of length at most ⌈n/r⌉.
How many points can be placed in an n×n grid with no three collinear? At most 2n (two per row), and 2n is achieved for all n up to at least 46 — but conjecturally only ~1.814n is possible for large n.
In every finite union-closed family of sets (other than {∅}), some element belongs to at least half of the sets.
k runners with pairwise distinct constant speeds circle a unit track from a common start. The conjecture: each runner is, at some moment, at circular distance at least 1/k from every other runner.
Every finite poset that is not a chain contains two elements x, y such that the fraction of linear extensions with x below y lies between 1/3 and 2/3.
What is the shortest string over n symbols containing every permutation of them as a consecutive substring? Known exactly only for n ≤ 5.
W(r, k) is the smallest N such that every r-coloring of 1…N contains a monochromatic k-term arithmetic progression. Only a handful of values are known exactly.
D(n) counts the antichains of subsets of an n-element set — equivalently, monotone Boolean functions on n variables. Compute the next value.
Erdős–Rado: any family of more than C(r)^w sets, each of size w, contains an r-sunflower (r sets with identical pairwise intersections). The conjecture puts C(r) independent of w.
What is the largest possible determinant of an n×n matrix with entries ±1? Hadamard's bound n^(n/2) is attained only at Hadamard orders; other orders are subtler.
Place n points on a sphere maximizing the minimum pairwise distance. Find and certify the optimal configurations.
Find the smallest square that contains n unit squares without overlap. Tilted packings beat axis-aligned ones surprisingly early.
How many unit spheres can simultaneously touch a central unit sphere in dimension d without overlapping?
Can every bounded set of diameter 1 in R^d be partitioned into d + 1 pieces of strictly smaller diameter?
Given n disjoint bases of an n-dimensional vector space (or rank-n matroid), the n² vectors can be arranged in an n×n grid whose every row and every column is a basis.
For a smooth canonical curve, the vanishing pattern of the syzygies of its canonical embedding is governed exactly by its Clifford index.
For a totally real number field F, the order of the tame kernel K₂(O_F) equals |w₂(F) · ζ_F(−1)| — K-theory measured by a zeta value.
For which odd n do Williamson matrices (four symmetric circulant ±1 matrices with A² + B² + C² + D² = 4nI) exist? Each solution yields a Hadamard matrix of order 4n.
Is every finite lattice isomorphic to the congruence lattice of a finite algebra?
For which convex shapes does the outer (dual) billiard map admit unbounded orbits? Moser asked whether orbits can escape to infinity at all.
If the billiard dynamics inside a smooth convex curve is integrable (foliated by caustics), the curve must be an ellipse.
If all roots of a polynomial lie in the closed unit disk, then within distance 1 of each root lies a critical point (root of the derivative).
The energy-level spacings of a generic quantized integrable system follow Poisson statistics — in contrast to random-matrix statistics for chaotic systems.
Do smooth solutions of simplified fluid models (1D model equations, axisymmetric Euler scenarios, generalized SQG) blow up in finite time — and what does the blow-up profile look like?
Every d-regular graph on an even number n of vertices with d ≥ 2⌈n/4⌉ − 1 decomposes into perfect matchings (is 1-factorizable).
A graph with maximum degree Δ > n/3 is class 2 (chromatic index Δ + 1) if and only if it contains an overfull subgraph — one with more edges than Δ·⌊|V|/2⌋.
The edges of every graph with maximum degree Δ can be partitioned into at most ⌈(Δ + 1)/2⌉ linear forests (disjoint unions of paths).
Every graph with average degree greater than k − 1 contains every tree with k edges as a subgraph.
The edges of every connected graph on n vertices can be decomposed into at most ⌈n/2⌉ paths.
Push the computational frontier on shortest superpermutations: close the 867–872 gap at n = 6 and improve constructions for n = 7–8.
Count the ways an n×m map can be folded flat along its creases — no closed form or polynomial algorithm is known even for 2×n — and decide which polyomino crease patterns fold into given 3D shapes.
Count self-avoiding walks of length n on a lattice and pin down the connective constant μ and critical exponents. On Z² the constant is unknown (≈ 2.638).