\documentclass[12pt]{article}
\usepackage{graphicx,latexsym,amsmath,amssymb,amsfonts,amsthm}
\newcommand{\phio  }{\mathop{\phi_{\rm o}}}        % oriented chromatic number
\newcommand{\Oscr  }{{\mathcal O}}
\DeclareMathOperator{\imbal}{imbal}
\newtheorem{thm}{\bf{Theorem}}%[chapter]
\newtheorem{lem}[thm]{\bf{Lemma}}
\newtheorem{note}[thm]{\bf{Note}}
%\newtheorem{def}[thm]{\bf{Definition}}
\newtheorem{conj}[thm]{\bf{Conjecture}}
\newtheorem{que}[thm]{\bf{Question}}
\newtheorem{prop}[thm]{\bf{Proposition}}
\newtheorem{cor}[thm]{\bf{Corollary}}
\newtheorem{obs}[thm]{\bf{Observation}}
\newtheorem{corollary}[thm]{Corollary}
\begin{document}
\title{Balancing Covectors}
\author{Laura Ch\'avez-Lomel\'i\\Affiliation \and Luis Goddyn\\SFU \and Winfried Hochst\"attler\\FernUniversit\"at in Hagen}
\maketitle
\begin{abstract}
  Recently, Goddyn, Hochst\"attler and Hlin\v{e}n\'{y} proved that the
  oriented flow number introduced by Goddyn, Tarsi and Zhang for an
  oriented matroid of rank $r$ is bounded by $14 r^2\ln r$. We
  improve this bound by showing that any oriented matroid without a
  coloop admits a reorientation such the imbalance of each covector is
  at most $3r-1$. In particular this yields a new upper bound for the
  oriented flow number.
\end{abstract}
\section{Introduction}
This paper is concerned with a generalization of
the graph chromatic number to geometric hyperplane
arrangements and to oriented matroids.
There are at least two ways to extend the
definition of graph chromatic number to
the class of oriented matroids \cite{GTZ, HN}.
%The invariant in \cite{GHH}$\phi_o(\mathcal O)$
%studied in \cite{GHH} is defined in terms
%of reorientations of a given oriented matroid $\mathcal O$.
One consequence of our main result is a significant improvement
in the upper bound derived in \cite{GHH} regarding 
the \emph{oriented flow number}.
Moreover, the argument in this paper is somewhat easier
than the probablisitic method used in \cite{GHH}. 
%

Although the main result uses the
%our result uses the slightly arcane
language of oriented matroids,
%as detailed in \cite{BLSW},
the specialization of the result to \emph{represented}
oriented matroids is easily accessible to a nonspecialist.

\begin{thm}
\label{thm-matrix}
Let $A$ be a real matrix of rank $r\ge 2$ such that deleting
any of its columns preserves its rank.
It is possible to multiply some columns of $A$ by $-1$ so that,
for every vector $\bold{t}$ in the row space of the resulting matrix,
the number of positive entries in $\bold{t}$ is at most $3r-2$
times the number of negative entries in $\bold{t}$.
\end{thm}

%PUT THIS LATER
%We remark that the bound $3r-2$ is probably not best possible.
%However, if each column of $A$ contains exactly one $1$ and one $-1$
%and no other nonzero entries,  then the statement of
%Theorem \label{thm-matrix}
%is false when $3r-1$ is replaced by~$\sqrt{2r}$.

Before stating the general result,
we review some terminology and notation for oriented matroids using
a variation of that used in the standard reference \cite{BLSW}.
A \emph{signed subset} $X$ of a ground set $E$ is a
subset $\underline{X} \subseteq E$ (the \emph{support} of $X$)
together with an ordered partition $(X^+, X^-)$ of $\underline{X}$,
where either of the parts may be empty.
%If $L$ is an ordinary subset of $E$,
%%%%%%%%%%I moved this to the next section%%%%%%%%5
%If $F \subseteq E$,
%%then $X \cap L$ denotes the signed subset with support
%then $X \vert_F$ denotes the
%%\emph{restricted}
%signed set with support $\underline{X} \cap L$
%and partition $(X^+ \cap L, X^- \cap L)$.
%%%%%%%%%%%%%%%%%%%%%%5
%
An oriented matroid $\mathcal{O}$ on the ground set $E$
can be presented as a set $\mathcal{L} = \mathcal{L}(\mathcal O)$
of \emph{covectors}.
Each covector in~$\mathcal{L}$ is a signed subset of~$E$,
and $\mathcal{L}$ satisfies the covector axioms listed in
\cite[\S 4.1.1]{BLSW}.
%%%added by Luis
A \emph{coloop} is a covector whose support has cardinality one.
%
If $F \subseteq E$,
then the \emph{reorientation} $\mathcal{O}_F$
of $\mathcal{O}$ specified by $F$
is the oriented matroid obtained from $\mathcal{O}$
by replacing each covector $(X^+,\,X^-)$
by $(X^+ \bigtriangleup (F\cap \underline{X}),\,X^- \bigtriangleup (F\cap\underline{X}))$,
where $\bigtriangleup$
is the symmetric difference operator.
%%%%%%%%%%%I moved this to the next section%%%%%%%%5
%%If $F \subseteq E$, then the
%The \emph{restriction} $\mathcal{O} \vert F$ of $\mathcal O$ to $F$ is
%the oriented matroid on ground set $F$
%%which is the result of replacing each covector
%%$(X^+,\,X^-)$ by $(X^+ \cap F,\,X^- \cap F)$.
%whose covectors are $\{ X \vert_F \,\mid\, X \in \mathcal{L}(\mathcal O)$.
%%%%%%%%%%%%%
%
The \emph{imbalance} of a signed subset $X$
is defined to be
\[
\imbal (X) = \min\left\{\frac{|\underline{X}|}{|X^+|},
                        \frac{|\underline{X}|}{|X^-|}\right\},
\]
if both $X^+$ and $X^-$ are non-empty. It is convenient to define the
imbalance of $X$ to be $\infty$ if exactly one of $X^+$, $X^-$ is empty
and $0$ if both are empty. 
%%%%%%%%%%%I moved this to the next section%%%%%%%%5
%It is well-known that any oriented matroid
%without coloops admits a {\em totally cyclic} reorientation. In a
%totally cyclically oriented matroid, any covector $X$ satisfies
%$X^+\ne \emptyset \ne X^-$, and hence $\imbal(X)\le |\underline{X}|$.
%%%%%%%%%%%%%
 
\begin{thm}\label{theo:w1}
Every oriented matroid $\mathcal{O}$ of rank $r\ge 2$ and having
no coloop has a reorientation
in which every covector
has imbalance at most $3r-1$.
\end{thm}
%
In case $r=1$, the best upper bound on imbalance is $3$.
Here $\mathcal O$ has only one covector, whose support has size, say, $s$.
An ``alternating reorientation'' yields an imbalance of $2$ if $s$ is even,
and $\frac{2s}{s-1} \le 3$ if $s$ is odd (see \cite{GHH} for details).

  %For an oriented matroid $\Oscr$ we denote by ${\mathcal C}^\ast(\mathcal O)$
  %its set of cocircuits.
We denote by ${\mathcal C}^\ast(\mathcal O)$
the set of (signed) cocircuits of an oriented matroid~$\mathcal{O}$.
Since cocircuits are precisely the covectors
  of minimal non-empty support, as a corollary of Theorem~\ref{theo:w1} we
  derive a considerable improvement on the upper bound of the oriented
  flow number of an oriented matroid without coloop. 
  For an oriented matroid ${\mathcal O}$ the {\em oriented flow
    number} $\phio({\mathcal O})$  is defined as
 \[ 
  \phio(\Oscr) := \min_{F\subseteq E} \, \max_{D \in {\mathcal C}^\ast (\Oscr_F)} \,
  \imbal(D).
 \]
 This invariant is introduced in \cite{GTZ} as a generalization of
 (the dual of) the circular chromatic number. In \cite{GHH} an upper
 bound of $14 r^2\ln r$ for an oriented matroid of rank $r$ was
 derived using the probabilistic method.
The method applied here is inspired by \cite{Jenny}.
 \begin{corollary}
   %Let ${\mathcal O}$ be an oriented matroid of rank $r$ without
   %coloops. Then $\phio(\Oscr)\le 3r-1$.
   Every oriented matroid $\mathcal{O}$ of rank $r$ and having
   no coloop satisfies $\phio(\Oscr)\le 3r-1$.
 \end{corollary}
% \begin{flushright}
%  {\qedsymbol}
% \end{flushright}




\section{Proof of Theorem~\ref{theo:w1}}
%%%%%%%%%%I moved this from the previous section%%%%%%%%
Here are a few more facts and definitions.
It is well-known that
any oriented matroid without coloops
admits a {\em totally cyclic} reorientation. In a
totally cyclically oriented matroid, every covector $X$ satisfies
$X^+\ne \emptyset \ne X^-$, and hence $\imbal(X)\le |\underline{X}|$.
%%%%%%%%%%%%
A circuit $C$ in a connected
matroid $M$ is {\em removable}, if $M\setminus C$ is still connected and the rank of $M\setminus C$ equals the rank of $M$. We
denote by $c(M)$ the {\em circumference}\/ of $M$,
which is the cardinality of the largest circuit in $M$.
\begin{lem}[Lemos, Oxley\cite{lemox}]\label{lem:lemox}
  Let $M$ be a connected matroid of rank $r$. If $|E(M)|\ge 3(r+1)-c(M)$, then $M$ has a removable
  circuit.
\end{lem}
%%%%%%%%%%%%%%%%%I moved ghe following from the previous section
The \emph{restriction} $\mathcal{O} \vert F$
of an oriented matroid $\mathcal O$ to a subset $F$ of its ground set
is the oriented matroid on ground set $F$
%which is the result of replacing each covector
%$(X^+,\,X^-)$ by $(X^+ \cap F,\,X^- \cap F)$.
whose covectors are $\{ X \vert_F \,\mid\, X \in \mathcal{L}(\mathcal O)\}$.
Here $X \vert_F$ denotes the
%\emph{restricted}
signed set with support $\underline{X} \cap F$
and partition $(X^+ \cap F, X^- \cap F)$.
%%%%%%%%%%%%
The following almost trivial observation will prove
helpful.
\begin{prop}\label{prop:1} Let $X$ be a signed subset of $E$ and
  $E=E_1\dot\cup\ldots\dot\cup E_k$ a partition.  Then
%\[\imbal(X)\le \max\{\imbal(X\cap E_1),\ldots,\imbal(X\cap E_k)\}.\]\flushright{\qedsymbol}
%\[
$
 \imbal(X)\le \max\{\imbal(X\vert_{E_1}),\ldots,\imbal(X\vert_{E_k})\}.
$
%\]
%\flushright{\qedsymbol}
\end{prop}

\begin{proof}[Proof of Theorem~\ref{theo:w1}.]
  Since no loop is contained in any covector, we may assume that $M$,
  the matroid underlying $\Oscr$, has no loops.  By
  Proposition~\ref{prop:1} we may furthermore assume that $M$ is
  connected.

  If $|E|\le 3r-1$, then $|E|\ge 2$ since $M$ has no coloops, and in
  any totally cyclic orientation of $\mathcal{O}$ we have
  $\imbal(X)\le |\underline{X}| \le |E|\le 3r-1$.

  We assume $|E|\ge 3r$.
%%%%%%%%%%%The following was replaced by the comment after the theorem statement
%If $r=1$, then $M$ is isomorphic to a graph
%%%%%That is not quite true...loops...
% with two vertices and $|E|$ edges and an alternating reorientation
% yields an imbalance of the unique covector of ${\mathcal O}$ of at
% most $\frac{2|E|}{|E|-1}\le 3$ (see \cite{GHH} for
% details). If $r\ge 2$ then $c(M)\ge 3$, hence
%%%%%%%%
Since $r\ge 2$, we have $c(M)\ge 3$ so
  \[|E|\ge 3(r+1)-c(M),\] and Lemma~\ref{lem:lemox} yields a removable
  circuit. Inductively, we find circuits $C_1,\ldots,C_k$ which are
  pairwise disjoint such that, setting $L= E\setminus\bigcup_{i=1}^k
  C_i$, the restriction $M\vert L$ is still connected of rank $r$ and
  $|L|<3r$. Next, we choose a reorientation $\tilde {\mathcal
    O}$ of ${\mathcal O}$ such that each of $\tilde {\mathcal
    O}\vert L, \tilde\Oscr\vert C_1,\ldots,\tilde\Oscr\vert C_k$ is totally cyclic.
  
  Now, let $X\in {\mathcal L}(\tilde{\mathcal O})$ be an
  arbitrary covector. We partition $X$ according to the above
  partition of the groundset $E=C_1\dot \cup \ldots \dot \cup
  C_k\dot\cup L$ into parts
  %\[X_L=X\cap L,\quad \mbox{ and }X_i=X\cap C_i\quad \mbox{ for }\quad
  \[X_L=X\vert_L,\quad \text{ and }X_i=X\vert_{C_i}\quad
   \mbox{ for } 1\le i \le k.\] 
 Each $X_i$ is a covector in $\Oscr\vert C_i$ and hence
  \[\imbal(X_i)\le |\underline{X_i}|\le |C_i|\le r+1 \qquad \mbox{ for }1\le i \le k\] 
and similarly
\[\imbal(X_L)\le |\underline{X_L}|\le |L|\le 3r-1.\]
Finally, Proposition~\ref{prop:1} yields
\[
\imbal(X)\le \max\left\{\imbal(X_L),\,\imbal(X_1),\ldots,\,\imbal(X_k)\right\}\le 3r-1.
\]
  \end{proof}

  \section{Concluding Remarks} Our proof suggests the definition of a
  seemingly new parameter related to the flow resp.\ chromatic number
 $$
 \phi_{\mathcal L}(\Oscr) := \min_{F\subseteq E} \,  \max_{X \in {\mathcal L}(\Oscr_F)} \,
 \imbal(X)
 $$
 which measures the possibility to balance all covectors in an
 oriented matroid. Clearly, $\phi_{\mathcal L}\ge \phi_o$.
  It is not difficult to compute that \[\phi_{\mathcal
    L}(\Oscr^\ast(K_n))=\binom{n}{2}\approx r+\sqrt{2r}\]
    whereas
\[\phi_o(\Oscr^\ast(K_n))=\chi(K_n)=n\approx \sqrt{2r}\]
where $r=\binom{n}{2}-n+1$ is the rank of the cographic oriented
matroid $\Oscr^\ast(K_n)$ of the complete graph on $n$ vertices.
Hence, our bound for $\phi_{\mathcal L}(\Oscr)$ is within a linear
factor of the best upper bound, wheras it may be the case that
$\phi_o(\Oscr)=O(\sqrt{r}) \mbox{ (see \cite{GHH}).}$ 

  \bibliographystyle{amsplain} \bibliography{balancing1}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: