From 795bf392c7ae0e7ddfb5c45b2ba2c4d3b8ebfd24 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 27 Feb 2008 12:17:59 +0100 Subject: [PATCH] Corrections to the minor-closed chapter. --- PLAN | 1 + adv.tex | 64 ++++++++++++++++++++++++++++++--------------------------- 2 files changed, 35 insertions(+), 30 deletions(-) diff --git a/PLAN b/PLAN index 228a8e0..3795f32 100644 --- a/PLAN +++ b/PLAN @@ -78,3 +78,4 @@ Notation: - use \delta(X) notation - unify use of n(G) vs. n - use calligraphic letters from ams? +- change the notation for contractions -- use double slash instead of the dot? diff --git a/adv.tex b/adv.tex index bf78611..8c02792 100644 --- a/adv.tex +++ b/adv.tex @@ -34,38 +34,41 @@ Non-trivial minor-closed classes include: Many of the nice structural properties of planar graphs extend to minor-closed classes, too (see \cite{diestel:gt} for a~nice overview of this theory). The most important property is probably the characterization -of such classes by forbidden minors. +of such classes in terms of their forbidden minors. \defn For a~class~$\cal H$ of graphs we define $\Forb({\cal H})$ as the class of graphs which do not contain any of the graphs in~$\cal H$ as a~minor. We will call $\cal H$ the set of \df{forbidden (or excluded) minors} for this class. +We will often abbreviate $\Forb(\{M_1,\ldots,M_n\})$ to $\Forb(M_1,\ldots,M_n)$. \obs For every~${\cal H}\ne\emptyset$, the class $\Forb({\cal H})$ is non-trivial and closed on minors. This works in the opposite direction as well: for every minor-closed class~$\cal C$ there is a~class $\cal H$ such that ${\cal C}=\Forb({\cal H})$. -One such~$\cal H$ is the complement of~$\cal C$, but smaller sets can be found, too. -For example, the planar graphs exclude exactly $K_5$ and~$K_{3,3}$ --- this follows -from the Kuratowski's theorem (the theorem uses forbidden subdivisions, but while -in general this is not the same as forbidden minors, it is for $K_5$ and $K_{3,3}$). -The celebrated theorem by Robertson and Seymour guarantees that we can always find -a~finite set of forbidden minors. +One such~$\cal H$ is the complement of~$\cal C$, but smaller ones can be found, too. +For example, the planar graphs can be equivalently described as the class $\Forb(K_5, K_{3,3})$ +--- this follows from the Kuratowski's theorem (the theorem speaks of forbidden +subdivisions, but while in general this is not the same as forbidden minors, it +is for $K_5$ and $K_{3,3}$). The celebrated theorem by Robertson and Seymour +guarantees that we can always find a~finite set of forbidden minors. \thmn{Excluded minors, Robertson \& Seymour \cite{rs:wagner}} For every non-trivial minor-closed graph class~$\cal C$ there exists a~finite set~$\cal H$ of graphs such that ${\cal C}=\Forb({\cal H})$. \proof -This theorem has been proven in the series of papers on graph minors +This theorem has been proven in a~long series of papers on graph minors culminating with~\cite{rs:wagner}. See this paper and follow the references to the previous articles in the series. \qed \para -We will make use of another important property --- the bounded density of minor-closed -classes. The connection between minors and density dates back to Mader in the 1960's -and it can be proven without use of the Robertson-Seymour theorem. +For analysis of the contractive algorithm, +we will make use of another important property --- the bounded density of +minor-closed classes. The connection between minors and density dates back to +Mader in the 1960's and it can be proven without use of the Robertson-Seymour +theorem. \defn\id{density}% Let $\cal C$ be a class of graphs. We define its \df{edge density} $\varrho(\cal C)$ @@ -74,13 +77,13 @@ holds for every $G\in\cal C$. \thmn{Mader \cite{mader:dens}} For every $k\in{\bb N}$ there exists $h(k)\in{\bb R}$ such that every graph -with average degree at least~$h(k)$ contains a~subdivision of~$K_{k}$ as a~subgraph. +of average degree at least~$h(k)$ contains a~subdivision of~$K_{k}$ as a~subgraph. \proofsketch (See Lemma 3.5.1 in \cite{diestel:gt} for a~complete proof in English.) -Let us fix~$k$ and prove by induction on~$m$ that every graph with average -degree $a\ge 2^m$ contains a~subdivision of some graph with $k$~vertices +Let us fix~$k$ and prove by induction on~$m$ that every graph of average +degree at least~$2^m$ contains a~subdivision of some graph with $k$~vertices and ${k\choose 2}\ge m\ge k$~edges. For $m={k\choose 2}$ the theorem follows as the only graph with~$k$ vertices and~$k\choose 2$ edges is~$K_k$. @@ -93,39 +96,40 @@ the cycle~$C_k$. Induction step: Let~$G$ be a~graph with average degree at least~$2^m$ and assume that the theorem already holds for $m-1$. Without loss of generality, -$G$~is connected. Consider a~maximal set $U\subseteq V$ such that $G[U]$ is connected -and the graph $G.U$ ($G$~with $U$~contracted to a~single vertex) has average -degree at least~$2^m$ (such~$U$ exists, because $G=G.U$ whenever $\vert U\vert=1$). -Now consider the subgraph~$H$ induced in~$G$ by the -neighbors of~$U$. Every $v\in V(H)$ must have degree at least~$2^{m-1}$ -(otherwise we can add this vertex to~$U$, contradicting its maximality), so by -the induction hypothesis $H$ contains a~subdivision of some graph~$R$ with -$r$~vertices and $m-1$ edges. Any two non-adjacent vertices of~$R$ can be -connected in the subdivision by a~path lying entirely in~$G[U]$, which reveals -a~subdivision of a~graph on $m$~vertices. \qed +$G$~is connected. Consider a~maximal set $U\subseteq V$ such that the subgraph $G[U]$ +induced by~$U$ is connected and the graph $G.U$ ($G$~with $U$~contracted to +a~single vertex) has average degree at least~$2^m$ (such~$U$ exists, because +$G=G.U$ whenever $\vert U\vert=1$). Now consider the subgraph~$H$ induced +in~$G$ by the neighbors of~$U$. Every $v\in V(H)$ must have $\deg_H(v) \ge 2^{m-1}$, +as otherwise we can add this vertex to~$U$, contradicting its +maximality. By the induction hypothesis, $H$ contains a~subdivision of some +graph~$R$ with $r$~vertices and $m-1$ edges. Any two non-adjacent vertices +of~$R$ can be connected in the subdivision by a~path lying entirely in~$G[U]$, +which reveals a~subdivision of a~graph with $m$~edges. \qed \thmn{Density of minor-closed classes, Mader~\cite{mader:dens}} Every non-trivial minor-closed class of graphs has finite edge density. \proof Let~$\cal C$ be any such class, $X$~its smallest excluded minor and $x=n(X)$. -As $H\minorof K_x$, the class $\cal C$ entirely lies in ${\cal C}'=\Forb(\{K_x\})$, so +As $H\minorof K_x$, the class $\cal C$ entirely lies in ${\cal C}'=\Forb(K_x)$, so $\varrho({\cal C}) \le \varrho({\cal C}')$ and therefore it suffices to prove the theorem for classes excluding a~single complete graph~$K_x$. We will show that $\varrho({\cal C})\le 2h(x)$, where $h$~is the function from the previous theorem. If any $G\in{\cal C}$ had more than $2h(x)\cdot n(G)$ edges, its average degree would be at least~$h(x)$, so by the previous theorem -$G$~would contain a~subdivision of~$K_x$ and therefore $K_x$ as a~minor. +$G$~would contain a~subdivision of~$K_x$ and hence $K_x$ as a~minor. \qed \rem -See also Theorem 6.1 in \cite{nesetril:minors}, which also lists some other equivalent conditions. +Minor-closed classes share many other interesting properties, as shown for +example by Theorem 6.1 of \cite{nesetril:minors}. \thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}% -For any fixed non-trivial minor-closed class~$\cal C$ of graphs, Algorithm \ref{contbor} finds -the MST of any graph in this class in time $\O(n)$. (The constant hidden in the~$\O$ -depends on the class.) +For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's +algorithm (\ref{contbor}) finds the MST of any graph of this class in time +$\O(n)$. (The constant hidden in the~$\O$ depends on the class.) \proof Following the proof for planar graphs (\ref{planarbor}), we denote the graph considered -- 2.39.2