Universality vs genericity and C₄-free graphs

DOI10.1016/J.EJC.2022.103590MaRDI QIDQ2674563zbMATH OpenOpenAlexWikidataFDO

Authors Aristotelis Panagiotopoulos, Katrin Tent

Publication date 14 September 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2104.13222

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Categoricity and completeness of theories (03C35) Model theory of denumerable and separable structures (03C15) Models of other mathematical theories (03C65)

Abstract: We show that the existence of a universal structure implies the existence of a generic structure for any approximable class $mathcalC$ of countable structures. We also show that the converse is not true. As a consequence, we provide several new examples of weak Fra"iss'e classes of finite graphs. Finally, we show that the class of all countable $C_4$-free graphs does not contain a generic structure, strengthening a result of A. Hajnal and J. Pach.

Recommendations

• There is no universal countable pentagon‐free graph
• Universal graphs with a forbidden near‐path or 2‐bouquet
• Some remarks on universal graphs
• Universal arrow-free graphs
• Some remarks on universal graphs

Cites work

• scientific article; zbMATH DE number 3902684 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• A course in model theory
• Bowtie-free graphs have a Ramsey lift
• Coherent extension of partial automorphisms, free amalgamation and automorphism groups
• Countable Ultrahomogeneous Undirected Graphs
• Examples of weak amalgamation classes
• Games with finitely generated structures
• Generic expansions of ω-categorical structures and semantics of generalized quantifiers
• Geodetic graphs of diameter two
• On strongly regular graphs with \(\mu =1\)
• Some remarks on universal graphs
• Some remarks on universal graphs
• Some universal graphs
• There is no universal countable pentagon‐free graph
• Turbulence, amalgamation, and generic automorphisms of homogeneous structures
• Universal elements and the complexity of certain classes of infinite graphs
• Universal graphs and universal functions
• Universal graphs with a forbidden near‐path or 2‐bouquet
• Universal graphs with forbidden subgraphs and algebraic closure
• Weak saturation and weak amalgamation property

Cited in

(6)

• Metrically universal generic structures in free amalgamation classes
• Homogeneous isosceles-free spaces
• A Universal Structure for N -Free Graphs
• Games with finitely generated structures
• From Ramsey degrees to Ramsey expansions via weak amalgamation
• The weak Ramsey property and extreme amenability

This page was built for publication: Universality vs genericity and \(C_4\)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2674563)