Sh:492

• Komjáth, P., & Shelah, S. (1995). Universal graphs without large cliques. J. Combin. Theory Ser. B, 63(1), 125–135. arXiv: math/9308221 DOI: 10.1006/jctb.1995.1008 MR: 1309360
• 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)

@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}
}