# Title:Universal graphs without large cliques

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 <= lambda of countable cofinality. On the other hand, even for kappa = omega_1, and any regular lambda >= 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.
 Subjects: Logic (math.LO) Journal reference: J. Combin. Theory Ser. B 63 (1995), 125--135 Report number: Shelah [KoSh:492] Cite as: arXiv:math/9308221 [math.LO] (or arXiv:math/9308221v1 [math.LO] for this version)

## Submission history

From: Shelah Office [view email]
[v1] Sun, 15 Aug 1993 00:00:00 UTC (11 KB)
{"ft_lang_label":"__label__en","ft_lang_prob":0.8334019,"math_prob":0.9247463,"size":1324,"snap":"2020-10-2020-16","text_gpt3_token_len":333,"char_repetition_ratio":0.1310606,"word_repetition_ratio":0.037558686,"special_character_ratio":0.26510575,"punctuation_ratio":0.12878788,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9857118,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-04-02T21:55:52Z\",\"WARC-Record-ID\":\"<urn:uuid:51873464-b6cd-4786-b051-75da57981b14>\",\"Content-Length\":\"22726\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:3313354d-d11c-4b7e-b4e3-4a38e6f4fe52>\",\"WARC-Concurrent-To\":\"<urn:uuid:d4077272-4465-4115-a35f-cb8c1b609c27>\",\"WARC-IP-Address\":\"128.84.21.199\",\"WARC-Target-URI\":\"https://arxiv.org/abs/math/9308221\",\"WARC-Payload-Digest\":\"sha1:ID5CPREEWMACCNRPIXOLZQNDDDDYGTVC\",\"WARC-Block-Digest\":\"sha1:UAZMQALVZ4TZDIP75XMPE6JUK2IB2PQG\",\"WARC-Identified-Payload-Type\":\"application/xhtml+xml\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-16/CC-MAIN-2020-16_segments_1585370508367.57_warc_CC-MAIN-20200402204908-20200402234908-00554.warc.gz\"}"}