From 5f3dce607a36e14a168b3cb07fd72a909611b163 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 13 Sep 2008 20:21:17 +0200 Subject: [PATCH] A couple of fixes to minor-closed classes. --- adv.tex | 18 +++++++++--------- 1 file changed, 9 insertions(+), 9 deletions(-) diff --git a/adv.tex b/adv.tex index dace909..eca96fd 100644 --- a/adv.tex +++ b/adv.tex @@ -79,11 +79,11 @@ edge density $\varrho(\cal C)$ of the class is then defined as the infimum of $\ Let us consider a~non-trivial minor-closed class~${\cal C} = \Forb({\cal H})$ and a~graph $X\in{\cal H}$ with the minimum number of vertices. Obviously, $\Forb({\cal H}) \subseteq \Forb(X)$, because excluding additional -minors cannot make the class richer. Also, if we denote the number of vertices +minors can only reduce the class. Also, if we denote the number of vertices of~$X$ by~$k$, we have $X\minorof K_k$ and hence $\Forb(X) \subseteq \Forb(K_k)$. When we put these two inclusions together, we get ${\cal C} \subseteq \Forb(K_k)$ and so $\varrho({\cal C}) \le \varrho(\Forb(K_k))$. It is therefore sufficient to -bound the density of classes that exclude a~single complete graph. +bound the density for classes that exclude a~single complete graph only. Moreover, our parameter~$k$ is equal to the well-known Hadwiger number: \defn\id{hadwiger}% @@ -106,7 +106,7 @@ Hadwiger number of the class. \proof We already know that it is sufficient to prove the theorem for the case when -${\cal C}$ excludes on the complete graph~$K_k$. +${\cal C}$ excludes just the complete graph~$K_k$. We will prove the contrapositive. If $\varrho({\cal C}) > 2h(k)$, then there is some graph $G\in{\cal C}$ such that $\varrho(G) > 2h(k)$. This implies that the average degree @@ -114,12 +114,12 @@ of~$G$ is greater than~$h(k)$, so by the previous theorem $G$~contains a~subdivi of~$K_k$ and hence also~$K_k$ as a~minor. \qed -\para -The Mader's original proof of Theorem \ref{maderthm} yields $h(k) \approx 2^{n^2}$, which is -very coarse. It was however vastly improved later: Kostochka -\cite{kostochka:lbh} and independently Thomason \cite{thomason:efc} have proven -that an~average degree $\Omega(k\sqrt{\log k})$ is sufficient to enforce~$K_k$ -as a~minor and that this is the best what we can get. Their result implies: +\paran{A~better bound}% +The Mader's original proof of Theorem \ref{maderthm} yields $h(k) \approx 2^{n^2}$, +but it is possible to obtain a~closer bound. Kostochka \cite{kostochka:lbh} and +independently Thomason \cite{thomason:efc} have proven that an~average degree +$\Omega(k\sqrt{\log k})$ is sufficient to enforce~$K_k$ as a~minor and that +this is the best what we can get. Their result implies: \cor $\varrho({\cal C}) = \O(k\sqrt{\log k})$ whenever ${\cal C}$ is a~minor-closed -- 2.39.2