Universality vs genericity and C₄-free graphs

DOI10.1016/J.EJC.2022.103590zbMATH Open1497.05233arXiv2104.13222OpenAlexW3159512109WikidataQ113875488 ScholiaQ113875488MaRDI QIDQ2674563FDOQ2674563

Authors: Aristotelis Panagiotopoulos, Katrin Tent 

Publication date: 14 September 2022

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

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.

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

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

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)

Cites Work

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

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)