Universal Infinite Clique-Omitting Graphs: Dedicated to the memory of Professor Mahmut Bajraktarević

Mirna Džamonja

doi:10.5644/SJM.12.2.02

Authors

Mirna Džamonja School of Mathematics, University of East Anglia, Norwich, UK

DOI:

https://doi.org/10.5644/SJM.12.2.02

Keywords:

Universal graph, omitting infinite cliques, countable cofinality

Abstract

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.

Statistics

Abstract: 37 / PDF: 9

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.