Universality vs Genericity and C₄-free graphs

2021/04/27 by Aristotelis Panagiotopoulos, Katrin Tent, Panagiotopoulos, Aristotelis +1
Computer Science · Mathematics · #03C52 #05C38 #05C75 #Advanced Topology and Set Theory #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2104.13222

openalex publication_date 2021/04/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the existence of a universal structure implies the existence of a generic structure for any approximable class C of countable structures. We also show that the converse is not true. As a consequence, we provide several new examples of weak Fraïssé classes of finite graphs. Finally, we show that the class of all countable C₄-free graphs does not contain a generic structure, strengthening a result of A. Hajnal and J. Pach.

Related

• Universal bridge-free graphs
• Finitely Generated Groups Are Universal
• Universal graphs with a forbidden subgraph: Block path solidity
• Universal-homogeneous structures are generic
• Automorphism Groups of Generic Structures: Extreme Amenability and Amenability