% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P55}{20(3)}{2013}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

\usepackage{enumitem}
\usepackage{capt-of}
\usepackage{ifthen}

% we recommend the graphicx package for importing figures
%\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
%\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins



% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

%\theoremstyle{definition}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{open}[theorem]{Open Problem}
%\newtheorem{problem}[theorem]{Problem}
%\newtheorem{question}[theorem]{Question}

%\theoremstyle{remark}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A note on forbidding clique immersions}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Matt DeVos\thanks{Supported in part by an NSERC Discovery Grant (Canada) and a Sloan Fellowship.}\\
\small Department of Mathematics\\[-0.8ex]
\small Simon Fraser University\\[-0.8ex]
\small Burnaby, B.C., Canada\\
\small\tt mdevos@sfu.ca\\
\and
Jessica McDonald\thanks{Previously supported by an NSERC Postdoctoral Fellowship (Canada).} \\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small Auburn University\\[-0.8ex]
\small Auburn, AL, U.S.A.\\
\small\tt mcdonald@auburn.edu
\and
Bojan Mohar\thanks{Supported in part by an NSERC Discovery Grant (Canada), by the Canada Research Chair program, and by the Research Grant J1--4106 of ARRS (Slovenia). On leave from: IMFM \& FMF, Department of Mathematics, University of Ljubljana, Ljubljana, Slovenia.}\\
\small Department of Mathematics\\[-0.8ex]
\small Simon Fraser University\\[-0.8ex]
\small Burnaby, B.C., Canada\\
\small\tt mohar@sfu.ca
\and
Diego Scheide \\
\small Department of Mathematics\\[-0.8ex]
\small Simon Fraser University\\[-0.8ex]
\small Burnaby, B.C., Canada\\
\small\tt dscheide@sfu.ca
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{July 10, 2012}{Sep 23, 2013}{Oct 7, 2013}\\
\small Mathematics Subject Classifications: 05C75}

\begin{document}

\maketitle


\begin{abstract}
Robertson and Seymour proved that the relation of graph immersion is well-quasi-ordered for finite graphs. Their proof uses the results of graph minors theory. Surprisingly, there is a very short proof of a corresponding rough structure theorem for graphs without $K_t$-immersions; it is based on the Gomory-Hu theorem. The same proof also works to establish a rough structure theorem for Eulerian digraphs without $\vec{K}_t$-immersions, where $\vec{K}_t$ denotes the complete digraph of order $t$.

  % keywords are optional
  
\end{abstract}

\vspace*{.3in}

In this paper all graphs and digraphs are finite and may have loops and multiple edges, unless explicitly stated otherwise.

A pair of distinct adjacent edges $uv$ and $vw$ in a graph
are \emph{split off} from their common vertex $v$ by deleting the edges
$uv$ and $vw$, and adding the edge $uw$ (possibly in parallel to an existing edge,
and possibly forming a loop if $u = w$). A graph $H$ is
said to be \emph{immersed} in a graph $G$ if a graph isomorphic to
$H$ can be obtained from a subgraph of $G$ by splitting off pairs of
edges (and removing isolated vertices).
If $H$ is immersed in a graph $G$, then we also say
that $G$ has an \emph{$H$-immersion}.
An alternative definition is that $H$ is immersed in $G$ if there is
a 1-1 function $\phi: V(H)\to V(G)$ such that for each edge $uv\in E(H)$, if $u\neq v$
there is a path $P_{uv}$ in $G$ joining vertices $\phi(u)$ and $\phi(v)$, if $u=v$ there is a cycle $C_{uv}$ in $G$ containing $\phi(u)=\phi(v)$,
and the paths $P_{uv}$ and cycles $C_{uv}$ are pairwise edge-disjoint for all $uv\in E(H)$.

