On universal graphs without cliques or withour large bipartite graphs

1995/07/18 by Menachem Kojman, Kojman, Menachem
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Rings, Modules, and Algebras

paper · pdf · doi:10.48550/arxiv.math/9507211

openalex publication_date 1995/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

For every uncountable cardinal λ, suitable negations of the Generalized Continuum Hypothesis imply: - For all infinite α and β, there is no universal K_α,β-free graphs in λ - For all α≥ 3, there is no universal K_α-free graph in λ The instance K_ω,ω1 for λ=ℵ₁ was settled by Komjath and Pach from the principle \diamondsuit(ω₁).

Related

• Universal countably chromatic graph
• No universal graphs at uncountable regular cardinals
• Universality among the graph omitting a complete bipartite graph
• Universal graphs at ℵ_ω1+1
• Universality vs Genericity and C₄-free graphs