A. Hajnal, Zs. Nagy, L. Soukup:
On the number of certain subgraphs of graphs without
large cliques and independent subsets
A graph G=<V,E> without
cliques or independent subsets of size |V| is called non-trivial.
We say that G= <V,E> is almost-smooth iff it is isomorphic
to G[V-W] whenever W is a subset of V with |W| < |V|. Given a
graph G= <V,E> denote by I(G) the set of all isomorphism classes of
induced subgraphs
of cardinality |V|. It is shown that
- |I(G)|>=2^omega for each non-trivial graph G=<omega_1,E>.
- under principle Diamond^+ there is a non-trivial graph
G=<omega_1,E> with |I(G)|=omega_1.
- the existence of a non-trivial, almost-smooth graph on omega_1 is
consistent with
different set-theoretical assumptions.
- under principle Diamond^+ there exists a family F
of countable subsets of omega_1
which is non-trivial
in a certain sense, and which is isomorphic to
{B \in F: B \subset A} whenever
A \subset omega_1 is an uncountable set.
Downloading the paper
gzipped tex file (21709 bytes)
gzipped dvi file (49419 bytes)
appeared in "A Tribute to Paul Erdos ",
e.d. A Baker, B. Bollobás, A. Hajnal, Cambridge University Press,
1990, p. 223-248.