{"id":"palomar/PALOMAR-2026-11-20-000001","url":"https://github.com/RBarish-UTokyo/PlanarMaxFlow-WordRAM-Lean4/tree/cfeb331b18ac14bccc38ef44ca640f0dff3f8c0a","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-20-000001-v1.json","repo":"https://github.com/RBarish-UTokyo/PlanarMaxFlow-WordRAM-Lean4","tags":["math.CO","cs.DS","msc:05C10","msc:05C21","msc:05C38","msc:05C70","msc:05C85","msc:68Q25","msc:68W40","msc:90C35"],"score":0,"title":"Flows and shortest paths in plane graphs, with machine programs including the maximum-flow algorithm of Borradaile, Klein, Mozes, Nussbaum and Wulff-Nilsen, in Lean 4","trust":"high","domain":"math.CO","source":"palomar","authors":["Robert D. Barish"],"reviews":0,"subject":"math.CO","summary":"A Lean 4 and Mathlib formalization of maximum flows and shortest paths. Plane graphs are combinatorial maps (darts with a reversal, a tail vertex, a face and a next dart along the face boundary) whose graph and dual are connected and which satisfy Euler's formula V + F = D/2 + 2. The machine statements are about one explicit word RAM (unit cost per instruction, natural registers and memory cells bounded by a word bound W along the run) and fixed encodings of the inputs as lists of natural numbers; each asserts one fixed program for all inputs. Six theorems are compared: (1) the max-flow…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-20","reactions":{},"formalized":true,"formalizes":[{"title":"Maximal flow through a network","identifier":"","relationship":"formalizes"},{"title":"Flow in planar graphs with multiple sources and sinks","identifier":"","relationship":"formalizes"},{"title":"A note on two problems in connexion with graphs","identifier":"","relationship":"formalizes"},{"title":"Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time","identifier":"","relationship":"formalizes"},{"title":"Two theorems in graph theory","identifier":"","relationship":"adapts"}]}