{"id":"arxiv/2606.05156","url":"https://arxiv.org/abs/2606.05156","tags":["cs.DM","math.CO"],"score":0,"title":"Temporal Cliques Admit Linear Spanners","domain":"cs.DM","source":"arxiv","authors":["Julia Baligacs"],"reviews":0,"subject":"cs.DM","summary":"A temporal graph is a graph in which every edge carries a non-empty set of time labels, and it is temporally connected if for every two vertices $u$ and $v$, there exists a $u$-$v$-path with non-decreasing time labels. A spanner is a subset of its edges preserving temporal connectivity. Unlike static graphs, temporally connected graphs need not admit sparse spanners; nonetheless, minimizing spanner size is a central and widely studied problem. A particularly intriguing question is whether temporal cliques admit spanners of linear size. Despite considerable effort over the past years, the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-03","reactions":{}}