6
$\begingroup$

Consider the following generalized graph-minor theorem:

GM($κ,λ$): Given any collection $S$ of $κ$ simple undirected graphs each with less than $λ$ vertices, there are distinct graphs $G,H$ in $S$ such that $G$ embeds as a minor into $H$.

Then the Robertson-Seymour theorem is GM($\aleph_0,\aleph_0$). Vopěnka's principle is said to imply GM(∞,∞) where "∞" here denotes "proper class sized". I was hence wondering what is known about other cardinals $κ,λ$. It is obvious that GM($κ,λ$) is true if $κ > \sup_{μ<λ} 2^μ$. And this post states that GM($2^{\aleph_0},(2^{\aleph_0})^+$) is false. So my questions are:

  1. What is known about the minimum $κ$ in terms of $λ$ such that GM($κ,λ$) is true? In particular, I am most curious about $λ = \aleph_1$, and I guess GM($\aleph_0,\aleph_1$) is false while GM($\aleph_1,\aleph_1$) is true.

  2. Is GM($κ,κ$) known to be true or false for any particular $κ > \aleph_0$? Does Vopěnka's principle make a difference?

[Note: I edited to fix an error that was pointed out in the comments.]

Improve this question
$\endgroup$
6
  • $\begingroup$ I have a result saying that if $\kappa$ is an uncountable cardinal, then there are $2^\kappa$ graphs of size $\kappa$ none embeddable as a minor in any other. doi.org/10.1017/S0305004100072881 $\endgroup$
    – Péter Komjáth
    Commented Jun 2, 2019 at 12:48
  • $\begingroup$ @PéterKomjáth: Your result implies GM($2^κ,κ^+$) is false for uncountable cardinal $κ$, and so GM($κ,κ$) is false for any successor cardinal $κ ≥ \aleph_2$, right? I'll have a look at your paper; somehow I couldn't find it via google. Any idea for $\aleph_1$ and uncountable limit cardinals? Thanks! $\endgroup$
    – user21820
    Commented Jun 2, 2019 at 13:11
  • $\begingroup$ @user21820 Do you have a reference for Vopenka's principle being equivalent to $GM(\infty, \infty)$ ? It's true if 'graph minor' is replaced with 'subgraph' (which implies one direction of the equivalence), but how do you show the other direction? $\endgroup$
    – Adam P. Goucher
    Commented Jul 1, 2019 at 17:36
  • $\begingroup$ @AdamP.Goucher: I just quoted wikipedia's claim, and don't actually know a reference. $\endgroup$
    – user21820
    Commented Jul 1, 2019 at 18:06
  • $\begingroup$ @user21820 Where does Wikipedia make that claim? I did a Ctrl+F for 'minor' on that page to no avail. $\endgroup$
    – Adam P. Goucher
    Commented Jul 1, 2019 at 18:21

0

Reset to default

You must log in to answer this question.