2020/10/12 by Abhisekh Sankaran, Sankaran, Abhisekh
Computer Science · Mathematics · #03C13 #03C40 #03C52 #03C75 #05C38 #05C62 #05C76 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.2010.05799
openalex publication_date 2020/10/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider classes of arbitrary (finite or infinite) graphs of bounded shrub-depth, specifically the class TMr, p(d) of p-labeled arbitrary graphs whose underlying unlabeled graphs have tree models of height d and r labels. We show that this class satisfies an extension of the classical Löwenheim-Skolem property into the finite and for MSO. This extension being a generalization of the small model property, we obtain that the graphs of TMr, p(d) are pseudo-finite. In addition, we obtain as consequences entirely new proofs of a number of known results concerning bounded shrub-depth classes (of finite graphs) and TMr, p(d). These include the small model property for MSO with elementary bounds, the classical compactness theorem from model theory over TMr, p(d), and the equivalence of MSO and FO over TMr, p(d) and hence over bounded shrub-depth classes. The proof for the last of these is via an adaptation of the proof of the classical Lindström's theorem characterizing FO over arbitrary structures.