Robertson and Seymour \cite{RS23} proved that the relation of graph immersion is a well-quasi-ordering, that is, for every infinite set of graphs, one of them can be immersed in another one. Their proof is based on a significant part of the graph minors project. It is perhaps surprising then that there is a very short proof of a corresponding rough structure theorem for graphs without $K_t$-immersions. Moreover, the same proof technique also works to prove a rough structure theorem for Eulerian digraphs without $\vec{K}_t$-immersions. Here, by $\vec{K}_t$ we mean the \emph{complete digraph} of order $t$, having $t$ vertices and a \emph{digon} (pair of oppositely oriented edges) between each pair of vertices. By immersion in digraphs we mean the natural directed analogue of immersion in undirected graphs. That is, we say that a digraph $F$ is \emph{immersed\/} in a digraph $D$ if there is
a 1-1 function $\phi: V(F)\to V(D)$ such that for each edge $uv\in E(F)$, if $u\neq v$ there is a directed path $P_{uv}$ in $D$ from $\phi(u)$ to $\phi(v)$, if $u=v$ there is a directed cycle $C_{uv}$ in $D$ containing $\phi(u)=\phi(v)$,
and the paths $P_{uv}$ and cycles $C_{uv}$ are pairwise edge-disjoint for all $uv\in E(F)$. Given a directed walk $uvw$ of length two in a digraph , the pair of  edges $uv$, $vw$ are \emph{split off} from $v$ by deleting the edges $uv$ and $vw$, and adding the edge $uw$.

To state the two rough structure theorems explicitly, we first need the definition of a laminar family of edge-cuts. Given a graph or digraph $G$ and a vertex-set $X\subseteq V(G)$, we denote by $\delta(X)$ the edge-cut of $G$ consisting of all edges between $X$ and $V(G)\setminus X$ (in both directions). Two edge-cuts $\delta(X)$ and $\delta(Y)$ in a connected graph or digraph are \emph{uncrossed\/} if either $X$ or $V(G) \setminus X$ is contained in either $Y$ or $V(G) \setminus Y$.  Two edge-cuts in a general graph or digraph are \emph{uncrossed\/} if this holds in each component.  A family of pairwise uncrossed edge-cuts is called \emph{laminar}. A laminar family of edge-cuts in a graph or digraph induces a partition of the entire vertex set; we call the parts of such a partition \emph{blocks}.

\begin{theorem}\label{undirstruct}
For every graph which does not contain an immersion of the complete graph $K_{t}$, there exists a laminar family of edge-cuts, each with size $< (t-1)^2$, so that every block of the resulting vertex partition has size less than $t$.
\end{theorem}

\begin{theorem}\label{dirstruct}
For every Eulerian digraph which does not contain an immersion of $\vec{K}_t$, there exists a laminar family of edge-cuts, each with size $< 2(t -1)^2$, so that every block of the resulting partition has size less than $t$.
\end{theorem}

We will show that the Gomory-Hu Theorem (stated shortly) yields very easy proofs of Theorems \ref{undirstruct} and \ref{dirstruct}. We originally had somewhat weaker bounds for both of these results. In fact, Theorem \ref{undirstruct} as stated above is due to Wollan \cite{W}, whose work we learned of later. We were helped by the following observation of Wollan \cite{W}, and its directed analog.

\begin{observation}\label{SW} Let $H_t$ be the graph obtained from $K_{1,t-1}$ by replacing each edge with $t-1$ parallel edges. Then $H_t$ has a $K_{t}$-immersion.
\end{observation}

\begin{proof} Let $v_1$ be the vertex of degree $(t-1)^2$ and let $v_2, \ldots v_t$ be the vertices of degree $t-1$. Label the $t-1$ edges between $v_1$ and $v_j$ by $\{e_{j,1},e_{j,2}, \ldots e_{j, t} \} \setminus e_{j,j}$ for $2 \le j \le t$. Then we have an immersion of $K_t$ on the vertices $v_1, \ldots, v_{t}$, where the requisite paths between $v_1$ and $v_2, \ldots v_{t}$ are given by $e_{2,1}, \ldots e_{t,1}$, and for every pair of vertices $v_i, v_j$ with $1<i< j\leq t$, the path between $v_i$ and $v_j$ is given by $e_{i,j}e_{j,i}$.\end{proof}


