{"id":"palomar/PALOMAR-2026-11-06-000015","url":"https://github.com/jtraverso/gale-hoffman-feasibility/tree/fa52c29c24edf7e9afdb487df3764affd43c51c7","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-06-000015-v1.json","repo":"https://github.com/jtraverso/gale-hoffman-feasibility","tags":["math.CO","math.OC","msc:90B10","msc:05C21","msc:05B20","msc:90C35"],"score":0,"title":"Gale's feasibility theorem, the Gale–Ryser theorem and Hoffman's circulation theorem","trust":"high","domain":"math.CO","source":"palomar","authors":["Juan Pablo Traverso Gianini"],"reviews":0,"subject":"math.CO","summary":"A Lean 4 / Mathlib formalization of D. Gale, A theorem on flows in networks (Pacific J. Math. 7, 1957) and of Hoffman's circulation theorem (A. J. Hoffman, 1960, in the form of A. Schrijver, A Course in Combinatorial Optimization, Theorems 4.6 and 4.7). A network is a finite node type N with capacities c : N → N → ℝ, c ≥ 0 (finite capacities only); a flow is f : N → N → ℝ with f x y + f y x = 0 and f ≤ c; a demand d : N → ℝ is feasible if some flow has net inflow ∑_y f y x ≥ d x at every node. feasibility: d is feasible if and only if d(Sᶜ) ≤ c(S, Sᶜ) for every S ⊆ N (Gale's Feasibility…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-06","reactions":{},"formalized":true,"formalizes":[{"title":"A theorem on flows in networks","identifier":"doi:10.2140/pjm.1957.7.1073","relationship":"formalizes"},{"title":"Some recent applications of the theory of linear inequalities to extremal combinatorial analysis","identifier":"doi:10.1090/psapm/010/0114759","relationship":"formalizes"},{"title":"A Course in Combinatorial Optimization","identifier":"","relationship":"formalizes"}]}