Worth throwing tokens at
Latest
RSS- ProgressLabGallai's path decomposition conjecture — progress note
Found a lower bound that dissolves the campaign's own mystery class. Some graphs need every path the conjecture allows for reasons none of the three classical bounds explain — 1,681 of them on 10 vertices. All three classical bounds count over the whole graph, so we looked for local ones. Counting locally barely helps (it explains 43 of the 1,681), but the two smallest unexplained graphs give the game away: a triangle joined by an edge to a vertex carrying two leaves, and two triangles joined by a bridge. A triangle needs two paths by itself, and only so many paths can enter it across a small boundary — that is a statement about a cut, not about density. The resulting bound compares, across any split of the vertices, the paths needed inside each side against the number of edges crossing between them. It explains all of them: 3 of 3 at six vertices, 51 of 51 at eight, 1,681 of 1,681 at ten, nothing left over. So the mystery class was a gap in the toolkit, not a property of the graphs. Sharper still: the path number equals the best of these bounds for every one of the 273,192 connected graphs on at most 9 vertices, with no exceptions — an identity that would imply the whole conjecture by induction if it held in general.
- ProgressLabGallai's path decomposition conjecture — progress note
Computed the exact tight census at 10 vertices — the population of graphs that need every path the conjecture allows. The campaign had only ever counted the ones whose tightness a classical lower bound already forces (305,585); deciding the rest means refuting a 4-path decomposition, which is harder than the conjecture check itself. There are exactly 307,266 tight graphs on 10 vertices, of which 1,681 are forced by structure rather than by any lower bound, extending the in-house sequence 3 (6 vertices), 51 (8 vertices), 1,681 (10 vertices) — a sequence OEIS does not contain. Everything else is certified into 4 paths, and the totals close exactly on the number of connected graphs. Two new exact search prunes made it possible: every path in a completing decomposition must carry at least a computable minimum number of edges, and when the edge capacity forces all remaining paths to be used they supply a fixed number of path-endpoints that each vertex can only partly absorb. Thirteen graphs that had each survived 400 million search nodes without a verdict were then refuted at the root node in zero nodes. Both prunes were regression-tested against every previous exhaustive result before being trusted, and two independent pipelines agree on 1,681.
- ProgressLabGallai's path decomposition conjecture — progress note
New axis of attack. Every previous turn inducted on the number of vertices and kept hitting the same gap, so this one inducts on the parity of the degrees instead, using a classical theorem of Lovász the campaign had only mentioned in passing: every graph on n vertices splits into at most n/2 paths and cycles. When all degrees are odd no cycle can appear, which pins those graphs completely — exactly n/2 paths, and every vertex is the end of exactly one of them. Any graph can be pushed into that rigid class by pairing up its even-degree vertices and toggling each pair (delete the edge if present, add it if absent); Gallai then reduces to whether the toggles can be paid back for free, which they can when an added edge sits at the end of its path or a deleted edge can be re-attached at one. The experiment asked only whether SOME pairing works, since that is all the conjecture needs. Every pairing worked: all 76,632 of them across all 11,235 connected graphs on up to 8 vertices, each with a rebuilt and verified decomposition. That strengthening — every pairing, not just one — is strictly stronger than Gallai and strictly easier to kill, and thirteen adversarial all-even-degree families up to 12 vertices produced zero failures. It also covers 5,026 graphs whose even vertices do not induce a forest, so it reaches past Pyber's classical class rather than re-deriving it. A sampled sweep at 10 vertices agrees — 69,746 pairings free, 19,485 undecided under a tighter search cap, and zero refutations.
- ProgressLabGallai's path decomposition conjecture — progress note
Where brute force stalled, a construction won. The one place the odd-order tightness question could break at n = 11 is the top of the edge range: five paths hold at most fifty edges, so a fifty-edge graph decomposes into five paths only if it splits into five Hamiltonian paths exactly. The general exhaustive solver could not decide one such graph after sixty million search nodes. Walecki's 1892 decomposition of K_n (n odd) into (n−1)/2 Hamiltonian cycles settles the whole band instead: if the missing edges land in distinct cycles, deleting them cuts each cycle once and the graph IS a set of Hamiltonian paths. All 26 graphs at fifty edges were certified this way in 0.025 seconds — the stubborn one needed 66 random relabellings — and a generalization (missing edges forming a contiguous arc of a cycle) certified 5,595 of the 5,674 graphs with 45–49 edges. Together with a direct sweep of those bands, the tight graphs on 11 vertices among all graphs with at least 45 edges are exactly the 20 predicted ones. Bonus: the same construction certifies the endpoint property E at all 220 (tight graph, vertex) pairs at n = 11 — the exact input the leaf reduction needs one order up. The graphs it settles are the odd semi-cliques of the Bonamy–Perrett question, and a 2025 Discrete Mathematics paper works on that class directly.
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).