\begin{observation}\label{SW2} Let $\vec{H}_t$ be the digraph obtained from $K_{1,t-1}$ by replacing each edge with $t-1$ digons. Then $\vec{H}_t$ has a $\vec{K}_{t}$-immersion.
\end{observation}

\begin{proof}
Modify the proof of Observation \ref{SW} by labelling digons as opposed to labelling edges.
\end{proof}

The bounds of Theorems \ref{undirstruct} and \ref{dirstruct} provide rough structure to the same extent. Namely, while the laminar family of Theorem \ref{undirstruct}  does not prohibit  a $K_t$-immersion, it does indeed prohibit a $K_{t^2}$-immersion. Analogously, the laminar family of Theorem \ref{dirstruct} also prohibits a $\vec{K}_{t^2}$-immersion.


That we restrict ourselves to Eulerian digraphs in Theorem \ref{dirstruct} should not be surprising. First of all, let us observe that digraph immersion is not a well-quasi-order in general. Furthermore, the present authors have exhibited in \cite{DMMS} that there exist simple non-Eulerian digraphs with all vertices of arbitrarily high in- and outdegree which do not contain even a $\vec{K}_3$-immersion. (Here, by simple digraph we mean a digraph $D$ with no loops and  at most one edge from $x$ to $y$ for any $x,y \in V(D)$, but where digons are allowed).
On the positive side, it has been shown by Chudnovsky and Seymour \cite{ChSe} that digraph immersion is a well-quasi-order for tournaments. That Eulerian digraphs of maximum outdegree $2$ are well-quasi-ordered by immersion was proved (although not written down) by Thor Johnson as part of his PhD thesis \cite{Jo}.

In \cite{DDFMMS}, the present authors along with Fox and Dvo\v{r}\'{a}k, proved that (undirected) simple graphs with minimum degree at least $200t$ contain a $K_t$-immersion.
In another paper \cite{DMMS}, the following positive result is obtained for digraphs when the Eulerian condition is added.

\begin{theorem} \emph{\cite{DMMS}}
\label{mindeg}
Every simple Eulerian digraph with minimum outdegree at least $t(t-1)$ contains an immersion of $\vec{K}_t$.
\end{theorem}

Theorem \ref{mindeg} is directly implied by Theorem \ref{dirstruct}, providing an alternate proof of Theorem \ref{mindeg} to that given in \cite{DMMS}. In fact, we obtain a slightly stronger version, as follows.

\begin{theorem}
Every simple Eulerian digraph with minimum outdegree at least $(t-1)^2$ contains an immersion of $\vec{K}_t$.
\end{theorem}

\begin{proof}
Suppose, for a contradiction, that $D$ is a simple Eulerian digraph with minimum outdegree at least $(t-1)^2$ that does not contain an immersion of $\vec{K}_t$. It must be the case that $t\geq 3$, so in particular $D$ contains at least $t$ vertices, and Theorem \ref{dirstruct} implies that $D$ contains a set $S\subseteq V(D)$ of  $|S|=s<t$ vertices with $|\delta(S)| < 2(t-1)^2$. Note that by the minimum degree condition, we know that $s >1$.
Then
$$s(t-1)^2\leq |E[S]|+\tfrac{1}{2}|\delta(S)| < s(s-1)+(t-1)^2$$
which implies that
$$s>(t-1)^2.$$
Since $t\geq 3$, this contradicts the fact that $s<t$.
\end{proof}


An edge-cut $\delta(X)$ in a graph $G$ is said to \emph{separate} a pair of vertices $x,y\in V(G)$ if $x\in X$ and $y\in V(G)\setminus X$ (or vice versa). Given a tree $F$ and an edge $e\in E(F)$, there exists $X\subseteq V(F)$ such that $\delta(X)=e$; $\delta(X)$ is called a \emph{fundamental cut\/} in $F$ and is associated with the vertex partition $\{X, V(F)\setminus X\}$ of $V(F)$.

