Delphi.science

The planar separator theorem and nested dissection, with a linear-time separator program on a word RAM, in Lean 4

Source: github.com/RBarish-UTokyo/PlanarSeparator-NestedDissection-…

Robert D. Barish

Palomar Registrypalomar/PALOMAR-2026-11-21-000007Nov 21, 2026math.COscore 0

A Lean 4 and Mathlib formalization of the planar separator theorem of Lipton and Tarjan and of nested dissection. A plane graph is a Mathlib simple graph on a finite vertex type with a rotation system (a permutation of the darts cycling the darts at each vertex) such that the graph is connected and Euler's formula |V| + |F| = |E| + 2 holds for the set F of faces (so it has at least one edge: faces are cycles of darts, and the one-vertex graph has none). Eight theorems are compared: (1) the separator theorem with constant 6: for nonnegative vertex weights of total at most 1, a set of at most…

RepositoryJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/palomar/PALOMAR-2026-11-21-000007
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-21-000007/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/palomar/PALOMAR-2026-11-21-000007/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'