Skip to content

Add Goemans/DGG cost conjecture — solved by counterexample#1

Merged
mewc merged 22 commits into
mainfrom
add-dgg-goemans-counterexample
Jul 23, 2026
Merged

Add Goemans/DGG cost conjecture — solved by counterexample#1
mewc merged 22 commits into
mainfrom
add-dgg-goemans-counterexample

Conversation

@mewc

@mewc mewc commented Jul 23, 2026

Copy link
Copy Markdown
Owner

Lands the single-source unsplittable-flow cost conjecture (Goemans / Dinitz–Garg–Goemans, Conjecture 1.3) in the registry, marked solved via a finite, exhaustive, exact-integer counterexample.

What's here

  • New problem goemans-unsplittable-flow in lib/problems.ts, stage solved. Precise statement separating the proven congestion theorem (DGG 1999) from the disproved cost strengthening.
  • New solved stage end-to-end: STAGE_LABEL, a distinct blue badge + status-chip (app/globals.css), and a search-rank bonus (components/SearchHome.tsx).
  • Cross-linked references: new ProblemRef type + a §References section on the generic dossier (app/p/[slug]/page.tsx), linking the source writeup, the in-lab verifier, and the 1999 DGG paper.
  • research/dgg-counterexample.ts — exact-integer verifier. Rebuilds x from its path decomposition (feasibility check), enumerates all 8 unsplittable routings, and asserts min congestion-good cost = 60 > 58 = cᵀx. Exhaustive: two s→tᵢ paths per terminal ⇒ no splice hybrids ⇒ 8 routings is the whole universe.
  • research/dgg-goemans.md — campaign log (dead ends kept on the record) + a ready-to-paste jump-in prompt for the open sub-frontiers.
  • .claude/skills/tackle-conjecture — reusable pipeline for landing conjecture results honestly, with this counterexample as the worked template.

The counterexample (verifiable)

7 vertices, a K₄ subdivision (planar, not series-parallel); demands (15,10,15), D=15. Three zero-cost detours down a shared spine are pairwise capacity-incompatible under +D, forcing ≥2 cost-30 direct paths ⇒ every congestion-good routing costs ≥ 60 while the fractional flow costs 58.

bun run research/dgg-counterexample.ts   # *** COUNTEREXAMPLE CONFIRMED ***  60 > 58

Honesty note

The congestion half (the actual DGG theorem) is proven; only the cost strengthening is disproved here. As of Jan-2026 sources the cost conjecture was still listed open, so the status marks this a self-contained, exhaustive certificate pending external audit — not a peer-reviewed theorem.

bun run typecheck and bun run build both pass.

🤖 Generated with Claude Code

Land the single-source unsplittable-flow cost conjecture (Goemans /
Dinitz–Garg–Goemans Conjecture 1.3) in the registry, marked solved via a
finite, exhaustive, exact-integer counterexample.

- New "solved" Stage (badge + status-chip CSS, search-rank bonus, label).
- New ProblemRef type + cross-linked §References section on the dossier.
- research/dgg-counterexample.ts: exact verifier over all 8 routings
  (min congestion-good cost 60 > 58 = cᵀx), confirmed passing.
- research/dgg-goemans.md: campaign log (dead ends + the working construction)
  and a ready-to-paste jump-in prompt for the open sub-frontiers.
- .claude/skills/tackle-conjecture: reusable pipeline for landing a conjecture
  result honestly, with this counterexample as the worked template.

Honest caveat kept on the record: Jan-2026 sources still list the cost
conjecture open, so this is a self-contained certificate pending external audit.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
@vercel

vercel Bot commented Jul 23, 2026

Copy link
Copy Markdown

The latest updates on your projects. Learn more about Vercel for GitHub.

Project Deployment Actions Updated (UTC)
math-lab Ready Ready Preview, Comment Jul 23, 2026 3:22am

mewc and others added 7 commits July 23, 2026 11:44
…cards

- Remove the ".lede" paragraph under the hero headline in SearchHome.
- Add a structured `solution` field (by / when / approach / links) to the
  problem registry; populate it honestly for the Goemans counterexample
  (deep-reasoning campaign, reproduced in-lab; pending-audit caveat kept).
