{"id":"arxiv/2601.16039","url":"https://arxiv.org/abs/2601.16039","tags":["cs.DM","cs.LO","math.CO","math.LO"],"score":0,"title":"Characterizations of monadically dependent tree-ordered weakly sparse structures","domain":"cs.DM","source":"arxiv","authors":["Hector Buffière","Yuquan Lin","Jaroslav Nešetřil","Patrice Ossona de Mendez","Sebastian Siebertz"],"reviews":0,"subject":"cs.DM","summary":"A class of structures is monadically dependent if one cannot interpret all graphs in colored expansions from the class using a fixed first-order formula. A tree-ordered $σ$-structure is the expansion of a $σ$-structure with a tree-order. A tree-ordered $σ$-structure is weakly sparse if the Gaifman graph of its $σ$-reduct excludes some biclique (of a given fixed size) as a subgraph. Tree-ordered weakly sparse graphs are commonly used as tree-models (for example for classes with bounded shrubdepth, structurally bounded expansion, bounded cliquewidth, or bounded twin-width), motivating their…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-22","reactions":{}}