Definability in the Substructure Ordering of Simple Graphs |
| |
Authors: | Alexander Wires |
| |
Institution: | 1.School of Economic and Mathematics,Southwestern University of Finance and Economics,Chengdu,P.R. China |
| |
Abstract: | For simple graphs, we investigate and seek to characterize the properties first-order definable by the induced subgraph relation. Let \({\mathcal{P}\mathcal{G}}\) denote the set of finite isomorphism types of simple graphs ordered by the induced subgraph relation. We prove this poset has only one non-identity automorphism co, and for each finite isomorphism type G, the set {G, G co } is definable. Furthermore, we show first-order definability in \({\mathcal{P}\mathcal{G}}\) captures, up to isomorphism, full second-order satisfiability among finite simple graphs. These results can be utilized to explore first-order definability in the closely associated lattice of universal classes. We show that for simple graphs, the lattice of universal classes has only one non-trivial automorphism, the set of finitely generated and finitely axiomatizable universal classes are separately definable, and each such universal subclass is definable up to the unique non-trivial automorphism. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|