Pseudo-finiteness of arbitrary graphs of bounded shrub-depth

2022/02/13 by Abhisekh Sankaran, Sankaran, Abhisekh
Computer Science · Mathematics · #03C13 #03C20 #03C40 #03C52 #03C68 #05C05 #05C63 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Logic in Computer Science (cs.LO)

paper · pdf · doi:10.48550/arxiv.2202.06308

openalex publication_date 2022/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the classes TM_r(d) of arbitrary graphs that have tree models of height d and r labels. We show that the graphs of TM_r(d) are MSO-pseudo-finite relative to the class TM^f_r(d) of finite graphs of TM_r(d); that is, that every MSO sentence true in a graph of TM_r(d) is also true in a graph of TM^f_r(d). We also show that TM_r(d) is closed under ultraproducts and ultraroots. These results have two consequences. The first is that the index of the MSO[m]-equivalence relation on graphs of TM_r(d) is bounded by a (d+1)-fold exponential in m. The second is that TM_r(d) is exactly the class of all graphs that are MSO-pseudo-finite relative to TM^f_r(d).

Related

• Some classical model theoretic aspects of bounded shrub-depth classes
• Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO
• Pseudofiniteness and measurability of the everywhere infinite forest
• Transducing paths in graph classes with unbounded shrubdepth
• Modeling Limits in Hereditary Classes: Reduction and Application to Trees