- Render a solved panel on the homepage card showing who solved it, the
  approach, and links to the writeup + in-lab verifier. Card becomes a
  positioned container with a stretched navigation hitbox so the whole card
  still opens the dossier while the external links stay clickable (no nested
  anchors).

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
Replace the top nav bar with a hand-rolled, collapsible, searchable left
sidebar (no shadcn/Tailwind — the repo stays zero-dep; built on the existing
semantic CSS tokens). It lists the whole registry grouped by category with a
type-to-search filter, stage dots, and active-route highlighting; collapses to
an icon rail on desktop and slides over content on mobile. The old .topbar is
removed from every page; per-page cross-links (Collatz ↔ attack log, back to
index) survive as compact breadcrumb rows, and the dossier stage moves to a
crumb chip.

Add a "Submit / feedback" button in the sidebar that opens a math-context-aware
modal (Submit / Correction / Idea / Question). On a dossier it takes that
problem head-on — shown in the header and attached to the payload — and offers a
GitHub PR/issue as the durable path. It POSTs to a new server route
app/api/feedback that relays the note to Slack via chat.postMessage using a
server-only bot token (env SLACK_BOT_TOKEN + SLACK_FEEDBACK_CHANNEL; see
.env.example). This is the app's one server seam — no new deps, plain fetch;
returns 501 until the env is set. CLAUDE.md updated to reflect it.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
Generated via favicontools.com from noto:abacus — favicon.ico, 16/32/48/96
PNGs with light/dark 16px variants, apple-touch-icon, Android/PWA icons.
Wired into App Router metadata.icons/manifest with prefers-color-scheme
media queries; rebranded manifest.json to Math Lab.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
Add attribution in three durable spots: manifest generator field, a
layout comment by the icons metadata, and a README Credits section.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
…feed/theme work included

Pushes the branch so Vercel builds a preview with the Slack env vars
(Preview scope) to verify app/api/feedback end-to-end. Bundles concurrent
work-in-progress from this workspace (SEO routes, news feed, theme controls,
search filter popover) — tree typechecks and builds clean.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
mewc and others added 5 commits July 23, 2026 12:21
- lib/feed.ts: feed derived from problem registry (solves + notes) plus a
  curated layer (ChatGPT DGG solve; X posts get added here). AI/human updates
  to lib/problems.ts flow into the feed automatically.
- app/feed.xml: RSS 2.0 over the same feed.
- components/NewsFeed.tsx: horizontal-scroll card row of 'the latest'.
- components/ThemeControls.tsx: single light<->dark switch; system only sets
  the initial default (via the no-FOUC script in layout).

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
Sitemap validation found the Collatz attack-log page — a real, indexable,
HTTP-200 content page — absent because the generator maps registry entries 1:1
and skipped dossier sub-pages. Add a subPages block. 72 → 73 URLs; all 200, no
redirects, HTTPS-only, XML valid, referenced in robots.txt.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
- New CommandPalette: global ⌘K/Ctrl+K jump list over every problem plus
  nav destinations (Home, Problems by field, Collatz attack log) and actions
  (Submit/feedback, GitHub). Keyboard-driven (↑↓/↵/esc), grouped, stage badges.
- Collapsed rail: widen 60→68px, enlarge icon-buttons (mark/collapse/submit/
  GitHub to 34–40px), add a rail search button that opens the palette (search
  was hidden when collapsed), and drop RSS from the rail to declutter.
- Expanded search gains a ⌘K hint that also opens the palette.
Programmatic-SEO layer over the problem registry:

