Universal Infinite Clique-Omitting Graphs
Dedicated to the memory of Professor Mahmut Bajraktarević
DOI:
https://doi.org/10.5644/SJM.12.2.02Keywords:
Universal graph, omitting infinite cliques, countable cofinalityAbstract
Dedicated to the memory of Professor Mahmut Bajraktarević
The main result of the paper is that when $\kappa$ is a cardinal of cofinality $\omega$ and $\lambda\ge \kappa$, the class of graphs of size $\lambda$ omitting cliques of size $\kappa$ has no universal element under graph homomorphisms (or the weak and strong embeddings). This theorem only requires ZF.
Downloads
References
Moti Gitik, All uncountable cardinals can be singular, Israel J. Math., 35 (1-2) (1980), 61–88.
Bjarni J´onsson, Universal relational systems, Math. Scand., 4 (1956), 193–208.
Menachem Kojman, On universal graphs without cliques or without large bipartite graphs, Preprint, Research Showcase CMU, 1995.
Peter Komj´ath and Saharon Shelah, Universal graphs with no large cliques, J. Comb. Theory. Ser. B, 63 (1992), 125–135.
L´aszl´o Lov´asz, Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications, American Mathematical Society, Providence, RI, 2012.
