{"id":"palomar/PALOMAR-2026-11-17-000011","url":"https://github.com/dracoanguis/soumission-linear-spanners/tree/f569fc7a084845d58491cc3752544149109212ff","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-17-000011-v1.json","repo":"https://github.com/dracoanguis/soumission-linear-spanners","tags":["cs.DM","math.CO","msc:05C85","msc:05C40","msc:05C38","msc:68R10"],"score":0,"title":"Temporal cliques admit linear spanners","trust":"high","domain":"cs.DM","source":"palomar","authors":["Ethan Bargaud-Arm"],"reviews":0,"subject":"cs.DM","summary":"Lean 4 / Mathlib formalization of the theorem that every temporal clique on n vertices admits a temporal spanner with at most 7n edges. A temporal clique is the complete graph on a finite vertex set whose edges carry natural-number time labels, locally injective (two edges sharing an endpoint have distinct labels); a temporal spanner is a set of edges in which every vertex reaches every other one by a journey with non-decreasing labels. The result and its proof are due to Júlia Baligács (arXiv:2606.05156, 2026): the dismountability of Carnevale, Casteigts and Corsini (SAND 2025) reduces…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"verified":true,"discussed":0,"published":"2026-11-17","reactions":{},"formalized":true,"formalizes":[{"title":"Temporal Cliques Admit Linear Spanners","identifier":"arXiv:2606.05156","relationship":"formalizes"},{"title":"Dismountability in Temporal Cliques Revisited","identifier":"doi:10.4230/LIPIcs.SAND.2025.6","relationship":"formalizes"},{"title":"How to Reduce Temporal Cliques to Find Sparse Spanners","identifier":"doi:10.4230/LIPIcs.ESA.2024.11","relationship":"formalizes"}]}