- Category hubs /problems + /problems/[category] ("open problems in
  <field>") and cross-cutting tag hubs /tags + /tags/[tag], gated to
  tags spanning >=2 problems (singletons would be thin/duplicate).
- Per-problem OG cards (next/og, no new dep) + site-wide fallback;
  math glyphs transliterated so satori needs no build-time font fetch.
- JSON-LD on every dossier (DefinedTerm + BreadcrumbList) and hub
  (ItemList); keyword-led titles via layout template + metadataBase so
  canonicals/OG resolve absolutely.
- Related-problems section wires every dossier into the hub-and-spoke
  graph (kills orphan/thin pages); server-rendered browse nav on the
  homepage gives crawlers real <a>s past the JS-only search.

All derived from lib/problems.ts via lib/seo.ts — hubs, sitemap, and
structured data follow the registry with nothing hand-maintained.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
Concurrent UI/tooling tweaks left in the tree: the filter popover's stage
control becomes chip buttons (matching the category chips), and .gstack/
is gitignored.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
@mewc

mewc commented Jul 23, 2026

Copy link
Copy Markdown
Owner Author

just bundling more in here to one shot init setup to get going

Concurrent cleanup: drop dead lines from the news feed component and the
now-unused feed styles in globals.css.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
mewc and others added 7 commits July 23, 2026 12:41
Prata is a single-weight (400) hairline didone; its thin strokes shimmered on
screen and ignored the 500–700 font-weights the headings already request.
Fraunces is a variable old-style serif with true italic — same editorial feel,
much sturdier strokes, and it honors the intended weights. Renamed the font var
--font-prata → --font-fraunces.
Real shadcn components (per request), layered over the existing hand-rolled CSS:
globals.css imports only Tailwind's theme + utilities layers (no preflight), so
the legacy dossier pages are untouched; @theme inline maps the oklch tokens onto
Tailwind. Base <a> rules moved into @layer base so utilities win in components.

- components/ui/{button,badge,card,popover,switch,checkbox}: shadcn (new-york).
  Button/Badge marked 'use client' (this @radix-ui/react-slot builds createContext
  at module load, which breaks in RSC / the server-rendered feed).
- ThemeControls: single shadcn Switch (light<->dark; system = initial only).
- NewsFeed: horizontal-scroll row of shadcn Cards + Badges.
- SearchHome: funnel filter is now a shadcn Popover (Button + Checkbox chips).
- CLAUDE.md: document the new stack + the news-feed/RSS append convention.

Verified: bun run typecheck + bun run build pass; light/dark render checked.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
Evergreen, high-intent content page for the very common search "I think I
solved [famous problem], now what". A calm, honest 12-step playbook: the base
rate, five-minute sanity checks, computational stress tests (Wolfram Alpha,
OEIS, SageMath/PARI/SymPy in exact arithmetic), building your own
counterexample, adversarial AI review (flaw-finders not judges), the literature
check, formalizing in Lean/Rocq/Isabelle, the classic failure modes, getting
human eyes via MathOverflow, priority/publishing, and submitting to the lab.

- HowTo + FAQPage JSON-LD for AI answer engines / rich results.
- Built on the legacy dossier classes (TOC + chapters) to match the site;
  every external tool link is real; tone is supportive, not mocking, and stays
  on the site's honesty line ("solved" means it survived all of the above).
- Wired into sitemap.ts (priority 0.8) and cross-linked from the Submit modal
  ("Think you've solved one? Read the playbook first").

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
…tes it)

The inline THEME_SCRIPT toggles the `dark` class on <html> before React
hydrates, so the server/client class list differs by design — flag it so React
doesn't warn on every load.
Title-only cards read as unfinished; add back a 4-line-clamped summary and let
the title breathe, with cards stretched to a uniform height in the scroll row.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
The shadcn rebuild reintroduced the per-kind border-l-[3px] accent; remove it
and the now-dead KIND_ACCENT/FeedKind. Cards keep the plain uniform border.
Internal linking so the playbook is reachable (and flows link-equity) beyond
the sitemap:
- Generic dossier template gets a "Think you can crack this one? Read the
  playbook before you announce →" callout under §Status — one edit covers every
  registry problem, and it's suppressed on solved problems.
- Sidebar footer gets a "Solved something? Start here" link.

Co-Authored-By: Claude Opus 4.8 (1M context) <noreply@anthropic.com>
@mewc
mewc merged commit b6fd439 into main Jul 23, 2026
3 checks passed
@mewc
mewc deleted the add-dgg-goemans-counterexample branch July 23, 2026 05:03
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant