# Sh:492

• Komjáth, P., & Shelah, S. (1995). Universal graphs without large cliques. J. Combin. Theory Ser. B, 63(1), 125–135.
• Abstract:
We give some existence/nonexistence statements on universal graphs, which under GCH give a necessary and sufficient condition for the existence of a universal graph of size \lambda with no K(\kappa), namely, if either \kappa is finite or cf(\kappa)>cf(\lambda). (Here K(\kappa) denotes the complete graph on \kappa vertices.) The special case when \lambda^{<\kappa}=\lambda was first proved by F. Galvin. Next, we investigate the question that if there is no universal K(\kappa)-free graph of size \lambda then how many of these graphs embed all the other. It was known, that if \lambda^{<\lambda}= \lambda (e.g., if \lambda is regular and the GCH holds below \lambda), and \kappa=\omega, then this number is \lambda^+. We show that this holds for every \kappa\leq\lambda of countable cofinality. On the other hand, even for \kappa=\omega_1, and any regular \lambda\geq\omega_1 it is consistent that the GCH holds below \lambda, 2^{\lambda} is as large as we wish, and the above number is either \lambda^+ or 2^{\lambda}, so both extremes can actually occur.
• Version 1993-08-22_10 (9p) published version (11p)
Bib entry
@article{Sh:492,
author = {Komj{\'a}th, P{\'e}ter and Shelah, Saharon},
title = {{Universal graphs without large cliques}},
journal = {J. Combin. Theory Ser. B},
fjournal = {Journal of Combinatorial Theory. Series B},
volume = {63},
number = {1},
year = {1995},
pages = {125--135},
issn = {0095-8956},
mrnumber = {1309360},
mrclass = {05C10},
doi = {10.1006/jctb.1995.1008},
note = {\href{https://arxiv.org/abs/math/9308221}{arXiv: math/9308221}},
arxiv_number = {math/9308221}
}