\documentclass[12pt]{article} \usepackage{e-jc} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \date{\dateline{April 4, 2014}{April 4, 2014}\\ \small Mathematics Subject Classifications: 05C63, 05C40, 05B35} \usepackage{amsthm,amssymb,amsmath,enumerate,graphicx,psfrag} %\usepackage[notref,notcite]{showkeys} % comment for final version \usepackage{algorithm} \newtheorem{definition}{Definition} \newtheorem{proposition}[definition]{Proposition} \newtheorem{theorem}[definition]{Theorem} \newtheorem{corollary}[definition]{Corollary} \newtheorem{lemma}[definition]{Lemma} \newtheorem{conjecture}[definition]{Conjecture} \newtheorem{question}[definition]{Question} \newtheorem{problem}[definition]{Problem} \newtheorem*{noCounterThm}{Theorem} \newtheorem{algo}[definition]{Algorithm} \newcommand{\kreis}[1]{\mathaccent"7017\relax #1} \newcommand{\charf}[1]{\raisebox{\depth}{\(\chi\)}_{#1}} \newcommand{\1}{{\rm 1\hspace*{-0.4ex}% \rule{0.1ex}{1.52ex}\hspace*{0.2ex}}} \newcommand{\comment}[1]{} %\newcommand{\comment}[1]{\footnote{{\bf Comment:} #1}} \newcommand{\N}{\mathbb N} \newcommand{\R}{\mathbb R} \newcommand{\Z}{\mathbb Z} \newcommand{\es}{\emptyset} \newcommand{\emtext}[1]{\text{\em #1}} \newcommand{\mymargin}[1]{% \marginpar{% \begin{minipage}{\marginparwidth}\small% \begin{flushleft}% #1% \end{flushleft}% \end{minipage}% }% }% \renewcommand{\mymargin}[1]{}% % \begin{equation}\label{somelabel} % \begin{minipage}[c]{0.8\textwidth}\em % text goes in here % \end{minipage}\ignorespacesafterend % \end{equation} \newcommand{\sm}{\setminus} \newcommand{\mm}{-} % matroid minus as min M-X \newcommand{\selfcite}[1]{$\!\!${\bf\cite{#1}}} \newcommand{\del}{\ensuremath\text{\rm del}} \newcommand{\ind}{\ensuremath\mathcal{I}} %connectivity function \newcommand{\cf}{\kappa} \newcommand{\mfc}{\ensuremath{M_{\rm FC}}}% finite cycles \newcommand{\mc}{\ensuremath{M_{\rm C}}}% topological cycles \newcommand{\mfb}{\ensuremath{M_{\rm FB}}}% finite bonds \newcommand{\mb}{\ensuremath{M_{\rm B}}}% bonds \newcommand{\atc}{\ensuremath{M_{\rm AC}}}% algebraic cycles \newcommand{\I}{\ensuremath\mathcal{I}} \newcommand{\Imax}{\ensuremath\mathcal{I^{\rm max}}} \newcommand{\eends}{\ensuremath\mathcal{E}} % edge-ends \newcommand{\itop}[1]{||#1||} \title{Matroid and Tutte-connectivity in infinite graphs} %Matroid and Tutte-connectivity in finitely separable graphs %nur um das unendlich aus dem Titel zu haben? \author{Henning Bruhn\\ \small Universit\"at Ulm, Germany\\ {\small\tt }} %\date{} \begin{document} \maketitle \begin{abstract} We relate matroid connectivity to Tutte-connectivity in an infinite graph. Moreover, we show that the two cycle matroids, the finite-cycle matroid and the cycle matroid, in which also infinite cycles are taken into account, have the same connectivity function. As an application we re-prove that, also for infinite graphs, Tutte-connectivity is invariant under taking dual graphs. \end{abstract} \section{Introduction} This work is part of a project to develop a theory for infinite matroids that is analogous to its finite counterpart. In the initial paper of this project~\cite{infaxioms}, we extended previous work of Higgs~\cite{Higgs69,Higgs69c} and Oxley~\cite{Oxley92} by giving equivalent definitions of (finite or infinite) matroids in terms of independence, bases, circuits, closure and (relative) rank, just as one is used to for finite matroids. Since then, in a series of papers~\cite{2sepmat,infintmat,matunion,matintbase,thindual}, several other aspects of infinite matroids have been explored, among them graphic matroids~\cite{matgraphs} and matroid connectivity~\cite{linkingthm}. These two last aspects are the focus of the current work: Connectivity in graphic matroids. For cycle matroids of finite graphs matroid connectivity translates into a purely graph theoretic notion. A graph $G$ is \emph{$k$-Tutte-connected} if for every $\ell\leq k$ and every partition $X,Y$ of its edge set into sets of at least $\ell$ edges each, the number of vertices incident with both an edge in $X$ and an edge in $Y$ is greater than~$\ell$. Tutte~\cite{tutte66} proved that a finite graph is $k$-Tutte-connected if and only if its cycle matroid is $k$-connected. The main result of this work is an extension of this fact to infinite graphs and matroids. For this, let us define the \emph{finite-cycle matroid} of any graph by declaring to be independent any edge set that does not contain the edge set of a finite cycle. \begin{theorem}\label{mainthm} Let $k\geq 2$ be an integer. A graph is $k$-Tutte-connected if and only if its finite-cycle matroid is $k$-connected. \end{theorem} If the graph in the theorem is infinite, the finite-cycle matroid clearly will be infinite as well. But what does it mean for an infinite matroid to be $k$-connected? A finite matroid $M$ is $k$-connected if for any $\ell\leq k$ and any partition of its ground set into two sets $X,Y$ of at least $\ell$ elements each it follows that \( r(X)+r(Y)-r(M)\geq \ell. \) Clearly, this definition is useless for infinite matroids as the involved ranks will usually be infinite. In~\cite{linkingthm} we therefore gave a rank-free definition that carries over to infinite matroids. To argue that our definition is the right one, we showed that this notion of connectivity has the same properties as in finite matroids and we, furthermore, extended Tutte's linking theorem to at least a large subclass of infinite matroids. Theorem~\ref{mainthm} substantiates our claim further. \medskip Let us call a graph $G$ \emph{finitely separable} if any two vertices may be separated by the deletion of finitely many edges. In~\cite{matgraphs}, we observed that any {finitely separable} graph has not one but two cycle matroids: the {finite-cycle matroid} and the \emph{cycle matroid}, in which any edge set containing a finite or infinite cycle is said to be dependent. Here, an infinite cycle in the graph is the homeomorphic image of the unit circle in a natural topological space obtained from the graph (often by compactifying it). This definition was proposed by Diestel and K\"uhn in a completely graph-theoretical context and was subsequently seen to be extremely fruitful as it allows to extend virtually any result about cycles in a finite graph to at least a large class of infinite graphs; see Diestel~\cite{diestelBook10} for an introduction. The cycle matroid and the finite-cycle matroid coincide in a finite graph but will usually be different in infinite graphs. However, as we shall observe in Theorem~\ref{samecf}, they always have the same connectivity and even the same connectivity function. Finally, as an application of our argumentation, we get another extension of a result known for finite graphs: Tutte-connectivity is invariant under taking duals. \begin{theorem}$\!\!${\bf\cite{endduality}}\label{tconnthm} Let $G$ and $G^*$ be a pair of dual graphs, and let $k\geq 2$. Then $G$ is $k$-Tutte-connected if and only if $G^*$ is $k$-Tutte-connected. \end{theorem} We remark that this is not a new result. In~\cite{endduality} we gave a graph-theoretical proof. Here, we will see a matroidal variant. \section{Infinite cycles} Let us fix a finitely separable graph $G=(V,E)$ in this section. A \emph{ray} of $G$ is a one-way infinite path. Two rays are \emph{edge-equivalent} if for every finite set of edges $F$ there is a component of $G-F$ that contains subrays of both rays. The equivalence classes of this relation are the \emph{edge-ends $\eends(G)$} of~$G$. We view the edges of $G$ as disjoint homeomorphic images of the unit interval $[0,1]$, and define the quotient space $X_G$ by identifying these copies of $[0,1]$ at their common endvertices. Let us define a topological space $\itop G$ on $X_G\cup\eends(G)$ by specifying the basic open sets: these are all sets of the form $\tilde C$, which consists of a topological component of $X_G-Z$ for some finite set $Z$ of inner points of edges together with all edge-ends that have a ray lying entirely in $C$. We remark that normally this space will not be Hausdorff: no edge-end can be separated from a vertex that sends infinitely many edge-disjoint paths to one of its rays. However, and this is the reason for imposing finite separability, two vertices may always be topologically distinguished. For a locally finite $G$, that is, a graph in which every vertex has finite degree, the space $\itop G$ coincides with the Freudenthal compactification. \medskip For us a \emph{cycle of $\itop G$} is a homeomorphic image of the unit circle $S^1$ in $\itop G$. This definition of cycles includes the traditional finite cycles but allows also other cycles, which then contain necessarily infinitely many vertices and edges. A \emph{standard subspace} of $\itop G$ is the closure of a subgraph of $G$ in $\itop G$. The set of edges that are completely contained in a standard subspace $X$ are denoted by $E(X)$. Cycles are standard subspaces~\cite{Moritz}. A \emph{topological spanning tree} of $\itop G$ is a standard subspace that is path-connected in $\itop G$ and which contains every vertex of $G$ but no cycle. For more details see~\cite{matgraphs}. \begin{figure}[ht] \centering \includegraphics[scale=1]{infcycle} \caption{An infinite cycle in the double ladder}\label{dladder} \end{figure} In Figure~\ref{dladder} some of the introduced concepts are illustrated. The graph there, the double ladder, has two edge-ends, one to the left and one to the right. The infinite cycle $C$ in bold lines goes through these two edge-ends. Moreover, while $C+f$ is a spanning tree of the graph it is not (even including the two edge-ends) a topological spanning tree, simply because it contains the infinite cycle $C$. On the other hand, $C-e$ can be seen to be one. Its connectivity is ensured by the edge-ends. \section{Infinite matroids} As finite matroids, infinite matroids come with a number of different axiom systems. We only describe here the \emph{independence axioms}. Let $E$ be a set, let $\I\subseteq 2^E$ be a set of subsets of $E$, and denote by $\Imax$ the sets in $\I$ that are maximal under inclusion. We say that $M=(E,\I)$ is a \emph{matroid} with independent sets $\I$ if the following axioms are satisfied: \begin{itemize} \item[\rm (I1)] $\emptyset\in\mathcal I$. \item[\rm (I2)] $\I$ is closed under taking subsets, that is if $I\in\I$ and $J\subseteq I$ then $J\in \I$. \item[\rm (I3)] For all $I\in\I\sm\Imax$ and $I'\in\Imax$ there is an $x\in I'\sm I$ such that $I\cup\{x\}\in\I$ \item[\rm (IM)] The set $\{\,I'\in\I: I\subseteq I'\subseteq X\,\}$ has a maximal element, whenever $I\subseteq X\subseteq E$ and $I\in\I$. \end{itemize} Infinite matroids show the same properties as finite matroids. In particular, they possess bases ($\subseteq$-maximal independent sets), circuits (minimal dependent sets) and a natural notion of duality, in much of the same way as finite matroids, see~\cite{infaxioms}. In particular, $B\subseteq E$ is a base of $M$ if and only if $E\sm B$ is a base of the dual matroid $M^*$. We will use the normal matroid terminology. For instance, for any subset $X$ of the ground set $E$ of a matroid $M$ we will write $M|X$ for the restriction of $M$ to $X$, and we write $M\mm X=M|(E\sm X)$ for the matroid obtained by deleting the elements in $X$ from $M$. In~\cite{linkingthm}, the \emph{connectivity function} $\cf$ is extended to infinite matroids. For any $X\subseteq E(M)$ in a matroid $M$, choose a base $B$ of $M|X$ and a base $B'$ of $M\mm X$, and pick a set $F\subseteq B\cup B'$ so that $(B\cup B')\sm F$ is a base of $M$. Then we set $\cf_M(X):=|F|\in\mathbb N\cup\{\infty\}$ (we do not distinguish between different infinite cardinalities). We remark that the value $\cf_M(X)$ is independent of the choice of the bases and of the choice of $F$. Moreover, $F$ may be chosen to be a subset of $B$ or of $B'$, if necessary. This definition of the connectivity function has similar properties as the traditional connectivity function of a finite matroid. For finite matroids, the two notions coincide. More details and proof that $\cf$ is well-defined can be found in~\cite{linkingthm}. We call a partition $(X,Y)$ of $E$ a \emph{$\ell$-separation} if $\cf_M(X)\leq \ell-1$ and $|X|,|Y|\geq \ell$. The matroid $M$ is \emph{$k$-connected} if there exists no $\ell$-separation with $\ell |U|-1$. Then there exists a component $K$ of $(V[T_X],T_X\sm F)$ that contains no vertex of $U$, which means that $K$ is a component of $(V(G),T)$. However, as $G$ is connected the base $T$ of $\mfc(G)$ is the edge set of a spanning tree. This contradiction proves~\eqref{ma:eq:onecomp}. We now proceed by induction on $c(X)+c(Y)$, which is indeed a finite number as $|V[X]\cap V[Y]|$ is an upper bound for both $c(X)$ and $c(Y)$. Since the induction start is established by~\eqref{ma:eq:onecomp}, we may assume that $(V[X],X)$ has two components $K$ and $K'$. Insert a new edge $f$ between $K$ and $K'$, and set $G':=G+f$ and $X':=X\cup\{f\}$. Clearly, $(X',Y)$ is a partition of $E(G')$. Since $c(X')=c(X)-1$, the induction yields \[ \cf_{\mfc(G')}(X',Y) =|V[X]\cap V[Y]|-(c(X)-1)-c(Y)+1. \] We shall now show that $\cf_{\mfc(G')}(X',Y)=\cf_{\mfc(G)}(X,Y)+1$. Observe that then $T_X+f$ is (the edge set of) a maximal spanning forest of $(V[X'],X')\subseteq G'$. Moreover, $(T_X\sm F)\cup T_Y=((T_X+f)\sm (F\cup\{f\}))\cup T_Y$ is a spanning tree of $G'$, too. Thus \[ \cf_{\mfc(G')}(X,Y')=|F\cup\{f\}|=|F|+1=\cf_{\mfc(G)}(X,Y)+1, \] which finishes the proof. \end{proof} Next, let us show that the connectivity functions of $\mfc(G)$ and $\mc(G)$ coincide. For this, we need two results, one on spanning trees and one on the connectivity function under duality. \begin{theorem}\selfcite{duality}\label{acircST} Every connected finitely separable graph $G$ has a spanning tree whose closure in $\itop{G}$ is a topological spanning tree of $\itop{G}$. \end{theorem} \begin{lemma}\selfcite{linkingthm}\label{kapduallem} The connectivity function is invariant under duality, that is, $\cf_M(X)=\cf_{M^*}(X)$ for any subset $X$ of a matroid $M$. \end{lemma} \begin{theorem}\label{samecf} Let $G$ be a connected finitely separable graph. Then \[ \cf_{\mc(G)}(X)=\cf_{\mfc(G)}(X) \] for all $X\subseteq E(G)$. \end{theorem} \begin{proof} Let $B$ be the edge set of a spanning tree as in Theorem~\ref{acircST}. As then $B$ is as well the edge set of a topological spanning tree, we see that $B$ is simultaneously a base of $\mfc(G)$ and of $\mc(G)$. We use (IM) to extend $B\cap X$ to a base $B_X$ of $\mc(G)|X$. Since $B_X$ is independent in $\mfc(G)$ (but not necessarily a base) we may extend $B_X$ to a base $B'_X$ of $\mfc(G)|X$. Analogously, we define a base $B_{\overline X}\supseteq B\sm X$ of $\mc(G)\mm X$, and a base $B'_{\overline X}\supseteq B_{\overline X}$ of $\mfc(G)\mm X$. Therefore, setting $F':=(B'_X\cup B'_{\overline X})\sm B$, we obtain $\cf_{\mfc(G)}(X)=|F'|$. In a similar way, $\cf_{\mfc(G)}(X)=|F|$ for $F=(B_X\cup B_{\overline X})\sm B$. As $F\subseteq F'$, we deduce \[ \cf_{\mc(G)}(X)\leq \cf_{\mfc(G)}(X). \] Next, we observe that $E(G)\sm B$ is a base of $\mc^*(G)$ as well as of $\mfc^*(G)$. Since any independent set in $\mfc^*(G)$ is also independent in $\mc^*(G)$, we may use the same arguments as above to deduce that \( \cf_{\mfc^*(G)}(X)\leq \cf_{\mc^*(G)}(X). \) Finally, the invariance of the connectivity function under duality (Lemma~\ref{kapduallem}) yields $\cf_{\mfc(G)}(X)=\cf_{\mc(G)}(X)$. \end{proof} In particular, we have the following consequence: \begin{corollary}\label{sameconn} Let $G$ be a connected finitely separable graph, and let $k\geq 2$. Then $\mfc(G)$ is $k$-connected if and only if $\mc(G)$ is $k$-connected. \end{corollary} \section{Proof of main result} Let us recall the definition of Tutte-connectivity. A \emph{$\ell$-Tutte-separation} of a graph $G$ is a partition $(X,Y)$ of $E(G)$ so that $|X|,|Y|\geq \ell$ and so that $|V[X]\cap V[Y]|\leq \ell$. We say that a graph $G$ is \emph{$k$-Tutte-connected} if $G$ has no $\ell$-Tutte-separation for any $\ell