\begin{theorem}[Gomory-Hu \cite{GH}]
For every graph $G$, there exists a tree $F$ with vertex set $V(G)$ and a function $\mu : E(F) \rightarrow {\mathbb Z}$ so that the following hold.
\begin{itemize}
\item For every edge $e\in E(F)$ we have that $\mu(e)$ equals the size of the edge-cut of $G$ given by the vertex partition associated with the fundamental cut of $e$ in the tree $F$.
\item For every $u,v \in V(G)$ the size of the smallest edge-cut of $G$ separating $u$ and $v$ is the minimum of $\mu(e)$ over all edges $e$ on the path in $F$ from $u$ to $v$.
\end{itemize}
\end{theorem}

\bigskip


\noindent{\it Proof of Theorem \ref{undirstruct} (and Theorem \ref{dirstruct}):}
Let $G$ be an arbitrary graph (or let $D$ be an arbitrary Eulerian digraph and let $G$ be underlying graph of $D$). Apply the Gomory-Hu Theorem to $G$ to choose a tree $F$ on $V(G)$ and an associated function $\mu$.  Let ${\mathcal C}$ be the family of edge-cuts of $G$ that are associated with edges $e \in E(F)$ for which $\mu(e) < (t-1)^2$ ($\mu(e)<2(t-1)^2$). We show that if any block of the resulting vertex partition has size $\geq t$, than $G$ contains a $K_t$-immersion ($D$ contains a $\vec{K}_t$-immersion). To this end, suppose we have such a block with distinct vertices $ v_1, v_2 \ldots, v_t$. Then every edge-cut separating these $t$ vertices has size $\ge (t-1)^2$ ($\ge 2(t-1)^2$). We claim that there exist $(t-1)^2$ edge disjoint (directed) paths starting at $v_1$ so that exactly $t-1$ of them end at each $v_j$ for $2 \le j \le t$. To see this, consider adding an auxiliary vertex $w$ to the graph with $t-1$ parallel edges ($t-1$ digons) between $w$ and each of $v_2, \ldots, v_{t}$. Then apply Menger's Theorem to $v_1$ and $w$, noting that every cut separating $v$ and $w$ contains at least $(t-1)^2$ edges (in each direction). (Moreover, since $G$ is Eulerian, if we delete these directed paths we can apply Menger's Theorem again to get $(t-1)^2$ edge disjoint directed paths ending at $v_1$ so that exactly $t-1$ of them start at each $v_j$ for $2 \le j \le t$). Hence $G$ immerses the graph $H_t$ ($D$ immerses the digraph $\vec{H}_t$) as in Observation \ref{SW} (Observation \ref{SW2}).
\hfill$\Box$


\subsection*{Acknowledgements}

The authors are very grateful to Paul Wollan for helpful discussions, and to an anonymous referee, whose comments simultaneously improved the bound of Theorem \ref{dirstruct} and simplified its proof.






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem{ChSe} M. Chudnovsky and P. D. Seymour.  A well-quasi-order for tournaments. \emph{J. Combin. Theory, Ser. B}, 101: 47--53, 2011.

\bibitem{DMMS} M. DeVos, J. McDonald, B. Mohar and D. Scheide. Immersing complete digraphs.
    \emph{Europ. J. Combin.}, 33(6): 1294--1302, 2012.

\bibitem{DDFMMS} M.~DeVos, Z.~Dvo\v{r}\'{a}k, J.~Fox, J.~McDonald, B.~Mohar and D.~Scheide.
A minimum degree condition forcing complete graph immersion. 
\arxiv{1101.2630}, 2011. To appear in \emph{Combinatorica}. 

\bibitem{GH} R. E. Gomory and T. C. Hu. Multi-terminal network flows. \emph{J. Soc. Indust. Appl. Math.}, 9(4): 551--570, 1961.

\bibitem{Jo} T. Johnson. Eulerian Digraph Immersion. Ph. D. thesis, Princeton University, 2002.

\bibitem{RS23} N. Robertson and P. D. Seymour.
Graph Minors XXIII, Nash-Williams' immersion conjecture.
\emph{J. Combin. Theory, Ser. B}, 100: 181--205, 2010.

\bibitem{W} P. Wollan. The structure of graphs not admitting a fixed immersion. 
\arxiv{1302.3867}, 2013.

\end{thebibliography}

\end{document}