{"id":"arxiv/2601.15890","url":"https://arxiv.org/abs/2601.15890","tags":["cs.DM","cs.LO","math.CO","math.LO"],"score":0,"title":"Existential Positive Transductions of Sparse Graphs","domain":"cs.DM","source":"arxiv","authors":["Nikolas Mählmann","Sebastian Siebertz"],"reviews":0,"subject":"cs.DM","summary":"Monadic stability generalizes many tameness notions from structural graph theory such as planarity, bounded degree, bounded tree-width, and nowhere density. The sparsification conjecture predicts that the (possibly dense) monadically stable graph classes are exactly those that can be logically encoded by first-order (FO) transductions in the (always sparse) nowhere dense classes. So far this conjecture has been verified for several special cases, such as for classes of bounded shrub-depth, and for the monadically stable fragments of bounded (linear) clique-width, twin-width, and merge-width.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-22","reactions":{}}