6
$\begingroup$

The Rado graph contains every finite graph as induced subgraph, and its also holds for countable graphs. So it is an universal graph of size $\aleph_0$, which contains all graphs of size $\aleph_0$ as induced subgraph.

Question: Is it also true for higher cardinals? Does there exist a graph of size $\kappa$, which contains all graphs of size $\kappa$ as induced subgraph? If not, what is the condition for $\kappa$?

$\endgroup$
1
  • 1
    $\begingroup$ I think that you probably need some assumptions about cardinal arithmetics. Something like $\kappa^{<\kappa}=\kappa$. $\endgroup$
    – Asaf Karagila
    Jan 5, 2014 at 22:01

2 Answers 2

6
$\begingroup$

Following up on Asaf's comment, indeed, if $\kappa^{\lt\kappa}=\kappa$, then we may build a $\kappa$-universal graph of size $\kappa$. Proceed in $\kappa$ many stages. At each stage, we have a graph of size $\gamma$, less than $\kappa$. There are precisely $2^\gamma\leq\kappa$ many ways to add a single new point to this graph. Using a pairing function, we add at stage $\langle\alpha,\beta\rangle$ a point realizing the $\beta^{th}$ pattern of connectivity with the points constructed at stage $\alpha$. It follows that after $\kappa$ many stages, we will have a $\kappa$-universal graph, since for any graph of size $\kappa$, we enumerate its nodes and then systematically find a copy inside our universal graph realizing that pattern of connectivity with the previous nodes. This is the "forth" part of the usual back-and-forth arguments.

$\endgroup$
2
9
$\begingroup$

An old result of Shelah states that if one adds $\lambda > \kappa^{++}$ Cohen subsets to a cardinal satisfying $\kappa^{<\kappa}$, then in the resulting universe the universality number for graphs on $\kappa^+$ is $\lambda$. It is possible to have a universal graph of size $\aleph_1$ even when CH fails (Mekler and Shelah independently).

$\endgroup$
2
  • 3
    $\begingroup$ Mirna: Welcome! $\endgroup$
    – Asaf Karagila
    May 31, 2014 at 15:50
  • 2
    $\begingroup$ Welcome to MathOverflow! $\endgroup$ May 31, 2014 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.