\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{graph minor}

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{categorical_pov}{Categorical POV}\dotfill \pageref*{categorical_pov} \linebreak
\noindent\hyperlink{minorclosed_families}{Minor-closed families}\dotfill \pageref*{minorclosed_families} \linebreak
\noindent\hyperlink{graph_minor_theorem}{Graph minor theorem}\dotfill \pageref*{graph_minor_theorem} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\textbf{Please don't tamper with this article for a little while -- I want to make more edits soon and not have the flow interrupted.}

\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

Let $G$ and $H$ be [[graph|simple graphs]]. Then $H$ is a \textbf{graph minor} of $G$ if it is isomorphic to a graph obtained by applying a sequence of operations of the following sort, starting from $G$:

\begin{itemize}%
\item Removing edges;


\item Removing isolated points;


\item Contracting edges, where contracting an edge means removing it and identifying its endpoints.



\end{itemize}
Graph minors can be viewed as certain types of subquotients in an appropriate category of graphs; this article describes which subquotients those are in categorical language.

\begin{remark}
\label{}\hypertarget{}{}
To be honest, it's not really clear how a categorical POV (or at least the POV presented here) can usefully inform or guide or clarify graph theory. For the time being, we are just collecting some notes. No deep theorems of graph theory are proved here. The main observation is simply that graphs form a category with very good properties, and there may be potential of putting those properties to effective use some day.

\end{remark}
\hypertarget{categorical_pov}{}\subsection*{{Categorical POV}}\label{categorical_pov}

We take the point of view that a \emph{simple graph} (consisting of a set of vertices $V$ and a collection of two-element subsets of $V$ called ``edges'') carries the same information as a set $V$ equipped with a reflexive symmetric relation $E$, and that a morphism of simple graphs should be defined as a function between the vertex-sets which respects such relations. Indeed, such a relation determines and is uniquely determined by a simple graph $G$ where for given vertices $x, y \in V$, there is an edge $\{x, y\}$ between $x$ and $y$ in $G$ iff both $(x, y) \in E$ and $x \neq y$. We will write $E(x, y)$ to mean $(x, y) \in E$.

\begin{remark}
\label{}\hypertarget{}{}
Since edges are $2$-element subsets, it might seem more natural to interpret a simple graph as a set $V$ equipped with a symmetric \emph{irreflexive} relation $E$, whereby $E(x, x)$ is false for all $x \in V$. But the result is a rather poor category which lacks certain morphisms we would like, such as edge contractions, at least if we take the morphisms $(V, E) \to (W, F)$ to be functions $f: V \to W$ which preserve those relations. Indeed, we could never have both $E(x, y)$ and $f(x) = f(y)$ since irreflexivity of $F$ would render $F(f(x), f(y))$ false. Thus, requiring reflexivity is the more flexible option.

\end{remark}
Notice that contraction of edges yields a quotient in this category. For example, if we want to contract a collection of edges by identifying certain points along an equivalence relation $R$, that is via some quotient map $q: V \to V/R$, then we simply take the image of the composite

\begin{displaymath}
E \hookrightarrow V \times V \stackrel{q \times q}{\to} V/R \times V/R;
\end{displaymath}
notice this image is a reflexive symmetric relation on $V/R$.

Thus, we let $SimpGph$ denote the category of sets equipped with a reflexive symmetric relation. This category is convenient in many respects (for details see [[category of simple graphs]]):

\begin{theorem}
\label{}\hypertarget{}{}
The category $SimpGph$ has the following properties.

\begin{itemize}%
\item It is a [[Grothendieck quasitopos]]. In particular, both it and its opposite $SimpGph^{op}$ are regular categories.


\item It is an $\infty$-[[extensive category]].


\item The forgetful functor $\Gamma = \hom(1, -): SimpGph \to Set$ is faithful and exhibits $SimpGph$ as a [[topological concrete category]].


\item $SimpGph$ is \emph{cohesive}: the adjoint string $\Delta \dashv \Gamma \dashv \nabla: Set \to SimpGph$ has a further left adjoint $\Pi \dashv \Delta$, and $\Pi: SimpGph \to Set$ preserves products.



\end{itemize}
\end{theorem}
Of course $\Delta$ assigns to a set $X$ the discrete graph on $X$ (the minimal reflexive relation $\delta_X \hookrightarrow X \times X$), and $\nabla$ the codiscrete graph (the maximal relation $1_{X \times X}$), while $\Pi(G)$ is the set of connected components of $G$. Let $\gamma: 1 \to \Delta \Pi$ denote the unit of $\Pi \dashv \Delta$; the component $\gamma G: G \to \Delta \Pi (G)$ takes a vertex $v \in G$ to the connected component to which it belongs. Notice that $\gamma G$ is a regular epi.

\begin{defn}
\label{}\hypertarget{}{}
A \emph{contraction} map between simple graphs is a morphism $\pi: G \to G'$ that arises by pushing out a map of the form $\gamma K$ along some map $f: K \to G$:

\begin{displaymath}
\itexarray{
K & \stackrel{f}{\to} & G \\ 
\mathllap{\gamma K} \downarrow & po & \downarrow \mathrlap{\pi} \\ 
\Pi(K) & \to & G'
}
\end{displaymath}
is a pushout square. If $G \to G'$ is a contraction map, we also say $G'$ is a \emph{contraction} of $G$.

\end{defn}
It is immediate that a contraction map is a regular epi, since every $\gamma K$ is regular epi.

\begin{prop}
\label{composition}\hypertarget{composition}{}
Contraction maps are closed under composition.

\end{prop}
\begin{proof}
\end{proof}
\begin{defn}
\label{}\hypertarget{}{}
A graph $H$ is a \emph{minor} of a graph $G$ if it arises as a subobject of some contraction of $G$:

\begin{displaymath}
\itexarray{
 & & G \\ 
 & & \downarrow \mathrlap{contraction} \\ 
H & \rightarrowtail & G'
}
\end{displaymath}
\end{defn}
\begin{prop}
\label{}\hypertarget{}{}
The subquotient relation is reflexive and transitive.

\end{prop}
\begin{proof}
Reflexivity is clear. For transitivity, we compose subquotients by taking a pushout square as follows.

\begin{displaymath}
\itexarray{
G & \twoheadrightarrow & G' & \twoheadrightarrow & G'' \\
 & &  ^\mathllap{mono} \uparrow & & \uparrow^\mathrlap{mono} \\
 & & H & \twoheadrightarrow & H' \\
 & & & & \uparrow^\mathrlap{mono} \\
 & & & & J
}
\end{displaymath}
where we use the simple fact that the pushout of a mono along an arrow in $SimpGph$ is a mono (because $Vert$ reflects monos and preserves monos and pushouts, plus the fact that the pushout of a mono in $Set$ is a mono).

\end{proof}
For finite graphs, the subquotient relation is also antisymmetric (if $G$ and $H$ are minors of one another, then they are isomorphic). Indeed, if either the arrow $G \twoheadrightarrow G'$ or the arrow $H \hookrightarrow G'$ is not an isomorphism, then $H$ has strictly fewer edges and vertices than $G$. This is clearly not the case for infinite graphs (e.g., the infinite rooted binary tree without leaves contains as a subgraph a disjoint sum of two copies of itself).

(I intend to expand this section, eventually. Hopefully one can develop a categorical story about graph minors in particular.)

\hypertarget{minorclosed_families}{}\subsection*{{Minor-closed families}}\label{minorclosed_families}

\begin{itemize}%
\item The collection of [[forests]] is closed under the graph minor relation.


\item The collection of [[planar graphs]] is closed under the graph minor relation.



\end{itemize}
\hypertarget{graph_minor_theorem}{}\subsection*{{Graph minor theorem}}\label{graph_minor_theorem}

This celebrated result of Robertson and Seymour says that no collection of finite graphs, ordered by the graph minor relation, has an infinite [[antichain]]. Equivalently, that in any collection of finite graphs, there are only finitely many elements which are minimal with respect to the graph minor relation.

As a corollary, any class $F$ of finite graphs which is closed under minors admits a \textbf{forbidden minor characterization}: is precisely the class of graphs which do not have any members of a specific finite family of graphs as a minor. (Proof: the complement of $F$ in the poset of finite graphs has finitely many minimal members. Then, $x$ belongs to $F$ iff none of these minimal members occurs as a minor of $x$.

For example, the class of forests is precisely the class of finite graphs which do not have a triangle $K_3$ as a minor. The class of planar graphs is precisely the class of finite graphs which do not have $K_5$ or $K_{3, 3}$ as a minor.

Forbidden minor characterizations also exist for certain classes of [[matroid|matroids]]. (See for example Wikipedia \href{http://en.wikipedia.org/wiki/Matroid#Forbidden_minors}{here}.)

\hypertarget{references}{}\subsection*{{References}}\label{references}

\begin{itemize}%
\item Wikipedia article on graph minors \href{http://en.wikipedia.org/wiki/Minor_%28graph_theory%29}{(link)}

\end{itemize}
[[!redirects graph minors]]



\end{document}