Negative universality results for graphs

Volume 210 / 2010

S.-D. Friedman, K. Thompson Fundamenta Mathematicae 210 (2010), 269-283 MSC: Primary 03E75, 03E35; Secondary 03E05, 03E55. DOI: 10.4064/fm210-3-3


It is shown that in many forcing models there is no universal graph at the successors of regular cardinals. The proof, which is similar to the well-known proof for Cohen forcing, is extended to show that it is consistent to have no universal graph at the successor of a singular cardinal, and in particular at $\aleph _{\omega +1}$. Previously, little was known about universality at the successors of singulars. Analogous results show it is consistent not just that there is no single graph which embeds the rest, but that it takes the maximal number ($2^\lambda $ for graphs of size $\lambda $) to embed the rest.


  • S.-D. FriedmanKurt Gödel Research Center
    for Mathematical Logic
    Währinger Straße 25
    A-1090 Wien, Austria
  • K. ThompsonInstitut für Diskrete Mathematik und Geometrie
    Technische Universität Wien
    Wiedner Hauptstraße 8–10/104
    A-1040 Wien, Austria

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image