### Universal graphs without large cliques

by Komjath and Shelah. [KoSh:492]

J Combinatorial Theory. Ser. B, 1995

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.

Back to the list of publications