\documentclass{amsart} \usepackage{ifthen} \def\style{} \ifthenelse{\equal{\style}{preprint}}{ \usepackage{dmo_preprint} }{} \usepackage{amssymb} \newcommand{\hide}[1]{} %\newcommand{\R}{{\cal R}} %Use only if amsfonts are unavailable \newcommand{\R}{{\mathbb R}} \newcommand{\nullsp}{{\rm nullsp}} \newcommand{\ar}{{\rm arng}} \newcommand{\s}{\scriptscriptstyle} \newcommand{\deltaplus }{\delta^{\mbox{\raisebox{1pt}{$\s +$}}}\!} \newcommand{\deltaminus}{\delta^{\mbox{\raisebox{1pt}{$\s -$}}}\!} % Test: $\delta^+ X$, $\deltaplus X$, $\delta^- X$, $\deltaminus X$, %\newtheorem{lemma}{\sc Lemma}[section]% \newtheorem{lemma}{\sc Lemma}% Sectionless Paper \newtheorem{theorem}[lemma]{\sc Theorem}% \newtheorem{proposition}[lemma]{\sc Proposition}% \newtheorem{corollary}[lemma]{\sc Corollary}% \newtheorem{claim}[lemma]{\sc Claim}% \newtheorem{conjecture}[lemma]{\sc Conjecture}% \newtheorem{remark}[lemma]{\sc Remark}% \newtheorem{note}[lemma]{\sc Note}%G \newtheorem{algorithm}[lemma]{\sc Algorithm}% \newtheorem{example}[lemma]{\sc Example}% \newtheorem{observation}[lemma]{\sc Observation}% \newtheorem{definition}[lemma]{\sc Definition}{}% \newtheorem{question}[lemma]{\sc Question}{}% \newtheorem{numbered}[lemma]{\sc}% %%%%%% Choose end-of-proof symbol \newcommand{\QED}{{\rule[0pt]{4pt}{8pt}}} % Solid Box \newenvironment{proofT}{\noindent{\sc Proof of Theorem \ref{main}.}}{\hfill \QED\\} \newenvironment{sketch}{\noindent{\sc Sketch of proof.}} {\hfill \QED \\} %\voffset=-1in \setlength{\itemsep}{6pt} \topsep=0in \partopsep=0in \setlength{\evensidemargin}{.22truein} \setlength{\oddsidemargin}{.22truein} \setlength{\textwidth}{6.6truein} \addtolength{\topmargin}{-0.45truein} \setlength{\textheight}{8.8truein} \setlength{\headheight}{0in} %\setlength{\headsep}{1in} \setlength{\parindent}{1pc} \setlength{\hoffset}{-0.4truein} \title{{Nowhere-zero flows in regular matroids and Hadwiger's Conjecture}} \author{ Luis A.\ Goddyn \and Winfried Hochst\"attler } \dedicatory{To the memory of Reinhard B\"orger} \date{} \begin{document} \ifthenelse{\equal{\style}{preprint}}{ \DMOmathsubject{05C15, 05B35, 52C40} \DMOkeywords{nowhere zero flow, regular matroid, chromatic number, flow number, total unimodularity} \DMOtitle{031.13}{Nowhere-zero flows in regular matroids and Hadwiger's Conjecture} {Luis A.\ Goddyn \\ Winfried Hochst\"attler}{goddyn@sfu.ca\\winfried.hochstaettler@fernuni-hagen.de} }{} \maketitle \begin{abstract} We present a tool that shows, that the existence of a $k$-nowhere-zero-flow is compatible with 1-,2- and 3-sums in regular matroids. As application we present a conjecture for regular matroids that is equivalent to Hadwiger's conjecture for graphs and Tuttes's 4- and 5-flow conjectures. \vspace{2ex} \noindent {\sc Keywords:} {\it nowhere zero flow, regular matroid, chromatic number, flow number, total unimodularity} \end{abstract} \maketitle \vspace{1ex} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} A (real) matrix is {\it totally unimodular (TUM)\/} if each subdeterminant belongs to $\{0,\pm 1\}$. Totally unimodular matrices enjoy several nice properties which give them a fundamental role in combinatorial optimization and matroid theory. In this note we prove that the TUM possesses an attractive property. Let $S \subseteq \mathbb R$, and let $A$ be a real matrix. A column vector $f $ is a \emph{$S$-flow of $A$} if $Af=0$ and every entry of $f$ is a member of $\pm S$. For any additive abelian group $\Gamma$ use the notation $\Gamma^* = \Gamma \setminus \{0\}$. For a TUM $A$ and a column vector $f$ with entries in $\Gamma$, the product $Af$ is a well defined column vector with entries in $\Gamma$, by interpreting $(-1)\gamma$ to be the additive inverse of $\gamma$. %For $S \subset \Gamma$, $f$ is an $S$-flow if $Af=0$ and the entries of $f$ belong to $\pm S$. It is convenient to use the language of matroids. A regular oriented matroid $M$ is an oriented matroid that is representable $M=M[A]$ by a TUM matrix~$A$. Here the elements $E(M)$ of $M$ label the columns of $A$. Each (signed) cocircuit $D=(D^+, D^-)$ of $M$ corresponds to a $\{0,\pm 1\}$-valued vector in the row space of $A$ and having minimal support. The $+1$-entries in this vector constitute the sets $D^+$. It is known \cite[Prop.\ 1.2.5]{white_combinatorial_1987} that two TUMs represent the same oriented matroid if and only if the first TUM can be converted to the second TUM by a succession of the following operations: multiplying a row by $-1$, adding one row to another, deleting a row of zeros, and permuting columns (with their labels). %We often consider $f$ to be a function $f: E \to \Gamma$ For $S \subseteq E(M)$ we use the notation $f(S) = \sum_{e \in S} f(e)$. Let $M = M[A]$ be the regular oriented matroid represented by the TUM $A$. Let $S \subseteq \Gamma$ where $\Gamma$ is an abelian group. An \emph{$S$-flow} of $M$ is a function $f : E(M) \to S$ for which $A f = 0$, where $f$ is interpreted to be a vector indexed by the column labels of $A$. For any $S \subseteq \Gamma$ we say that a regular matroid $M$ has an $S$-flow if any of the TUMs that represent $M$ has an $S$-flow. By the previous paragraph, this property of $M$ is well defined. Since the rows of a TUM $A$ generate the cocycle space of $M = M[A]$, we have that a function $f : E(M) \to \Gamma$ is a flow if and only if for every signed cocircuit $D = (D^+, D^-)$ we have that $f(D)=0$ where $f(D)$ is defined to equal $f(D^+)-f(D^-)$. Let $\Gamma$ be a finite abelian group. Let $M$ be a regular oriented matroid, and let $F \subseteq E(M)$ and let $f : F \to \Gamma$. Let $\tau_\Gamma(M,f)$ denote the number of $\Gamma^*$-flows of $M$ which are extensions of $f$. \begin{theorem} \label{thm-counting} Let $M$ be an regular oriented matroid. Let $F \subseteq E(M)$ and let $f , f': F \to \Gamma$. % and $f': F \to \Gamma$. Suppose that for every minor $N$ of $M$ satisfying $E(N) = F$, we have that $f$ is a $\Gamma$-flow of $N$ if and only $f'$ is a $\Gamma$-flow of $N$. Then $\tau_\Gamma(M,f) = \tau_\Gamma(M,f')$. \end{theorem} \begin{proof} We proceed by induction on $d=|E\setminus F|$. If $d=0$, then there is nothing to prove. Otherwise let $e \in E \setminus F$. If $e$ is a coloop of $M$, then $\tau_\Gamma(M,f) = \tau_\Gamma(M,f')=0$. If $e$ is a loop of $M$, then by applying induction to $M\setminus e$, we have $\tau_\Gamma(M,f) = \tau_\Gamma(M,f')=(|\Gamma|-1)\tau_\Gamma(M\backslash e,f) $. Otherwise we apply Tutte's deletion/contraction formula \cite{arrowsmith_enumeration_1982} and induction to get \begin{align*} \tau_\Gamma(M,f')=\tau_\Gamma(M / e,f')-\tau_\Gamma(M\backslash e,f') =\tau_\Gamma(M / e,f)-\tau_\Gamma(M\backslash e,f)=\tau_\Gamma(M,f). \end{align*} \end{proof} \begin{corollary} \label{cor-cocircuit} Let $D$ be a positively oriented cocircuit of a regular oriented matroid $M$. Let $f , f': D \to \Gamma$. Suppose that for every $S \subseteq D$ we have that $f(S) = 0$ if and only if $f'(S)=0$. Then $\tau_\Gamma(M,f) = \tau_\Gamma(M,f')$. \end{corollary} \begin{proof} Let $N$ be a minor of $M$ satisfying $E(N)=D$. Then $E(N)$ is a disjoint union $\bigcup_i D_i$ of positively oriented cocircuits of $N$ \cite[Prop.\ 9.3.1]{oxley}. Thus $f$ is a $\Gamma*$-flow of $N$ if and only if $f$ has no zeros, and $f(D_i)=0$ for each~$i$. The result follows from Theorem \ref{thm-counting}. \end{proof} \begin{corollary} \label{cor-13} Let $M$ be a regular oriented matroid which has a $\Gamma^*$-flow $f$. \begin{enumerate} \item Let $e \in E(M)$ and $\gamma \in \Gamma^*$. Then $M$ has a $\Gamma^*$-flow $f'$ with $f'(e) = \gamma$. \item Let $D$ be a signed cocircuit of $M$ of cardinality three. Let $f' : D \to \Gamma^*$ satisfy $f'(D)=0$. Then $f'$ extends to a $\Gamma^*$-flow of $M$. \end{enumerate} \end{corollary} \begin{proof} \begin{enumerate} \item In any minor $N$ with $E(N)=\{e\}$, both $f'$ and $f \upharpoonright_{\{e\}}$ are $\Gamma^*$-flows of $N$ if and only if $N$ is a loop. Thus by Theorem \ref{thm-counting} $\tau_\Gamma(M,f')=\tau_\Gamma(M ,f) > 0$. \item Let $S\subset D$. For any $e \in D$ we have $f'(D\setminus \{e\}) = f'(D) - f'(e) = -f'(e) \ne 0$. Therefore $f'(S)=0$ if and only if $S=D$. Since $f$ is a $\Gamma$-flow and $D$ is a positively oriented cocircuit of $D$ we have $f(D)=0$. Since $f(e) \ne 0$ for $e\in D$ we again have that $f(S)=0$ if and only if $S=D$. It follows from Theorem \ref{thm-counting} that $\tau_\Gamma(M,f')=\tau_\Gamma(M ,f) > 0$. \end{enumerate} \end{proof} A \emph{$k$-nowhere zero flow ($k$-NZF)} of a regular oriented matroid $M$ is an $S$-flow of $M$ for $S = \{ 1,2,\dots, k-1\} \subset\mathbb R$. We frequently use the following observation of Tutte \cite{Tutte:dichromate}. \begin{proposition} \label{prop-kNZF} Let $\Gamma$ be an abelian group of order $k$, and let $S = \{ 1,2,\dots, k-1\} \subset \mathbb R$. Then $M$ has a $k$-NZF if and only if $M$ has a $\Gamma^*$-flow. In particular, the existence of a $\Gamma ^*$-flow in $M$ depends only on $|\Gamma|$. \end{proposition} A key step in the proof of Proposition \ref{prop-kNZF} is the conversion of a $\Gamma^*$-flow into a $k$-NZF, where $\Gamma$ is the group of integers modulo $k$. By modifying this argument, one can show that the statement of Corollary \ref{cor-13} remains true if each occurrence of the symbol $\Gamma^*$ is replaced by the set of integers $S=\{ \pm1, \pm2, \dots , \pm(k-1)\}$. We omit the proof of this fact, as it is not needed in this paper. %%%%%%%%%%%%%%% \section{Seymour decomposition} We provide here a description of Seymour's decomposition theorem for regular oriented matroids. We refer the reader to \cite{matroiddecomposition} for further details. We first describe three basic types of regular oriented matroids. A oriented matroid is \emph{graphic} if it can be represented by the $\{0,\pm 1\}$-valued vertex-edge incidence matrix of a directed graph, where loops and multiple edges are allowed. Any $\{0,\pm 1\}$-valued matrix which whose rows span the nullspace of a network matrix is called a {\it dual network matrix\/}. Dual network matrices are also TUM, and an oriented matroid is \emph{cographic} is it is representable by a dual network matrix. The third class consists of all the all the orientations of one special regular matroid $R_{10}$. Every orientation of $R_{10}$ can be represented by the matrix $[I \vert B]$ where $B$ is obtained by negating a subset of the columns of the following matrix.%the one of the following two matrices. \begin{align} \label{eq-R10} \left[ \begin{matrix} +&0&0&+&-\\ -&+&0&0&+\\ +&-&+&0&0\\ 0&+&-&+&0\\ 0&0&+&-&+ \end{matrix} \right] %, %\qquad %\left[ \begin{matrix} %+&+&+&+&+\\ %+&+&+&0&0\\ %+&0&+&+&0\\ %+&0&0&+&+\\ %0&0&0&0&+ %\end{matrix} \right]. \end{align} Here ``$+$'' and ``$-$'' respectively denote $+1$ and $-1$. %Seymour \cite{Sey1} showed that any TUM may be obtained from a list %of network matrices, dual network matrices and two special matrices %by a sequence of operations called $k$-sums, $k=1,2,3$, %and by ``pivotting'' and multiplying some rows and columns by $-1$. %See Schrijver \cite{Schrijver} for details. Let $M_1$, $M_2$ be regular oriented matroids. If $E(M_1)$ and $E(M_2)$ are disjoint, then the \emph{1-sum} $M_1 \oplus_1 M_2$ is just the direct sum of $M_1$ and $M_2$. The signed cocircuits of $M_1 \oplus_1 M_2$ are the signed subsets of $E(M_1) \cup E(M_2)$ which are signed cocircuits of either $M_1$ or $M_2$. % If $M_1 \cap M_2 = \{e\}$ and $e$ is neither a loop nor a coloop in each $M_i$, then the \emph{2-sum} $M_1 \oplus_2 M_2$ has element set $E(M_1) \Delta E(M_2)$, where ``$\Delta$'' is the symmetric difference operator. A signed cocircuit is a signed subset of $E(M_1 \oplus_2 M_2)$ that is either a signed cocircuit of $M_1$ or $M_2$, or is a signed set of the form \begin{align} \label{eq-ksum} D = (D_1^+ \Delta D_2^+, D_1^- \Delta D_2^-) \end{align} where each $(D_i^+, D_i^-)$ is a signed cocircuit of $M_i$, and $e \in (D_1^+ \cap D_2^+) \cup (D_1^- \cap D_2^-)$. % If $M_1 \cap M_2 = B$ and $B = (B^+, B^-)$ is a signed cocircuit of cardinality $3$ in each $M_i$, then the \emph{3-sum} $M_1 \oplus_3 M_2$ has element set $E(M_1) \Delta E(M_2)$. A signed cocircuit is a signed subset of $E(M_1 \oplus_3 M_2)$ that is either a signed cocircuit of $M_1$ or $M_2$, or a signed subset of the form \eqref{eq-ksum} where each $(D_i^+, D_i^-)$ is a signed cocircuit of $M_i$, %with $B^+ \subseteq (D_1^+ \cap D_2^+)$ and $B^- \subseteq (D_1^- \cap D_2^-)$.. with $D_1 \cap D_2 = \emptyset$ and $(B^+,B^-)$ equals one of the following ordered pairs: \begin{align*} ( \; (D_1^+ \cap B^+) \cup (D_2^+ \cap B^+)\, , \;(D_1^- \cap B^-) \cup (D_2^- \cap B^-) \; )\phantom{.}\\ ( \; (D_1^- \cap B^+) \cup (D_2^- \cap B^+)\, , \;(D_1^+ \cap B^-) \cup (D_2^+ \cap B^-) \; ). \end{align*} The oriented version of Seymour's decomposition theorem \cite{matroiddecomposition} and can be derived from \cite[Theorem 6.6]{honi}. \begin{theorem} \label{thm-decomp} Every regular oriented matroid $M$ can be constructed by means of repeated application of $k$-sums, $k=1,2,3$, starting with oriented matroids, each of which is isomorphic to a minor of $M$ and each of which is either graphic, cographic, or an orientation of $R_{10}$. \end{theorem} We note that Schriver \cite{Schrijver} states an equivalent version of Theorem \ref{thm-decomp} in terms of TUMs, that requires a second representation of $R_{10}$ in \eqref{eq-R10} due to his implicit selection of a basis. Here is the main tool of this paper, which we employ in two subsequent applications. \begin{theorem} \label{thm-main} Let $k \ge 2$ be an integer and let $\mathcal M$ be a set of regular oriented matroids that is closed under minors. If every graphic and cographic member of $\mathcal M$ has a $k$-NZF, then every matroid in $M$ has a $k$-NZF. \end{theorem} \begin{proof} Let $M \in \mathcal M$. We proceed by induction on $|E(M)|$. If $M$ is an orientation of $R_{10}$, then $M$ has a $2$-NZF since $R_{10}$ is a disjoint union of circuits, and each circuit is the support of a $\{0,\pm 1\}$-flow in $M$. If $M$ is graphic or cographic, then we are done by assumption. Otherwise, by Theorem \ref{thm-decomp}, $M$ has two proper minors $M_1$, $M_2 \in \mathcal M$. such that $M = M_1 \oplus_i M_2$, for some $i= 1,2,3$. %, and $M_1$ is either graphic, or cographic, or isomorphic to an orientation of $R_{10}$. By induction, each $M_i$ has a $k$-NZF. Thus by Proposition \ref{prop-kNZF}, both minors have a $\Gamma^*$-flow where $\Gamma$ is any fixed group of order $k$. By Corollary \ref{cor-13}, we may assume that these $\Gamma ^*$-flows coincide on $M_1 \cap M_2$. Hence the union of these functions is a well defined $\Gamma^*$-flow on $M$ and we are done by another application of Proposition \ref {prop-kNZF}. \end{proof} \section{Tutte's flow Conjectures and Hadwiger's Conjecture} In this section we will present a conjecture that unifies two of Tutte's Flow Conjectures and Hadwiger's Conjecture on graph colorings. \begin{conjecture}[H(k)\cite{Hadwiger}] \label{conj:1} If a simple graph is not $k$-colorable, then it must have a $K_{k+1}$-minor. \end{conjecture} While H(1) and H(2) are trivial, Hadwiger proved his conjecture for $k=3$ and pointed out that Klaus Wagner proved that H(4) is equivalent to the Four Color Theorem~\cite{wagner_ber_1937,appel_every_1976,robertson_four-colour_1997}. Robertson, Seymour and Thomas~\cite{RST} reduced H(5) to the Four Color Theorem. The conjecture remains open for $k\ge 6$. Tutte~\cite{Tutte:dichromate} pointed out that the Four Color Theorem is equivalent to the statement that every planar graph admits an 4-NZ-flow. Generalizing this to arbitrary graphs he conjectured that \begin{conjecture}[Tutte's Flow Conjecture \cite{Tutte:dichromate}]\label{conj:2} There is a finite number $k \in \mathbb{N}$ such that every bridgeless graph admits a $k$-NZ-flow. \end{conjecture} and moreover that \begin{conjecture}[Tutte's Five Flow Conjecture \cite{Tutte:dichromate}]\label{conj:3} Every bridgeless graph admits a $5$-NZ-flow. \end{conjecture} Note that the latter is best possible as the Petersen graph does not admit a $4$-NZ-flow. Conjecture~\ref{conj:2} has been proven independently by Kilpatrick~\cite{Kilpatrick} and Jaeger~\cite{Jaeger} with $k=8$ and improved to $k=6$ by Seymour~\cite{SeymourNZ6}. Conjecture~\ref{conj:3} has a sibling which is a more direct generalization of the Four Color Theorem. \begin{conjecture}[Tutte's Four Flow Conjecture \cite{tutte2,tutte3}]\label{conj:4} Every graph without a Petersen-minor admits a $4$-NZ-flow. \end{conjecture} In \cite{tutte2,tutte3} Tutte cited Hadwiger's conjecture as a motivating theme and pointed out that while \begin{quote} ``Hadwiger's conjecture asserts that the only irreducible chain-group which is graphic is the coboundary group of the complete 5-graph'' \end{quote} Conjecture~\ref{conj:4} means that \begin{quote} ``the only irreducible chain-group which is cographic is the cycle group of the Petersen graph.'' \end{quote} The first statement refers to the case where the rows of a totally unimodular matrix $A$ consist of a basis of signed characteristic vectors of cycles of a digraph. Combining these we derive the following formulation in terms of regular matroids. First let us call any integer combination of the rows of $A$ a {\em coflow}. Clearly, by duality resp.\ orthogonality, flows and coflows yield the same concept in regular matroids. Note that the existence of a $k$-NZ-coflow in a graph is equivalent to $k$-colorability ~\cite{tutte2}. \begin{conjecture}[Tutte's Four Flow Conjecture, matroid version]\label{conj:5} A regular matroid that does not admit a $4$-NZ-flow has either a minor isomorphic to the cographic matroid of the $K_5$ or a minor isomorphic to the graphic matroid of the Petersen graph. \end{conjecture} Equivalently, we have \begin{conjecture}[Hadwigers's Conjecture for regular matroids and $k=4$] \label{conj:5a} A regular matroid that is not $4$-colorable, i.e.\ that does not admit a NZ-$4$-coflow, has a $K_5$ or a Petersen-dual as a minor. \end{conjecture} Some progress concerning this Conjecture was made by Lai, Li and Poon using the Four Color Theorem \begin{theorem}[\cite{lai_nowhere_2005}] A regular matroid that is not $4$-colorable has a $K_5$ or a $K_5$-dual as a minor. \end{theorem} Tutte's Five Flow Conjecture now suggests the following matroid version of Hadwiger's conjecture: \begin{conjecture}[Hadwigers's Conjecture for regular matroids and $k\ge 5$]\label{conj:6} If a regular matroid is not $k$-colorable for $k\ge 5$, then it must have a $K_{k+1}$-minor. \end{conjecture} \begin{theorem}\label{theo:15} \begin{enumerate} \item Conjecture \ref{conj:5} is equivalent to Conjecture \ref{conj:4}. \item Conjecture \ref{conj:6} for $k=5$ is equivalent to Conjecture \ref{conj:3}. \item Conjecture \ref{conj:6} for $k\ge 6$ is equivalent to Conjecture \ref{conj:1}. \end{enumerate} \end{theorem} \begin{proof} \begin{enumerate} \item By Weiske's Theorem~\cite{Hadwiger} a graphic matroid has no $K_5^\ast$-minor. Hence Conjecture~\ref{conj:5} clearly implies Conjecture~\ref{conj:4}. The other implication is proven by induction on $|E(M)|$. Consider a regular matroid $M$, that is not $4$-colorable, i.e.\ that does not admit a NZ-$4$-coflow. Clearly, $M$ cannot be isomorphic to $R_{10}$. If $M$ is graphic, it must have a $K_5$-minor by the Four Color Theorem~\cite{appel_every_1976,robertson_four-colour_1997} and an observation of Klaus Wagner~\cite{wagner_ber_1937}. If $M$ is cographic it must have a Petersen-dual-minor by Conjecture~\ref{conj:4}. Otherwise, by Theorem \ref{thm-decomp}, $M$ has two proper minors $M_1$, $M_2 \in \mathcal M$. such that $M = M_1 \oplus_i M_2$, for some $i= 1,2,3$ and at least one of them is not $4$-colorable by Theorem~\ref{thm-main}. Using induction we find either a Petersen-dual-minor or a $K_5$-minor in one of the $M_i$ and hence also in $M$. Thus, Conjecture~\ref{conj:4} implies Conjecture~\ref{conj:5}. \item We proceed as in the first case using $H(5)$ for graphs~\cite{RST} instead of the Four Color Theorem. \item We proceed similar to the first case, with only a slight difference in the base case. If $M$ is graphic, it must have a $K_{k+1}$-minor by Conjecture~\ref{conj:1}. $M$ cannot be cographic by Seymour's 6-flow-theorem~\cite{SeymourNZ6}. \end{enumerate} \end{proof} \begin{remark} James Oxley pointed that Theorem~\ref{theo:15} could also be proven using splitting formulas for the Tutte polynomial (see e.g.\ ~\cite{Andrzejak}), Seymour's decomposition and the fact that the flow number as well as the chromatic number are determined by the smallest non-negative integer non-zero of certain evaluations of the Tutte polynomial. \end{remark} %%%%%%%%%%%%% \bibliographystyle{amsplain} \bibliography{hadwiger} \end{document} By statement {\it 3.}~of Proposition \ref{prop-TUMprops} below, a similar theorem holds by replacing ``nullspace'' by ``rowspace'' in Theorem \ref{thm-main}. All matrices are real-valued unless otherwise stated. Let $\nullsp(A) = \{ f : Af=0\}$ denote the nullspace of a matrix $A$. A vector $f=(f_i:i\in I)$ is {\it nowhere-zero\/} if $f_i \ne 0$ for all $i\in I$. % Any $\{0,\pm 1\}$-valued matrix which whose rows are in the nullspace of a network matrix is called a {\it dual network matrix\/}. By Proposition \ref{prop=TUMprops}, dual network matrices are also TUM. Seymour \cite{Sey1} showed that any TUM may be obtained from a list of network matrices, dual network matrices and two special matrices by a sequence of operations called $k$-sums, $k=1,2,3$, and by ``pivotting'' and multiplying some rows and columns by $-1$. See Schrijver \cite{Schrijver} for details. We assume familiarity with graphs and basic matroid theory. \section{Basic Facts} \begin{proposition} \label{prop-TUMprops} If $A$ is TUM. Then any of the following are also TUM. \begin{enumerate} \item $A^T$ \item Any matrix obtained by multiplying a row or column by $-1$. \item The concatenated matrices $[A|I]$ and $[A|-A]$. \item Any $\{0,\pm 1\}$-valued matrix such that $AB=0$. \end{enumerate} \end{proposition} \label{prop-dualTUM} % \begin{proposition} \label{prop-floorceil} Let $A$ be TUM and let $f = (f_i: i \in I) \in \nullsp(A)$. Then there exists $f'= (f'_i: i \in I) \in \nullsp(A)$ such that $f'_i \in \{ \lfloor f_i \rfloor, \lceil f_i \rceil\}$ for all $i \in I$. \end{proposition} % \begin{theorem} \label{thm-main} Let $A$ be a TUM. Let $S\subseteq \mathbb R\setminus \{0\}$ satisfy $|S| < k$. If $A$ has an $S$-flow, then $A$ has an $S'$-flow, where %$S'=\{\pm 1,\pm 2,\ldots,\pm (k-1)\}$. $S'=\{1,2,\dots, k-1\}$. \end{theorem} \end{document}