Definability in the substructure ordering of simple graphs

DOI10.1007/s00026-015-0295-4zbMath1332.05139OpenAlexW2269626665MaRDI QIDQ259729

Alexander Wires

Publication date: 18 March 2016

Published in: Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00026-015-0295-4

zbMATH Keywords

ordered setinduced subgraphsfirst-order definabilityuniversal classes

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (05C99) Model theory of finite structures (03C13)

Related Items

Definability in First Order Theories of Graph Orderings ⋮ The Subtrace Order and Counting First-Order Logic ⋮ Unnamed Item ⋮ Definability in the substructure ordering of finite directed graphs ⋮ Complexity in Young's lattice ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Definability of Recursive Predicates in the Induced Subgraph Order ⋮ Definability in the embeddability ordering of finite directed graphs. II ⋮ The poset of graphs ordered by induced containment

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong perfect graph theorem
• Definability in substructure orderings. II: Finite ordered sets
• Definability in substructure orderings. I: Finite semilattices
• Definability in substructure orderings. IV: Finite lattices
• Definability in substructure orderings. III: Finite distributive lattices
• Planar graphs and poset dimension
• Definability in the lattice of equational theories of semigroups
• Undecidable theories
• The lattice of equational theories. Part II: The lattice of full sets of terms
• Definability in lattices of equational theoris
• The falsity of the reconstruction conjecture for tournaments
• Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem