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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra. Graduate Texts in Mathematics, Vol. 78. Springer-Verlag, New York (1981)
Chudnovsky M., Robertson N., Seymour P., Thomas R.: The strong perfect graph theorem. Ann. of Math. 2(164), 51–229 (2006)
Harary F., Holzmann C.: Line graphs and Bipartite graphs. Rev. Soc. Mat. Chile 1, 19–22 (1974)
Ježek J.: The lattice of equational theories. Part I: modular elements. Czech Math. J. 31, 127–152 (1981)
Ježek J.: The lattice of equational theories. Part II: the lattice of full sets of terms. Czech Math. J. 32, 573–603 (1981)
Ježek J.: The lattice of equational theories. Part III: definability and automorphisms. Czech Math. J. 3, 129–164 (1982)
Ježek J.: The lattice of equational theories. Part IV: equational theories of finite algebras. Czech Math. J. 36, 331–341 (1986)
Ježek J., Mckenzie R.: Definability in Substructure Orderings I: finite semilattices. Algebra Univers. 61, 59–75 (2009)
Ježek J., Mckenzie R.: Definability in Substructure Orderings II: finite ordered sets. Order 27, 115–145 (2010)
Ježek J., Mckenzie R.: Definability in substructure orderings III: finite distributive lattices. Algebra Univers. 61, 283–300 (2009)
Ježek J., Mckenzie R.: Definability in substructure orderings IV: finite lattices. Algebra Univers. 61, 301–312 (2009)
Ježek J., Mckenzie R.: Definability in the lattice of equational theories of semigroups, I. Semigroup Forum 46, 199–245 (1993)
Kaddour H.S., Pouzet M., Trotignon N.: Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem. Contrib. Discrete Math. 6(1), 86–97 (2011)
Mal’cev A.I.: Universally axiomatizable subclasses of locally finite classes of models. Sibirsk. Mat. Ž 8(3), 1005–1014 (1967)
McKenzie R.: Definability in lattices of equational theories. Ann. Math. Logic 3, 197–237 (1971)
Schnyder W.: Planar graphs and poset dimension. Order 5, 323–343 (1989)
Stockmeyer P.K.: The falsity of the reconstruction conjecture for tournaments. J. Graph Theory 1(1), 19–25 (1977)
Tarski A., Mostowski A., Robinson R.: Undecidable Theories. North-Holland, Amsterdam (1953)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wires, A. Definability in the Substructure Ordering of Simple Graphs. Ann. Comb. 20, 139–176 (2016). https://doi.org/10.1007/s00026-015-0295-4
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00026-015-0295-4