Previous |  Up |  Next


graph; isomorphic subgraphs; independent result; Cohen; forcing; iterated forcing
A graph $G$ on $\omega _1$ is called $<\!{\omega}$-{\it smooth\/} if for each uncountable $W\subset \omega _1$, $G$ is isomorphic to $G[W\setminus W']$ for some finite $W'\subset W$. We show that in various models of ZFC if a graph $G$ is $<\!{\omega}$-smooth, then $G$ is necessarily trivial, i.e\. either complete or empty. On the other hand, we prove that the existence of a non-trivial, $<\!{\omega}$-smooth graph is also consistent with ZFC.
[1] Hajnal A., Nagy Zs., Soukup L.: On the number of non-isomorphic subgraphs of certain graphs without large cliques and independent subsets. ``A Tribute to Paul Erdös '', ed. A. Baker, B. Bollobás, A. Hajnal, Cambridge University Press, 1990, pp.223-248. MR 1117016
[2] Jech T.: Set Theory. Academic Press, New York, 1978. MR 0506523 | Zbl 1007.03002
[3] Kierstead H.A., Nyikos P.J.: Hypergraphs with finitely many isomorphism subtypes. Trans. Amer. Math. Soc. 312 (1989), 699-718. MR 0988883 | Zbl 0725.05063
[4] Shelah S., Soukup L.: On the number of non-isomorphic subgraphs. Israel J. Math 86 (1994), 1-3 349-371. MR 1276143 | Zbl 0797.03051
Partner of
EuDML logo