\documentclass{ajour} % % First version by Hlineny Spring 01 % Rewrite by goddyn Spring 03 % Small changes by hochstaettler spring 03 % Final version by Hlineny April 03 % Minor changes by hochstaettler April 03 %%%%%%%%%%%% % First revision by hochstaettler August 04 % Second minor revision by Hlineny August 04 % Third tiny revision by hochstaettler August 04 % Minor revision by Goddyn August 25 % \usepackage{latexsym} \usepackage{amssymb} % LUIS: I have changed to the modern graphicx package %\usepackage{epsf} \usepackage{graphicx} % The following does not work with ajour.cls, already defined! %\newtheorem{theorem}{Theorem}[section] %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{conjecture}[theorem]{Conjecture} % Luis: % After much fooling around, and reading latex.ltx % I managed to number things consecutively without modifying ajour.cls % The only side effect I see: Conjectures are now in italics (so what?) % Alternatively, one can modify ajour.cls in obvious ways % (search for "newtheorem") \makeatletter \global\@namedef{lemma}{\@thm{theorem}{Lemma}}% \global\@namedef{proposition}{\@thm{theorem}{Proposition}}% \global\@namedef{corollary}{\@thm{theorem}{Corollary}}% \global\@namedef{conjecture}{\@thm{theorem}{Conjecture}}% \makeatother % why emails are not in \tt as usual? \let\emx=\email\def\email#1{\emx{\ttfamily\small #1}} \begin{document} \sloppy %Luis: proposes - now accepted and final... % - but referee does not agree!! new... %LUIS: I changed it back to what the referee suggests % because I do not like the parenthetical addition. % I do not feel strongly about it so change it back if you like. \title{Balanced Signings and the Chromatic Number of Oriented Matroids %\title{Balanced Signings of Oriented Matroids \mbox{(and the chromatic number)} \\ {\rm\normalsize (revision date: \today)} } \author{Luis Goddyn\thanks{Supported in part by the National Sciences and Engineering Research Council of Canada, and the Pacific Institute for the Mathematical Sciences.}} \affil{Department of Mathematics\\ Simon Fraser University\\ Burnaby, BC, Canada} \email{goddyn@math.sfu.ca} \and \author{Petr Hlin\v{e}n\'y% \thanks{Partial support by grant ****** TBA\dots} \hbox to0pt{~\footnotesize(corresponding author)} } \affil{ Department of Computer Science, \\FEI V\v SB -- Technical University of Ostrava, \\17.~listopadu 15, 708\,33 Ostrava, Czech Republic \\{and}\\ Institute of Theoretical Computer Science% \thanks{Supported by Ministry of Education of the Czech Republic as project LN00A056.} \\ Charles University, Prague, Czech Republic} \email{petr.hlineny@vsb.cz} % \email{hlineny@member.ams.org} \and \author{Winfried Hochst\"attler} \affil{Department of Mathematics\\ BTU Cottbus,\\ Cottbus, Germany} \email{hochst@math.tu-cottbus.de} \authorrunninghead{L.~Goddyn, P.~Hlin\v{e}n\'y, W.~Hochst\"attler} % \authorrunninghead{\textbf{DRAFT: NOT FOR DISTRIBUTION}} \titlerunninghead{Balanced Signings of Oriented Matroids} % \titlerunninghead{\textbf{DRAFT: NOT FOR DISTRIBUTION}} %\date{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Author's definitions \newcommand{\comment}[1]{} % used for comments to the coauthors \newcommand{\DEF}[1]{\emph{#1}} % used for definitions, eg. \DEF{flow} %\newcommand{\centeredgraphics}[1]{\begin{center}\hskip 0.1mm\epsffile{#1}\ % \end{center}} % Centering the EPS graphics inside the FIGURE environment % % Use for figures as follows: % \begin{figure}[htb] % \epsfxsize=11.5truecm %optional % \centeredgraphics{FileName1.eps} % \caption{Text of the caption} % \label{fig:1} % \end{figure} \newcommand{\chio }{\mathop{\chi_{\rm o}}} % oriented chromatic number \newcommand{\phio }{\mathop{\phi_{\rm o}}} % oriented chromatic number %Luis: I did not like the bold font, nor am thrilled with my proposed change. \newcommand{\supp }{ {\hbox{{\rm supp}}}} % imbalance function \newcommand{\imbal}{ {\hbox{{\rm imbal}}}} % imbalance function \newcommand{\girth}{\mathop{\hbox{{\rm girth}}}} % girth function \newcommand{\cogirth}{\mbox{{\rm cogirth}}} % cogirth function \newcommand{\ocb }{\mbox{{\rm ocb}}} % odd cogirth number \newcommand{\RR }{\ensuremath{\mathbb R}} % real numbers \newcommand{\NN }{\ensuremath{\mathbb N}} % natural numbers \newcommand{\ZZ }{\ensuremath{\mathbb Z}} % integers %\newcommand{\OO }{\ensuremath{\mathbb O}} % the circle group \renewcommand{\epsilon}{\varepsilon} % Petr: The following is used for reorientation \subset E, instead of F \newcommand{\Ror}{\ensuremath{I}} % edge subset for reorientation \newcommand{\vC }{{\vec C}} \newcommand{\vB }{{\vec B}} \newcommand{\Cscr }{{\cal C}} \newcommand{\Bscr }{{\cal B}} \newcommand{\vCscr }{{\vec\Cscr}} \newcommand{\vBscr }{{\vec\Bscr}} \newcommand{\Pscr }{{\cal P}} \newcommand{\Oscr }{{\cal O}} \newcommand{\Sscr }{{\cal S}} \newcommand{\Nscr }{{\cal N}} \newcommand{\prob}{\mathop{\rm Prob}} \newcommand{\QED}{\hspace*{\fill}\rule[1ex]{0.6ex}{1.9ex}} \newcommand{\rk}{\mathop{\rm rk}} \newcommand{\bv}{\mbox{\boldmath{$v$}}} \newcommand{\bt}{\mbox{\boldmath{$t$}}} \newcommand{\noproof}{\par\vspace*{-\bigskipamount}\endproof} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\maketitle \abstract{ We consider the problem of reorienting an oriented matroid so that all its cocircuits are `as balanced as possible in ratio'. It is well known that any oriented matroid having no coloops has a \DEF{totally cyclic reorientation}, a reorientation in which every signed cocircuit $B = \{B^+, B^-\}$ satisfies $B^+, B^- \neq \emptyset$. We show that, for some reorientation, every signed cocircuit satisfies $$ 1/f(r) \le |B^+|/|B^-| \le f(r), $$ where $f(r) \le 14\,r^2\ln(r)$, and $r$ is the rank of the oriented matroid. In geometry, this problem corresponds to bounding the discrepancies (in ratio) % \DEF{log-discrepancies} % $|\ln |B^+| - \ln |B^-||$ that occur among the Radon partitions of a dependent set of vectors. For graphs, this result corresponds to bounding the chromatic number of a connected graph by a function of its Betti number (corank) $|E|-|V|+1$. } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\subjclass{Primary 05C10; 05C15} \keywords{Oriented matroid, pseudosphere configuration, hyperplane arrangements, flow, circular chromatic number, discrepancy, cocircuit, wiring diagram} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{article} \section{Introduction} \label{sect:intro} This paper regards an optimization problem which is an oriented matroid analogue of the graph chromatic number. There are several ways in which a `chromatic number' might be defined for more general matroids. One such formulation, introduced by Goddyn, Tarsi and Zhang \cite{GTZ}, depends only on the sign patterns of (signed) circuits (or cocircuits). The result is a natural invariant of an oriented matroid. In fact, any oriented matroid is representable as a pseudosphere complex, a regular cell decomposition of the sphere, where the cocircuits correspond to the zero-dimensional cells, see Figure~\ref{fig:cocircuit} for an example in rank 3. Accordingly, the invariant can be viewed as a `discrepancy in ratio' of a hyperplane arrangement, and thus should be of interest to geometers. The main theorem answers a question raised in~\cite{GTZ}. \begin{figure}[htbp] \begin{center} % \epsfxsize=6.0truecm % \centeredgraphics{K4.eps}\medskip \includegraphics[width=6cm]{K4.eps} \caption{An orientation of $K_4$ is represented as rank 3 pseudosphere arrangement. The dotted circle is the sphere equator. Each graph edge corresponds to a hypersphere, which is drawn as a circular arc with its ``positive'' side indicated with an arrow. Each vertex of the arrangement corresponds to one of the 7 cocircuits (directed cuts) of $K_4$. Indicated on both diagrams is the signed cocircuit $\left\{\{1,5\},\{3,4\}\right\}$.} %LUIS: changed % The intersection of hyperspheres 2 and 6 corresponds to % the indicated signed cocircuit $\left\{\{1,5\},\{3,4\}\right\}$ of $K_4$}. % The vertices of the arrangement correspond to the 7 % cocircuits (directed cuts) of $K_4$. The intersection of % hyperspheres 2 and 6 e.g.\ corresponds to the cocircuit % hyperspheres 2 and 6 e.g.\ corresponds to the signed cocircuit % $\left\{\{1,5\},\{3,4\}\right\}$.} % $\left\{1,5,\>3,4\right\}$.} \label{fig:cocircuit} \end{center} \end{figure} We first state the result and some consequences, using a minimal set of definitions. Detailed definitions appear in Section~\ref{sect:Background}. It is convenient to view an oriented matroid $\Oscr$ to be a matroid %on the ground set $E$ in which every circuit~$C$ (and cocircuit~$B$) has been partitioned $C = C^+ \cup C^-$, (and $B = B^+ \cup B^-$) subject to a standard orthogonality condition. %~\ref[Section ]{BLSWZ}. %LUIS: replaced % We regard each partition as an unordered pair $\{C^+, C^-\}$, Each such partition is an unordered pair $\{C^+, C^-\}$, where one of the parts may be empty. %The pair $\vC = \{C^+, C^-\}$ is called a \DEF{signing} of $C$. For %any $\Ror \subseteq E(\Oscr)$, the \DEF{reorientation} $\Oscr_{\Ror}$ of $\Oscr$ is the new oriented matroid obtained from $\Oscr$ by repartitioning each circuit $C$ %and each cocircuit $B$ (and cocircuit~$B$) according to the rules \begin{equation} \label{eq:resigning} \begin{array}[h]{c} \{C^+,\,C^-\} \mapsto \{C^+ \bigtriangleup (\Ror\cap C) ,\, C^- \bigtriangleup (\Ror\cap C)\} \qquad \mbox{and} \\[.3em] \{B^+,\,B^-\} \mapsto \{B^+ \bigtriangleup (\Ror\cap B) ,\, B^- \bigtriangleup (\Ror\cap B)\}. \qquad \mbox{~~~~} \end{array} \end{equation} where ``$\bigtriangleup$'' is the symmetric difference operator. % \begin{theorem} \label{thm:main} Let $\Oscr$ be an oriented matroid of rank at most $r$. % such that every cocircuit has cardinality at least two. There exists a reorientation $\Oscr_{\Ror}$ in which every cocircuit $B$ of size at least two satisfies $$ |B^+|, |B^-| \ge |B| /f(r) $$ where %$f$ is a fixed function satisfying %$ \sqrt{2r} \le f(r) \le 14r^2\log{r}$. $f(3) \le 17$, and $f(r) \le 14r^2\ln{r}$ for $r \ge 3$. \end{theorem} % For $\RR$-represented matroids, our result specializes to a new bound on the discrepancies `in ratio' % \DEF{log-discrepancies} $|\ln |B^+| - \ln |B^-||$ that occur among the \DEF{Radon partitions} of minimally dependent sets of real vectors of small corank. To be more precise: % \begin{corollary} \label{cor:main dual real} Let $(\bv_e : e \in E)$ be a list of nonzero vectors in $\RR^r$. Then it is possible to replace some of these vectors by their negatives such that, for any minimal sublist $\{ \bv_e \mid e \in C\}$, $C \subseteq E$ of linearly dependent vectors, every nontrivial real solution to $\sum_{e\in C} \alpha_e \bv_e =0$ has at least $|C|/f(|E|-r)$ coefficients $\alpha_e$ of each sign, where $f(s) \le 14 s^2 \ln s$. \end{corollary} % We may restate this result in the dual. The \DEF{support} of a vector $\bt = (t_e) \in\RR^E$ is \ $\supp(\bt) = \{ e \in E \mid t_e \ne 0\}$. The \DEF{rowspace} of a matrix $A$ is the set of vectors of the form $yA$, where $y$ is a row vector. % \begin{corollary} \label{cor:main real} Let $A \in \RR^{R \times E}$ be a real matrix of rank $r$, where $R$ and $E$ are index sets. Then it is possible to multiply some columns of $A$ by $-1$ so that, for every vector $\bt$ in the rowspace of the resulting matrix, if $|\supp(\bt)| \ge 2$ and $\supp(\bt)$ is minimal among the nonzero vectors in the rowspace, then $\bt$ contains at least $|\supp(\bt)|/f(r)$ %entries of each sign positive and negative entries each, where $f(r) \le 14 r^2 \ln r$. \end{corollary} % We remark that, if $(\bv_e : e \in E)$ are the columns of a real matrix $A$, then the sets $C \subseteq E$, and $\supp(\bt) \subseteq E$ referred to in Corollaries~\ref{cor:main dual real} and~\ref{cor:main real} are, respectively, the circuits and cocircuits of the oriented matroid represented by the matrix~$A$. % If, in Corollary~\ref{cor:main dual real}, each vector $\bv_e$ is the If each column $\bv_e$ of $A$ is the difference of two unit vectors, then we are in the setting of graph theory: Here $A \in \RR ^{V \times E}$ is the $\{0, \pm1\}$-valued vertex-edge incidence matrix % Here $E$ is the set of edges of a directed graph $\vec G = (V,E)$. % the coordinates of vectors~$\bv_e$ are indexed by the vertex set $V({\vec G})$, % and the entries $+1, -1$ indicate edge incidences. Multiplying~$\bv_e$ by~$-1$ corresponds to reorienting the edge $e$ in $\vec G$. %LUIS: deleted -- better later % (In general, the vertex-edge incidence matrix of a directed graph % is a totally unimodular representation of its % polygon matroid~\cite[Chapter 5]{oxley}.) %LUIS: changed %gives a totally unimodular representation of its %matroid~\cite[Chapter 5]{oxley}.) %The incidence vectors of arcs of a digraph contain exactly two nonzero %entries $-1,+1$ at the head and the tail, respectively, and %changing the sign of such a vector means reversing the arc. %(In general, the incidence matrix of any orientation of a graph %gives a totally unimodular representation of its %matroid~\cite[Chapter 5]{oxley}.) A formula of Minty~\cite{Minty} relates the graph chromatic number $\chi(G)$ to ratios of the form $|C|/|C^+|$ seen among reorientations of a~$G$. %Here our result (Corollary~\ref{cor:main dual real}) further specializes Here Corollary~\ref{cor:main dual real} further specializes to the observation that $\chi(G) \le f(\rk^*(G))$ for any loopless graph $G=(V,E)$, where $\rk^*(G) = |E|-|V|+1$ is the \DEF{corank}, or the \DEF{first Betti number} of $G$. For graphs, the upper bound on $f$ can be improved to % $\chi(G) \le f(s) \le \left\lceil\sqrt{2(s+1)}^{~}\right\rceil$. $\chi(G) \le f(s) \le \left\lfloor\sqrt{2s}\right\rfloor+2$. (This follows without much difficulty from Dirac's density result \cite{D} for colour critical graphs.) This bound on $\chi(G)$ is (essentially) attained by complete graphs. % %Dirac's density result \cite{D} for colour critical graphs implies that %all graphs with chromatic number $k$ have at least $k \choose 2$ edges. %It follows easily that all loopless graphs $G$ %having corank $s$ satisfy %$$ %\chi(G) \le 1+ \sqrt{2s}, %$$ %and that this bound is (essentially) attained by complete graphs. The above discussion indicates that the best function~$f$ for our result %among all oriented matroids satisfies $$ \left\lfloor\sqrt{2s}\right\rfloor+2 \le\, f(s) \,\le 14s^2\ln s.$$ We do not attempt to further optimize the function $f(s)$ of Theorem~\ref{thm:main}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5 \section{Background and Definitions} \label{sect:Background} % Here we give some motivating comments % and make precise definitions. % We are assuming basic familiarity with graphs and matroids~\cite{oxley}. % For reader's convenience, we briefly review some matroid terminology. % The knowledgeable reader may prefer to quickly scan the following material. %A {\em matroid} $M$ is formed by a collection of independent sets over the %ground set $E(M)$. Minimal dependent sets are circuits, and the circuits %of the dual matroid $M^*$ are called cocircuits of~$M$. %A matroid is simple if it has no loops or parallel elements, %i.e.\ no circuits of size $1$ or~$2$. %We call flats the closed sets in a matroid, %i.e.\ the sets which are maximal of their rank. %In other words, a flat is such a set $X\subseteq E(M)$ that no circuit %has exactly one element outside of~$X$. %A flat of rank one less than the matroid rank is called a hyperplane, %and hyperplanes are precisely the complements of cocircuits. We shall use terminology from matroids, oriented matroids and real geometry. For sake of convenience, we tersely review the relevant definitions and connections, although the reader is expected to have some basic knowledge of graphs, matroids and linear algebra. The experienced reader prefer to skip to the fourth subsection, although a couple of our oriented-matroid terms are non-standard. \subsection{Matroids} A \DEF{matroid} $M$ is a \DEF{ground set} $E = E(M)$ together with a collection of subsets called \DEF{independent sets}. Independent sets are closed under taking subsets, and they satisfy a well-known \DEF{exchange axiom}. A maximal independent set is a \DEF{basis} of $M$. Minimal dependent sets in $M$ are \DEF{circuits}. A \DEF{loop} is a circuit of size one. Two elements are \DEF{parallel} if they form a circuit. The \DEF{parallel class} $[e]$ is the equivalence class of elements parallel to $e \in E$. A matroid is \DEF{simple} if it has no loops or parallel elements. The \DEF{girth} of $M$ is the least cardinality of one of its circuits. The \DEF{rank}, $\rk (X)$, of a set $X \subseteq E$ is the maximum cardinality of an independent subset of $X$. We write $\rk(M) = \rk(E(M))$ for the rank of the matroid. % Where $k \in \{0,1,\dots,\rk(M)\}$, a \DEF{$k$-flat} % or \DEF{closed set} A \DEF{$k$-flat} is a maximal subset $X$ of rank~$k$. Equivalently $X$ is a flat if no circuit of~$M$ contains exactly one element of~$E- X$. The intersection of two flats is a flat. A \DEF{hyperplane} of~$M$ is a $(r(M)-1)$-flat A \DEF{connected component} of~$M$ is a maximal subset of $E$ in which any two elements are contained on some circuit %(or, equivalently, some cocircuit) % Not yet defined! of~$M$. A matroid with one component is \DEF{connected}. The complements of the bases of~$M$ form the bases of %another matroid $M^*$ called the \DEF{dual matroid} $M^*$. We have $E(M) = E(M^*)$. The prefix ``\DEF{co}'' refers to sets or properties of the dual matroid. In particular, %a set of elements a set $X \subseteq E$ has \DEF{corank}~$k$, is a \DEF{coloop}, a \DEF{cocircuit}, or a \DEF{coparallel class} in $M$ if (resp.)\ $X$ has rank~$k$, is a loop, a circuit, or a parallel class in $M^*$. A matroid $M$ is \DEF{cosimple} if $M^*$ is simple. A cocircuit of $M$ is characterized as % It follows that a cocircuit of $M$ is precisely a minimal subset of $E$ which has nonempty intersection with every basis of $M$. Alternatively cocircuits of $M$ are precisely the complements of hyperplanes of $M$. A circuit and a cocircuit can never intersect in exactly one element. % The \DEF{corank} $\rk^*(X)$ of $X \subseteq E(M)$ in $M$ equals the rank of $X$ in $M^*$. % A matroid $M$ is uniquely specified by listing any one of the following collections % of subsets of $E(M)$: its bases, its circuits, its cocircuits, or its hyperplanes. % By \DEF{deleting} (or \DEF{contracting}) an element $e$ of $M$, we obtain a new matroid $M \backslash e$ (or $M/e$) on the ground set $E(M)-\{e\}$. % These are denoted $M \backslash e$ and $M / e$ respectively. % We have $E(M \backslash e) = E(M / e) = E -\{e\}$. The circuits of $M \backslash e$ are precisely the circuits of $M$ which avoid $e$. The cocircuits of $M / e$ are the cocircuits of $M$ which avoid $e$. If $S$ and $T$ are disjoint subsets of $E(M)$, then $M\backslash S/T$ denotes a matroid obtained by successively deleting the elements in $S$ and contracting those in $T$. The matroid $M\backslash S/T$ is well defined % since the order of these operations does not matter. % Any matroid of the form $M\S/T$ and is called a \DEF{minor} of $M$. The \DEF{polygon matroid} $M(G)$ of a connected graph (or directed graph)~$G$ has ground set~$E(G)$. The bases, circuits, and cocircuits of $M(G)$ are, respectively, (the edge sets of) the spanning trees, simple cycles and minimal edge cuts of $G$. A matroid of the form $M(G)$ is said to be \DEF{graphic}, and its dual is \DEF{cographic}. We have that $M(G)$ is connected if and only if $G$ is a $2$-connected graph. % A matroid $M$ is \DEF{represented} by a matrix~$A$ (over some field) if there is a bijective correspondence between $E(M)$ and columns of~$A$, such that the independent sets of $M$ correspond precisely to linearly independent sets of columns of~$A$. Here we may write $M = M[A]$. The cocircuits of $M[A]$ are the supports of non-zero vectors in the rowspace of~$A$ having minimal support. A matroid is \DEF{$\RR$-representable} if it can be represented by a real matrix. % If $M$ can be represented over any field, then $M$ is \DEF{regular}. A regular matroid can be represented by a \DEF{totally unimodular matrix}~$A$, a real matrix whose subdeterminants all belong to $\{0, \pm 1\}$. %As mentioned in Section~\ref{sect:intro}, the The $\{0,\pm 1\}$-valued incidence matrix of a directed graph is totally unimodular, so graphic (and cographic) matroids are regular. \smallskip \subsection{Oriented Matroids} % Among the several equivalent formulations of `oriented matroid', the following, which is due to Bland and Las Vergnas~\cite{BLV} (cf. \cite[Theorem 3.4.3]{BLSWZ}), is best suited to our purpose. % %Although a (simple) oriented matroid may be viewed as a geometric object, %it suits us to define them as matroids with signed circuits and cocircuits. % A \DEF{signing} of a set $X$ is an unordered partition $\vec X = \{ X^+, X^-\}$ of $X= X^+ \cup X^-$, where either part may be empty. % LUIS: moved it later % We define the \DEF{imbalance} % or \DEF{log-discrepancy} of $\vec X$ to be % $$ % 2 \le \imbal(\vec X) = \frac{|X|}{\min \{ |X^+|, |X^-|\}} \le \infty, % $$ % where the value $\infty$ indicates that one of $X^+$, $X^-$ is empty. A pair $(\vec C, \vec B)$ of signed sets is \DEF{orthogonal} if % \begin{equation} \label{eq_orth} (C^+ \cap B^+) \cup (C^- \cap B^-) = \emptyset \iff (C^+ \cap B^-) \cup (C^- \cap B^+) = \emptyset. \end{equation} % This terminology reflects the fact that, for any two orthogonal vectors in Euclidean space, % is orthogonal only if either their supports are disjoint, or there is both a positive and a negative summand in their scalar product. \comment{Winfried: Petr, does this match your requirements?} Any orientation of a graph $G$ naturally signs %(the edge set of) each circuit (simple cycle)~$C$ in~$G$, and each circuit and cocircuit of its polygon matroid $M(G)$. %also signs each cocircuit (minimal edge cut)~$B$ in~$G$. Moreover, each signed circuit-cocircuit pair $(\vC,\vB)$ in $M(G)$ is orthogonal. % Accordingly, we define an \DEF{oriented matroid} on the ground set $E$ to be a triple $\Oscr = (M, \vCscr, \vBscr)$ where \begin{enumerate} %\item $M = (E, \Cscr, \Bscr)$ is a matroid with \item $M$ is a matroid with ground set $E$, circuits $\Cscr$, and cocircuits $\Bscr$. \item $\vCscr = \{\vC \mid C \in \Cscr\}$ and $\vBscr = \{\vB \mid B \in \Bscr\}$ are signings of the circuits and cocircuits such that each pair in $\vCscr \times \vBscr$ is orthogonal. \end{enumerate} %%%%%%%%%%%%% The oriented matroid $\Oscr = (M, \vCscr, \vBscr)$ is called an \DEF{orientation} of $M$, and $M$ is said to be \DEF{orientable}. Graphic matroids are orientable; we write $\Oscr(\vec G)$ for the oriented matroid associated with a directed graph~$\vec G$. More generally, matroids which are $\RR$-representable %over an ordered field are orientable. Moreover, every real matrix representation $M = M[A]$ naturally induces an orientation $\Oscr[A]$ of~$M$. The signings of circuits $C = C^+ \cup C^-$ in $\Oscr[A]$ are the \DEF{Radon partitions} of minimally dependent sets of columns $\{ \bv_e \mid e \in C\}$ of~$A$. Specifically, the Radon partition of $C$ is determined by the signs of the real coefficients $\alpha_e$ in a non-trivial solution to $\sum_{e\in C} \alpha_e \bv_e = 0$. The signings of cocircuits of $\Oscr$ are determined by the sign patterns of nonzero vectors in the row-space of $A$ having minimal support. %This is what lies behind the statements of Corollaries %\ref{cor:main dual real} and \ref{cor:main real}. % If $M$ has a representation $M[A]$ over any field, then $M$ is said to be \DEF{regular}. % Regular matroids can be represented by a \DEF{totally unimodular matrix} $A$, % a real matrix whose subdeterminants belong to the set $\{0, \pm 1\}$. % As mentioned in Section~\ref{sect:intro}, the $\{0,\pm 1\}$-valued incidence % matrix of a directed graph is totally unimodular, so graphic matroids are regular. Not all matroids are orientable. For example, a \DEF{binary} matroid, i.e.\ a matroid representable by a matrix over GF(2), is orientable if and only if it is regular. Every orientation of a regular matroid can be represented by a totally unimodular matrix. Let $\Oscr = (M, \vCscr, \vBscr)$ be an oriented matroid. For any $\Ror \subseteq E$, the reorientation $\Oscr_{\Ror}$ defined by~(\ref{eq:resigning}) is easily seen to be an oriented matroid. % This The operation $\Oscr \mapsto \Oscr_\Ror$ is analogous to reversing a subset $\Ror$ of the edges of a directed graph. The orientations of $M$ are partitioned into \DEF{reorientation classes}, where the class of $\Oscr$ is defined to be $[\Oscr] = \{ \Oscr_{\Ror} \mid \Ror \subseteq E\}$. For sake of brevity, we say that $[\Oscr]$ is a \DEF{reclass} of $M$. An orientable matroid may have several reclasses. However all regular matroids (including graphs and cographs) have a unique reclass. For this reason, the reclass of an \emph{unoriented} graph $G$ is well defined by $[\Oscr(G)] = [ \Oscr(\vec G)]$ for some orientation $\vec G$ of $G$. For any connected component $I$ of $\Oscr$, we have $\Oscr_{\Ror} = \Oscr$. Indeed each reclass of $M$ contains precisely $2^{|E|-\omega}$ orientations of $M$, where $\omega$ is the number of connected components of $M$. Matroidal notions such as connectedness, simplicity, flats, and the rank function $\rk(\cdot)$ naturally carry over to oriented matroids and to reclasses. Matroid minors also carry over naturally: for disjoint subsets $S,T \subseteq E(\Oscr)$, the \DEF{minor} $\Oscr / S \backslash T$ is the orientation of the matroid minor $M/S\backslash T$ obtained by restricting the signings in $\vCscr \cup \vBscr$ to the circuits and cocircuits of $M/S\backslash T$. The \DEF{dual} of $\Oscr = (M, \vCscr, \vBscr)$ is defined by $\Oscr^* = (M^*, \vBscr, \vCscr)$. An oriented matroid $(M,\vCscr,\vBscr)$ is uniquely determined by either of the pairs $(M,\vCscr)$ or $(M,\vBscr)$. %%%%%%%%%5 \subsection{Geometry} \label{sect:geom} There is a bijective correspondence between simple reclasses~$[\Oscr]$ %of rank~$r$ and topological objects called pseudosphere complexes. This is due to Folkman/Lawrence~\cite{FoLa} and Edmonds/Mandel~\cite{Mandel}. We describe a pseudosphere complex in the case $\Oscr$ is $\RR$-representable, and outline the construction for general reclasses $[\Oscr]$. We then specialize to rank~$3$ and the easy-to-visualize wiring diagrams. %The pseudosphere complex of a simple $\RR$-represented oriented matroid %is easy to describe. Let $\Oscr = \Oscr[A]$ where each column $\bv_e$ of $A$ is a vector in~$\RR^r$. Let $S_0 = \{ x \in \RR^{r} \mid |\!|x|\!|=1\}$ be the unit $(r-1)$-sphere. Each $e\in E(\Oscr)$ corresponds to an $(r-2)$-subsphere~$H_e$, called a \DEF{pseudohypersphere}, and consisting of those vectors in $S_0$ which are orthogonal to~$\bv_e$. %Each $H_e$ is called a \DEF{pseudohypersphere}. %, and each of the two connected components of $S-H_e$ is a \DEF{side} of $H_e$. The \DEF{positive side} of $H_e$ are the vectors in $S_0$ having a positive scalar product with $\bv_e$. The \DEF{pseudosphere complex} $\Sscr = \Sscr[\Oscr]$ is the family of subspheres of~$S_0$ that can be obtained as intersections of pseudohyperspheres. Each subsphere in $\Sscr$ is a $k$-sphere for some $k$, and is called a \DEF{$k$-pseudosphere}. Evidently, a $k$-flat $F$ of $\Oscr$ corresponds to the set of pseudohyperspheres $\{ H_e \mid e \in F \}$ which contain a particular $(r-k-1)$-pseudosphere in~$\Sscr$. This correspondence between flats and pseudospheres is bijective. In particular, the hyperplanes of $\Oscr$ correspond to $0$-spheres in~$\Sscr$. (A $0$-sphere consists of two ``antipodal'' points of $S_0$.) Accordingly, each $0$-sphere $S \in \Sscr$ corresponds to a cocircuit $B = \{ e \in E \mid H_e \cap S = \emptyset \}$. The signing $B = B^+ \cup B^-$ is found by determining, for each $e \in B$, which of the two points of $S$ lies on the positive side of $H_e$. A reorientation $\Oscr_\Ror$ corresponds to interchanging the positive and negative sides of $H_e$, for each $e \in \Ror$. Thus the complex $\Sscr$ is well defined by the reclass $[\Oscr]$. The pseudosphere complex of a general simple reclass $[\Oscr]$ of rank $r$ is similarly defined, except that pseudospheres are no longer constrained to lie on subspaces of $\RR^r$. Instead, pseudospheres are topological subspheres of~$S_0$ which %are well behaved as if they were piecewise linear, and are subject to certain axioms. % Again, every cocircuit of $\Oscr$ is associated with a $0$-pseudosphere % in $\Sscr$. % The orientation in $[\Oscr]$ is determined by designating one side of % each pseudohypersphere~$H_e$ as being the positive side. The axioms ensure that any $0$-pseudosphere which is disjoint from a hyperpseudosphere~$H_e$ has exactly one of its two points on the positive side of~$H_e$, so the signing of each cocircuit well defined. A proof of the correspondence between reclasses and psudosphere complexes can be found in~\cite{FoLa}. Deleting an element $e$ of $\Oscr$ corresponds to deleting the pseudohypersphere $H_e$ in the construction of $\Sscr[\Oscr]$. Contracting $e$ in $\Oscr$ corresponds to restricting the complex $\Sscr[\Oscr]$ to those pseudospheres contained in~$H_e$. Here $H_e$ plays the role of $S_0$ and the pseudohyperspheres of $\Sscr[\Oscr / e]$ are the $(r-2)$-pseudospheres $\{ H_e \cap H_f \mid f \in E - \{e\}\}$. Thus contracting a flat $F$ in $\Oscr$ corresponds to restricting~$\Sscr$ to those pseudospheres contained in~$S_F$, where $S_F$ is the pseudosphere in $\Sscr$ corresponding to~$F$. Here, the cocircuits of $\Oscr / F$ correspond bijectively to the those $0$-pseudospheres in $\Oscr$ which are contained in~$S_F$. We have $\rk(\Oscr / F) = \rk(\Oscr) - \rk(F)$. % A \DEF{pseudosphere of dimension $k$} % (or \DEF{$k$-pseudosphere} for short) % is a piecewise-linear homeomorph of the unit $k$-sphere % $\{ x \in \RR^{k+1} \mid |\!|x|\!|=1\}$. % A \DEF{pseudosphere complex} associated with a reclass $[\Oscr]$ of rank $r$ % is a complex $\Sscr = \Sscr[\Oscr]$ of sub-pseudospheres % of a fixed $(r-1)$-pseudosphere $S_0$. % It is convenient to regard $S_0$ as the boundary of a unit cube % in $\RR^r$ centered at the origin. % The $(r-2)$-pseudospheres in $\Sscr$ are called \DEF{pseudohyperspheres}. % These pseudohyperspheres correspond bijectively to the elements of $\Oscr$, % and are subject to certain axioms. % The complex $\Sscr[\Oscr]$ % associated to the rank-$r$ reclass $[\Oscr]$ % is determined by a finite set % the arrangement of % of \DEF{pseudohyperspheres} (i.e.\ $(r-2)$-sub-pseudospheres of $S_0$). % The pseudohyperspheres % are in bijective correspondence with $E(\Oscr)$, % (The axioms % are intended to reflect properties of pseudohyperspheres which arise % as intersections of $S_0$ % with a finite family of $(r-1)$-subspaces of $\RR^r$.) % A pseudohypersphere is a topological $(r-2)$-sphere lying on $S_0$, and % which is well behaved as if it were piecewise linear. % Each element of $\Oscr$ corresponds to one of the pseudohyperspheres. % The pseudospheres which comprise $\Sscr$ % are all of the sub-pseudospheres of $S_0$ that can be % obtained as intersections of pseudohyperspheres. % Each $0$-pseudosphere, say $x \in \Sscr$, consists of two points on $S_0$. % The set of pseudohyperspheres in $\Sscr$ which contain~$x$ % corresponds to a (matroidal) hyperplane of $\Oscr$. % Those pseudohyperspheres which avoid~$x$ constitute a cocircuit of $\Oscr$. % In a similar way, %% every pseudosphere in $\Sscr$ corresponds to a flat of $\Oscr$. % every $k$-flat of $\Oscr$ corresponds to a pseudosphere in $\Sscr$ % of dimension $r-k-1$. %% % In case $\Oscr = \Oscr[A]$ for some real $r \times |E|$ matrix $A$ of rank $r$, % the pseudohypersphere corresponding to a column $\bv_e$ of~$A$ % may be taken to be % the set of points on $S_0$ which are orthogonal to the vector $\bv_e \in \RR^r$. % An specific orientation in $[\Oscr]$ is determined by designating, % for each hyperplane $H_e$, $e \in E$, % one of the two components of $S_0-H_e$ to be the ``positive side'' of~$H_e$. % We make this correspondence more explicit in the following paragraph. In a rank-$3$ pseudosphere complex $\Sscr= \Sscr[\Oscr]$, the pseudohyperspheres are simple closed curves %($1$-pseudospheres) on a $2$-sphere $S_0$. Any two such curves ``cross'' at a $0$-pseudosphere in $\Sscr$. The axioms ensure that $S_2$ contains an \DEF{equator}, a simple closed curve $K$ % which ``crosses'' every pseudohypersphere, and in general position such that every $0$-pseudosphere has % its two points on opposite sides of~$K$. one point on each side of~$K$. By restricting the complex to one side of~$K$, we obtain an affine representation of $\Sscr$ called a \DEF{wiring diagram}. A wiring diagram is a set of smooth plane curves $\{C_e \mid e\in E\}$, each curve connecting a pair of opposite boundary points of a fixed disc $D$ in the plane. Any two curves cross exactly once, and are otherwise disjoint. Each crossing point $x$ is an \DEF{vertex} which corresponds to the % Each crossing point $x$ is a \DEF{vertex} which corresponds to the matroid %matroid hyperplane $\{e\in E \mid C_e \ni x\}$ and the complementary cocircuit $\{ e \in E \mid C_e \not\ni x\} \in \Bscr(\Oscr)$. An oriented matroid in $[\Oscr]$ is determined by designating, for each $e \in E$, one of the two components of $D-C_e$ as being the ``positive side'' of $C_e$. Each element~$e$ of a cocircuit $B$ is signed according to whether the corresponding vertex lies on the positive or negative side of $C_e$. % (recall Figure~\ref{fig:cocircuit}). See Figure~\ref{fig:cocircuit} for an example. If $\Oscr$ is not simple, then all elements of one parallel class $[e]$ are associated to the same curve~$C_e$, although each element in~$[e]$ is independently oriented. We may record the cardinality of~$[e]$ on the diagram, and use arrows to indicate the positive side of each element. Loops geometrically correspond to the full sphere $S_0$ or disc $D$. Loops are not contained in any cocircuit and do not matter in our context. %The boundary of $D$, called the \DEF{equator} of the diagram, %corresponds to an arbitrary equator of $S_0$ which is in general position. Because of the choice selecting the equator $K$, several wiring diagrams may correspond to the same oriented matroid. The curves~$C_e$ % of a wiring diagram for $[\Oscr]$ may be drawn as straight lines if and only if $\Oscr$ is $\RR$-representable. % since there is choice in the location of the equator. %LUIS: moved to Example 2.1 % \begin{figure}[htb] % % \epsfxsize=11.3truecm % % \epsfxsize=\hsize % % \centeredgraphics{u36d.eps} % \begin{center} % \includegraphics[width=11.3cm]{u36d.eps} % \end{center} % \hbox to \hsize{\hfill $\Oscr_1$ \hfill\hfill ~~$\Oscr_2$ % \hfill\hfill ~~$\Oscr_3$ \hfill\hfill ~$\Oscr_4$\hfill} % \caption{The four reclasses of the uniform matroid $U_{3,6}$.} % \label{fig:-1} % \end{figure} % % Figure~\ref{fig:-1} depicts the wiring diagrams of the four reclasses % $\Oscr_1,\Oscr_2,\Oscr_3,\Oscr_4$ of $U_{3,6}$. % We remark that all % four diagrams could be drawn with straight lines. The first diagram % $\Oscr_1$ has an orientation with imbalance~$2$. There exist no such % orientations for the next three diagrams. (To see why, notice that % the cocircuits have all size $4$, and so imbalance must be either $2$ % or $4$. Now consider one of the little triangles; its lines allow % only one orientation, up to symmetry, possibly achieving % imbalance~$2$. This partial orientation then uniquely extends along % other triangles, leading to a contradiction. In $\Oscr_4$, e.g., we % derive, starting at the dark grey triangle, % extending along the two adjacent triangles, % a contradiction at the light grey triangle.) % \comment{\footnotesize "Figure 1 depicts two of the four % reclasses, $\Oscr_1$, $\Oscr_2$ of $U_{3,6}$. The orientations % shown are optimal in the definition of $\phio(\Oscr)$." The % caption should read "Optimal orientations of two reclasses..." % There are exactly three vertices in the second diagram whose % cocircuits have imbalance 4 (they are on the little triangle in the % right side of the diagram). Should we highlight this? Some of the % elements are hard to see in black/white. } %%%%%%%%%%%%% %LUIS: eliminated this part altogether %\medskip % % The following additional facts may be found in \cite{BLSWZ}, and are % used tacitly in this paper. %\comment{Luis:Delete or undelete these as you wish} % \begin{enumerate}\vspace*{-\smallskipamount} % \item A \DEF{flat} is a maximal set of elements of fixed rank. % The intersection of any two flats is a flat. % For any flat $F$ of $\Oscr$, $F' \subseteq E-F$ is a flat in % $\Oscr / F$ if and only if $F' \cup F$ is a flat in $\Oscr$. % A subset $F\subseteq E$ is a hyperplane % (i.e.~a flat of corank 1) of $\Oscr$ % if and only if $E-F$ is a cocircuit of $\Oscr$. % \item An oriented matroid $(M,\vCscr,\vBscr)$ is uniquely determined % by either of the pairs $(M,\vCscr)$ or $(M,\vBscr)$. % As with matroids, each of these pairs is subject to an % \DEF{strong elimination axiom}: % \begin{quote} % For $X,Y\in \Cscr$ and $e \in X^+ \cap Y^-$, % and $f \in (X^+ - Y^-)\cup(X^- - Y^+)$, % there exists $Z\in \Cscr$ with % $f\in Z$ and % each of $Z^+$, $Z^-$ contained in one of % $(X^+ \cup Y^+)-\{e\}$ or $(X^- \cup Y^-)-\{e\}$. % \end{quote} %\item Every coloop-free oriented matroid $\Oscr$ % has a \DEF{strong reorientation}, % a reorientation $\Oscr_{\Ror}$ % such that $B^+, B^- \ne \emptyset$ % for all $\vec B \in \vBscr_{\Ror}$. % Thus the circular flow number of a reclass is % at most the size of its largest cocircuit. %\item The \DEF{dual} of $\Oscr = (M,\vCscr,\vBscr)$ % is defined by $\Oscr^* = (M^*,\vBscr,\vCscr)$, % where $M^*$ is the dual matroid of $M$. %%%%%%%%%%%%%%%%%5 %LUIS: deleted redundant %\item For disjoint subsets $S,T \subseteq E(\Oscr)$, the \DEF{minor} % $\Oscr / S \backslash T$ is the orientation % of the matroid minor $M/S\backslash T$ obtained by % restricting the signings in % $\vCscr \cup \vBscr$ % to the circuits and cocircuits of $M/S\backslash T$. %\item Matroid elements are partitioned into % \DEF{parallel classes}, where the class of $e \in E$ is % $ [e] = \{e\} \cup \{f \in E \mid \{e,f\} \in \Cscr \}$. % The \DEF{multiplicity} of $e$ is $|[e]|$. % Any orientation $\Oscr$ of $M$ induces a partition % $ [e] = [e]^+ \cup [e]^-$ on each parallel class such that % each part is a subset of either $B^+$ or $B^-$ for % every signed cocircuit containing $e$. % %The \DEF{underlying simple oriented matroid} of $\Oscr$ % %is obtained by deleting all loops and deleting all but one element from % %each of $[e]^+$, $[e]^-$ for each parallel class $[e]$. %\item A binary matroid is orientable if and only if is it is regular. %\item A regular matroid has a unique reclass. % For oriented regular matroids, the two sets in (\ref{eq_orth}) % always have equal cardinalities. %\item There is a bijective correspondence between % \DEF{simple} reclasses $[\Oscr]$ % %(having no loops or multiple elements) % and topological objects called \DEF{pseudosphere complexes}. % This is due to Folkman and Lawrence~\cite{FoLa} % and Edmonds and Mandel~\cite{Mandel}. %%%%%%%%%% %LUIS: I deleted this as it is now redundant % \item Any matroid representable over $\RR$ is orientable. Every % $\RR$-representa\-tion $M = M[A]$, $A \in \RR^{R\times E}$ % determines an orientation $\Oscr = \Oscr[A]$ of $M$. The % signings of the cocircuits are derived as follows: Consider the % columns $A_{.e}$ of $M$ as linear forms in $\RR^R$. We may % identify the 1-dimensional space spanned by that form in dual % space with its nullspace and thus with a linear hyperplane. If % $M[A]$ is simple, then the pseudosphere complex corresponding % to $[\Oscr[A]]$ is a complex $\Sscr$ of subspheres of $S := \{ % x \in\RR^R \mid ||x||=1\}$. Each matroid flat $F \subseteq E$ % (see~\cite{BLSWZ} Remark 3.2.2) corresponds to the % subsphere $S_F = S \cap {\rm nullspace}(A_F) \in \Sscr$, where % $A_F$ is the submatrix of $A^T$ whose rows are selected by $F$. % The elements of $M$ correspond to \DEF{pseudohyperspheres} $S_{\{e\}} % \in \Sscr$. The hyperplanes of $M$ correspond to $0$-spheres % in $\Sscr$. Each of the two points constituting a $0$-sphere % is called a \DEF{vertex} of~$\Sscr$. The signings $\{B^+,B^-\}$ % of a cocircuit $B$ in $\Oscr[A]$ are given via % $$ % B^+ = \{ e\in B \mid A_{\{e\}} x >0 \} % \qquad % B^- = \{ e\in B \mid A_{\{e\}} x <0 \} % $$ % where $x$ ranges over the two vertices corresponding to the % hyperplane $E-B$. %\item Not all orientable matroids are $\RR$-representable. % However % any PSC may be obtained from a real sphere complex % by suitably ``perturbing'' coincident pseudohyperspheres. %\item A general oriented matroid may be viewed as % a PSC which has been endowed with additional information. % % {\footnotesize % Deleting a \DEF{pseudohypersphere} $S_{\{e\}}\in \Sscr$ % %from the underlying sphere % leaves two open balls called % \DEF{sides} of $S_{\{e\}}$. % A reorientation in $[\Oscr]$ is determined % by designating one side of each $S_{\{e\}}$ as % being ``positive''. % A nonsimple oriented matroid $\Oscr$ is represented as a PSC % with a pseudohypersphere $S_{[e]}$ for each parallel class. % To record the orientation, we % associate the two sets $[e]^+$, $[e]^-$ with the two sides of $S_{[e]}$. % Separately, we record the number of loops in $\Oscr$. % %The pair determines which elements of $[e]$ are oriented toward the % %positive side of $S_[e]$. % } %\item Any rank $3$ PSC can be affinely represented by a % \DEF{wiring diagram}. % {\footnotesize % A wiring diagram is a set of smooth plane curves % $\{C_e \mid e\in E\}$, each joining a pair of % opposite boundary points of a % fixed disc $D$ in the plane. % Any two curves must cross exactly once, % and are otherwise disjoint. % Each crossing point $x$ corresponds to % the matroid hyperplane % $\{e\in E \mid C_e \ni x\}$. % An orientation of the PSC is determined by designating, % for each curve $C_e$, one of the two components of $D-C_e$ % as being the ``positive side'' of $C_e$. % Each element~$e$ of a cocircuit $B$ is signed % according to whether the crossing % point for the hyperplane $E-B$ lies on the positive % or negative % side of $D-C_e$, for $e \in B$. % } %\item Deleting one element from % each of $[e]^+$, $[e]^-$, for some parallel class $[e]$, % can not decrease the imbalance of any cocircuit in $\Oscr$. %\item The circular flow number of the direct sum % $\Oscr \cup \Oscr'$ is the larger of % $\phio(\Oscr)$ and $\phio(\Oscr')$. %\item If $e,f\in E$ are coparallel in in $\Oscr$, then % $\phio(\Oscr) = \phio(\Oscr/e)$. %\end{enumerate} %%%%%%%%%%%%%%%%%%%5 \subsection{Oriented Flow Number} We define the \DEF{imbalance} or \DEF{log-discrepancy} of a signed set $\vec X = \{ X^+, X^- \}$, where $X = X^+ \cup X^- \subseteq E$, %$\vec X$ by $$ 2 \le \imbal(\vec X) = \frac{|X|}{\min \{ |X^+|, |X^-|\}} \le \infty. $$ Here, the value $\infty$ indicates that one of $X^+$, $X^-$ is empty. Minty \cite{Minty} considered the graph invariant $$ \chio(G) := \min_{\vec G} \, \max_{\vec C} \, \imbal(\vec C), $$ where $\vec G$ varies over the set of orientations of $G$, and $\vec C$ varies over the set of signed circuits in $\vec G$. He showed that the graph chromatic number is given by $\chi(G) = \lceil \chio(G) \rceil$. The invariant $\chio(G)$, now called the \DEF{circular chromatic number}, has several equivalent definitions and has seen a flurry of recent interest (see \cite{Zhu} for a survey). Within graph theory, this invariant is more usually denoted by $\chi_c$ or $\chi^*$, but we use $\chio$ to emphasize the viewpoint of orientations. The definition of $\chio$ is suitable for generalization to oriented matroids. In the matroid setting, we prefer to speak in terms of the dual parameter. Thus we define the \DEF{oriented flow number} of an oriented matroid to be $$ \phio(\Oscr) := \min_{\Oscr_{\Ror}^{\vbox to.9ex{\vfill}}} \, \max_{\vec B} \, \imbal(\vec B), $$ where $\Oscr_{\Ror}$ varies over the set of reorientations of $\Oscr$, and $\vec B$ varies over the signed cocircuits in~$\Oscr_{\Ror}$. % The oriented flow number of any reclass $[\Oscr]$ is well defined by $\phio([\Oscr]) = \phio(\Oscr) $. If a matroid $M$ has a unique reclass~$[\Oscr]$ (e.g.\ if $M$ is regular), then $\phio(M)$ is well defined to equal $\phio([\Oscr])$. Thus $\chio(G) = \phio(M^*(G))$ where $M^*(G)$ denotes the (cographic) dual of the polygon matroid $M(G)$. In general, the oriented flow number of an orientable matroid $M$ is \emph{not} well defined. \begin{example} \label{eg:U3,6} % As listed in~\cite{F}, The uniform matroid $U_{3,6}$ is orientable and has precisely four reclasses, $[\Oscr_i]$, $1\le i \le 4$, whose wiring diagrams are shown in Figure~\ref{fig:-1}. %(see Figure~\ref{fig:-1} for their geometric representations). % \begin{figure}[htb] % \epsfxsize=11.3truecm % \epsfxsize=\hsize % \centeredgraphics{u36d.eps} \begin{center} %\includegraphics[width=11.3cm]{u36d.eps} \includegraphics[width=11.3cm]{u36c.eps} \end{center} \hbox to \hsize{\hfill $\Oscr_1$ \hfill\hfill ~~$\Oscr_2$ \hfill\hfill ~~$\Oscr_3$ \hfill\hfill ~$\Oscr_4$\hfill} \caption{The four reclasses of the uniform matroid $U_{3,6}$.} \label{fig:-1} \end{figure} % % Figure~\ref{fig:-1} depicts the wiring diagrams %of the four reclasses % for $[\Oscr_i]$, $i=1,2,3,4$. % $\Oscr_1,\Oscr_2,\Oscr_3,\Oscr_4$. %of $U_{3,6}$. % We remark that all % four diagrams could be drawn with straight lines, % since each $\Oscr_i$ is $\RR$-representable. The first diagram shows an orientation with imbalance~$2$. %To see that other three reclasses have no such orientation, We claim that the other three reclasses have no such orientation. Let $P$ be a odd-sided polygonal cell in a diagram having imbalance~$2$. By considering adjacent vertices on $P$, one sees that $P$ lies on the positive side of either all or none of its bounding curves. All three diagrams have two adjacent odd polygons, %which makes an orientation of imbalance~$2$ impossible. which leads to an easy contradiction. Since all cocircuits have size~$4$, the oriented flow number of $[\Oscr_i]$ equals $2$ or $4$. Therefore $\phio([\Oscr_1]) = 2$ and $\phio([\Oscr_i]) = 4$ for $i=2,3,4$. % % There exist no such orientations for the other three reclasses. % (To see this, note that the cocircuits have all size $4$, % and so imbalance must be either $2$ % or $4$. % Now consider one of the little triangles; % its lines allow only one orientation, up to symmetry, possibly achieving % imbalance~$2$. This partial orientation then uniquely extends along % other triangles, leading to a contradiction. In $\Oscr_4$, e.g., we % derive, starting at the dark grey triangle, % extending along the two adjacent triangles, % a contradiction at the light grey triangle.) \comment{\footnotesize "Figure 1 depicts two of the four reclasses, $\Oscr_1$, $\Oscr_2$ of $U_{3,6}$. The orientations shown are optimal in the definition of $\phio(\Oscr)$." The caption should read "Optimal orientations of two reclasses..." There are exactly three vertices in the second diagram whose cocircuits have imbalance 4 (they are on the little triangle in the right side of the diagram). Should we highlight this? Some of the elements are hard to see in black/white. } \end{example} In case $M$ is graphic, $\phio(M)=\phi_c(G)$ is the \DEF{circular flow number} of a graph~$G$. This graph invariant, essentially introduced by Tutte \cite{Tu54}, is also of contemporary interest \cite{SeySurv,Zhu2}. Seymour~\cite{Sey6} showed that $\phi_c(G) \le 6$ for any $2$-edge connected graph~$G$. % % More generally if $A$ is a totally unimodular matrix, then % $\Oscr=\Oscr[A]$ is an oriented regular matroid (a matroid is {\em regular} % if it can be represented as a vector configuration over any % field), and there is an algebraic description of the oriented flow More generally, there is an algebraic description of the oriented flow number $\phio(M)$ of any regular matroid implicit in the work of Hoffman~\cite{Hof}, and made explicit in~\cite{GTZ}. In particular, if $A$ is a totally unimodular matrix representing the regular matroid $M$, then $$ \phio(M) = \inf\{ \alpha \in \RR \mid \mbox{$\exists x \in \RR^E$, $Ax=0$, $1 \le |x_e| \le \alpha-1$ for $e \in E$ }\}. $$ %A \DEF{coloop} %is a cocircuit of size one. If $\Oscr$ has a coloop, then %LUIS: fixed error %$\chio(\Oscr) = \infty$. $\phio(\Oscr) = \infty$. The converse also holds, since every coloop-free oriented matroid has a \DEF{totally cyclic} reorientation, one in which every signed cocircuit $\vB$ satisfies $B^+, B^- \ne \emptyset$. %This folklore result is implicit in~\cite{?}, for example. With this terminology, we may restate our main result. \begin{theorem} For any coloop-free oriented matroid $\Oscr$ of rank $r$, % and having no coloops, $$ \phio(\Oscr) \le 14 r^2 \ln r. $$ \end{theorem} % % The \DEF{dual} of an oriented matroid $\Oscr = (M, \vCscr, \vBscr)$ % is the oriented matroid $\Oscr^* = (M^*,\vBscr,\vCscr)$, where $M^*$ % is the dual matroid of $M$. %Thus We may define the `chromatic number' of $\Oscr$ to be the invariant $$ \chio(\Oscr) = \phio(\Oscr^*). $$ Incidentally, $\chio(\Oscr)$ is much easier than $\phio(\Oscr)$ to bound by a function of the rank $r = \rk(\Oscr)$. Since no circuit of $\Oscr$ has cardinality more than $r+1$, no circuit of $\Oscr$ has imbalance greater than $r+1$ in a totally cyclic orientation of~$\Oscr^*$. It follows that $\chio(\Oscr) \le r+1$ for any loopless oriented matroid $\Oscr$ of rank $r$. This bound is best possible since it is achieved when $\Oscr$ is (an orientation of) the complete graph $M(K_{r+1})$. % An \DEF{orientation} of a matroid $M$ is an oriented matroid of the % form $(M,\vCscr, \vBscr)$. We say $M$ is \DEF{orientable} if it has % an orientation. Not all matroids are orientable. For example, a % binary matroid, i.\ e.\ a matroid representable by a matrix over GF(2), is % orientable if and only if %%it does not contain a minor isomorphic to the Fano matroid $F_7$ or its dual. % it is regular. %% The orientations of $M$ are partitioned % into \DEF{reorientation classes}, where the class of % $\Oscr$ is $[\Oscr] = \{ \Oscr_{\Ror} \mid \Ror \subseteq E\}$. % For sake of brevity, % we say that $[\Oscr]$ is a \DEF{reclass} of $M$. % An orientable matroid may have several distinct reclasses. % However all regular matroids, including graphs and cographs, % have a unique reclass. % Recall, that if $\Oscr = (M, \vCscr, \vBscr)$ then % $\Ror \subseteq E(\Oscr)$ is a {\em connected component of % the underlying matroid, % $M$}, if $I$ is minimally non-empty with the property that all % circuits (or, equivalently, cocircuits) % of $\Oscr$ are either disjoint from or completely contained in $I$. % (Notice that, in graph theory setting, % matroid components correspond to vertex $2$-connected graph components. % There is, obviously, no analogue of simple graph connectivity in matroids.) % Thus, for any connected component $I$, we have % $\Oscr_{\Ror} = \Oscr$. Indeed each reclass of $M$ contains % precisely $2^{|E|-\omega}$ orientations of $M$, where $\omega$ is % the number of connected components of $M$. Matroidal notions such % as independence, simplicity, flats, and the rank function $\rk(\cdot)$ carry % over from $M$ to any orientation $\Oscr$ of $M$, and to any reclass % $[\Oscr]$. The oriented flow number $\phio([\Oscr])$ of a reclass % is well defined. % The oriented flow number of an orientable matroid % $M$ is \emph{not} well defined. % % \begin{example} % \label{eg:U3,6} % The uniform matroid $U_{3,6}$ is orientable % and has precisely four reclasses~\cite{F}, % $[\Oscr_i]$, $1\le i \le 4$ (see Figure~\ref{fig:-1} for their geometric representations). % They satisfy % $ \phio([\Oscr_1]) = 2$ and $\phio([\Oscr_i]) = 4$ for $i=2,3,4$. % \end{example} % %%%%%%%%%%%%%%%%%%%%%%% % Any rank~$3$ reclass $[\Oscr]$ of a simple matroid $M$ may be %% (i.e., without loops or parallel elements) % conveniently viewed as a $2$-pseudo\-sphere complex which is affinely % represented by a \DEF{wiring diagram}. A wiring diagram is a set of % smooth plane curves $\{C_e \mid e\in E\}$, each joining a pair of opposite % boundary points of a fixed disc $D$ in the plane. Any two curves % must cross exactly once, and are otherwise disjoint. Each crossing % point $x$ is a \DEF{vertex} which corresponds to the matroid % hyperplane $\{e\in E \mid C_e \ni x\}$ and the complementary cocircuit % $\{ e \in E \mid C_e \not\ni x\} \in \Bscr(\Oscr)$. An oriented matroid % in $[\Oscr]$ is determined by designating, for each $e \in E$, one of % the two components of $D-C_e$ as being the ``positive side'' of % $C_e$. Each element~$e$ of a cocircuit $B$ is signed according to % whether the corresponding vertex lies on the positive or negative % side of $C_e$ (recall Figure~\ref{fig:cocircuit}). If $\Oscr$ is not % simple, then all elements of one parallel class $[e]$ are associated % to the same curve~$C_e$, although each element in $[e]$ is % independently oriented. Loops, geometrically corresponding to the % full sphere, are not contained in any cocircuit and, thus, do not % matter in our context. We may record the cardinality of $[e]$ on the % diagram, and use arrows to indicate the positive side of each % element. The boundary of $D$ is called the \DEF{equator} of the % diagram. Several wiring diagrams may correspond to the same oriented % matroid since there is choice in the location of the equator. % % \begin{figure}[htb] % % \epsfxsize=11.3truecm % % \epsfxsize=\hsize % % \centeredgraphics{u36d.eps} % \begin{center} % \includegraphics[width=11.3cm]{u36d.eps} % \end{center} % \hbox to \hsize{\hfill $\Oscr_1$ \hfill\hfill ~~$\Oscr_2$ % \hfill\hfill ~~$\Oscr_3$ \hfill\hfill ~$\Oscr_4$\hfill} % \caption{The four reclasses of the uniform matroid $U_{3,6}$.} % \label{fig:-1} % \end{figure} % % Figure~\ref{fig:-1} depicts the wiring diagrams of the four reclasses % $\Oscr_1,\Oscr_2,\Oscr_3,\Oscr_4$ of $U_{3,6}$. We remark that all % four diagrams could be drawn with straight lines. The first diagram % $\Oscr_1$ has an orientation with imbalance~$2$. There exist no such % orientations for the next three diagrams. (To see why, notice that % the cocircuits have all size $4$, and so imbalance must be either $2$ % or $4$. Now consider one of the little triangles; its lines allow % only one orientation, up to symmetry, possibly achieving % imbalance~$2$. This partial orientation then uniquely extends along % other triangles, leading to a contradiction. In $\Oscr_4$, e.g., we % derive, starting at the dark grey triangle, % extending along the two adjacent triangles, % a contradiction at the light grey triangle.) % \comment{\footnotesize "Figure 1 depicts two of the four % reclasses, $\Oscr_1$, $\Oscr_2$ of $U_{3,6}$. The orientations % shown are optimal in the definition of $\phio(\Oscr)$." The % caption should read "Optimal orientations of two reclasses..." % There are exactly three vertices in the second diagram whose % cocircuits have imbalance 4 (they are on the little triangle in the % right side of the diagram). Should we highlight this? Some of the % elements are hard to see in black/white. } % %% \begin{figure}[htb] %% % \epsfxsize=11.3truecm %% \epsfxsize=8.0truecm %% \centeredgraphics{u36.eps} %% \caption{Two reclasses $\Oscr_1$ and $\Oscr_2$ of $U_{3,6}$} %% \label{fig:-1} %% \end{figure} % %\medskip % % The following additional facts may be found in \cite{BLSWZ}, and are % used tacitly in this paper. %%\comment{Luis:Delete or undelete these as you wish} % \begin{enumerate}\vspace*{-\smallskipamount} %% \item A \DEF{flat} is a maximal set of elements of fixed rank. %% The intersection of any two flats is a flat. %% For any flat $F$ of $\Oscr$, $F' \subseteq E-F$ is a flat in %% $\Oscr / F$ if and only if $F' \cup F$ is a flat in $\Oscr$. %% A subset $F\subseteq E$ is a hyperplane %% (i.e.~a flat of corank 1) of $\Oscr$ %% if and only if $E-F$ is a cocircuit of $\Oscr$. % \item An oriented matroid $(M,\vCscr,\vBscr)$ is uniquely determined % by either of the pairs $(M,\vCscr)$ or $(M,\vBscr)$. %% As with matroids, each of these pairs is subject to an %% \DEF{strong elimination axiom}: %% \begin{quote} %% For $X,Y\in \Cscr$ and $e \in X^+ \cap Y^-$, %% and $f \in (X^+ - Y^-)\cup(X^- - Y^+)$, %% there exists $Z\in \Cscr$ with %% $f\in Z$ and %% each of $Z^+$, $Z^-$ contained in one of %% $(X^+ \cup Y^+)-\{e\}$ or $(X^- \cup Y^-)-\{e\}$. %% \end{quote} %%\item Every coloop-free oriented matroid $\Oscr$ %% has a \DEF{strong reorientation}, %% a reorientation $\Oscr_{\Ror}$ %% such that $B^+, B^- \ne \emptyset$ %% for all $\vec B \in \vBscr_{\Ror}$. %% Thus the circular flow number of a reclass is %% at most the size of its largest cocircuit. %%\item The \DEF{dual} of $\Oscr = (M,\vCscr,\vBscr)$ %% is defined by $\Oscr^* = (M^*,\vBscr,\vCscr)$, %% where $M^*$ is the dual matroid of $M$. %\item For disjoint subsets $S,T \subseteq E(\Oscr)$, the \DEF{minor} % $\Oscr / S \backslash T$ is the orientation % of the matroid minor $M/S\backslash T$ obtained by % restricting the signings in % $\vCscr \cup \vBscr$ % to the circuits and cocircuits of $M/S\backslash T$. %%\item Matroid elements are partitioned into %% \DEF{parallel classes}, where the class of $e \in E$ is %% $ [e] = \{e\} \cup \{f \in E \mid \{e,f\} \in \Cscr \}$. %% The \DEF{multiplicity} of $e$ is $|[e]|$. %% Any orientation $\Oscr$ of $M$ induces a partition %% $ [e] = [e]^+ \cup [e]^-$ on each parallel class such that %% each part is a subset of either $B^+$ or $B^-$ for %% every signed cocircuit containing $e$. %% %The \DEF{underlying simple oriented matroid} of $\Oscr$ %% %is obtained by deleting all loops and deleting all but one element from %% %each of $[e]^+$, $[e]^-$ for each parallel class $[e]$. %%\item A binary matroid is orientable if and only if is it is regular. %%\item A regular matroid has a unique reclass. %% For oriented regular matroids, the two sets in (\ref{eq_orth}) %% always have equal cardinalities. %\item There is a bijective correspondence between % \DEF{simple} reclasses $[\Oscr]$ % (having no loops or multiple elements) % and topological objects called \DEF{pseudosphere complexes}. % This is due to Folkman and Lawrence~\cite{FoLa} % and Edmonds and Mandel~\cite{Mandel}. % \item Any matroid representable over $\RR$ is orientable. Every % $\RR$-representa\-tion $M = M[A]$, $A \in \RR^{R\times E}$ % determines an orientation $\Oscr = \Oscr[A]$ of $M$. The % signings of the cocircuits are derived as follows: Consider the % columns $A_{.e}$ of $M$ as linear forms in $\RR^R$. We may % identify the 1-dimensional space spanned by that form in dual % space with its nullspace and thus with a linear hyperplane. If % $M[A]$ is simple, then the pseudosphere complex corresponding % to $[\Oscr[A]]$ is a complex $\Sscr$ of subspheres of $S := \{ % x \in\RR^R \mid ||x||=1\}$. Each matroid flat $F \subseteq E$ % (see~\cite{BLSWZ} Remark 3.2.2) corresponds to the % subsphere $S_F = S \cap {\rm nullspace}(A_F) \in \Sscr$, where % $A_F$ is the submatrix of $A^T$ whose rows are selected by $F$. % The elements of $M$ correspond to \DEF{pseudohyperspheres} $S_{\{e\}} % \in \Sscr$. The hyperplanes of $M$ correspond to $0$-spheres % in $\Sscr$. Each of the two points constituting a $0$-sphere % is called a \DEF{vertex} of~$\Sscr$. The signings $\{B^+,B^-\}$ % of a cocircuit $B$ in $\Oscr[A]$ are given via % $$ % B^+ = \{ e\in B \mid A_{\{e\}} x >0 \} % \qquad % B^- = \{ e\in B \mid A_{\{e\}} x <0 \} % $$ % where $x$ ranges over the two vertices corresponding to the % hyperplane $E-B$. % %%\item Not all orientable matroids are $\RR$-representable. %% However %% any PSC may be obtained from a real sphere complex %% by suitably ``perturbing'' coincident hyperspheres. % %%\item A general oriented matroid may be viewed as %% a PSC which has been endowed with additional information. %% %% {\footnotesize %% Deleting a \DEF{pseudohypersphere} $S_{\{e\}}\in \Sscr$ %% %from the underlying sphere %% leaves two open balls called %% \DEF{sides} of $S_{\{e\}}$. %% A reorientation in $[\Oscr]$ is determined %% by designating one side of each $S_{\{e\}}$ as %% being ``positive''. %% A nonsimple oriented matroid $\Oscr$ is represented as a PSC %% with a pseudosphere $S_{[e]}$ for each parallel class. %% To record the orientation, we %% associate the two sets $[e]^+$, $[e]^-$ with the two sides of $S_{[e]}$. %% Separately, we record the number of loops in $\Oscr$. %% %The pair determines which elements of $[e]$ are oriented toward the %% %positive side of $S_[e]$. %% } % %%\item Any rank $3$ PSC can be affinely represented by a %% \DEF{wiring diagram}. % %% {\footnotesize %% A wiring diagram is a set of smooth plane curves %% $\{C_e \mid e\in E\}$, each joining a pair of %% opposite boundary points of a %% fixed disc $D$ in the plane. %% Any two curves must cross exactly once, %% and are otherwise disjoint. %% Each crossing point $x$ corresponds to %% the matroid hyperplane %% $\{e\in E \mid C_e \ni x\}$. %% An orientation of the PSC is determined by designating, %% for each curve $C_e$, one of the two components of $D-C_e$ %% as being the ``positive side'' of $C_e$. %% Each element~$e$ of a cocircuit $B$ is signed %% according to whether the crossing %% point for the hyperplane $E-B$ lies on the positive %% or negative %% side of $D-C_e$, for $e \in B$. %% } % %%\item Deleting one element from %% each of $[e]^+$, $[e]^-$, for some parallel class $[e]$, %% can not decrease the imbalance of any cocircuit in $\Oscr$. % %%\item The circular flow number of the direct sum %% $\Oscr \cup \Oscr'$ is the larger of %% $\phio(\Oscr)$ and $\phio(\Oscr')$. % %%\item If $e,f\in E$ are coparallel in in $\Oscr$, then %% $\phio(\Oscr) = \phio(\Oscr/e)$. % %\end{enumerate} % %%%%%%%%%%%%%%%%%%%%%%%%%% %Luis: The following has a problem, so save it for the next paper... % % The object of this paper is to bound the function % $$ %\phio(r) = \supp \{ \phio(\Oscr): % \mbox{$\Oscr$ is coloop free of rank $r$} \}. %$$ %Any oriented matroid (or reclass) %achieving this bound is said to be %\DEF{$r$-extremal}. %An $r$-extremal reclass is \DEF{minimal} %%if no proper sub-oriented matroid is $r$-extremal. %if deleting some of its elements does not result in another %$r$-extremal reclass. %Property ?? implies that %$\phio(r)$ is nondecreasing with $r$. %Together with Property ??, it also implies that %every $r$-extremal reclass is connected. % %Trivially, we may define the loop to be $0$-extremal %and define $\phio(0)=2$. % %If $\Oscr$ has rank $1$, %then $\Oscr$ contains a unique cocircuit $B$. %Let $n=|B|$. %If $n$ is even, then $\phio(\Oscr)=2$. %If $n=2k+1$, then $\phio(\Oscr)=2+1/k$. %Thus $\phio(1)=3$, %and the three-element cocircuit $\theta$ %is the only $1$-extremal reclass. %We shall see in Section ??, %that $\phio(2)=3$, and that there are two $2$-extremal reclasses, %the four point line, $U_{2,4}$, %and a series extension of $\theta$. % %When studying $\phio$, %one should not restrict attention to simple reclasses. %This is particularly true when $\phio([\Oscr])$ is close to two. %For example, vertices of degree two play a major role when %studying graphs which have homomorphisms onto large odd circuits. %However, parallel elements play only a minor role in determining $\phio(r)$. %A reorientation of $\Oscr$ is \DEF{optimal} if all %cocircuits have imbalance at most $\phio(\Oscr)$. % %\begin{lemma} %Every minimally $r$-extremal reclass $[\Oscr]$ different from $\theta$ %%has multiplicity at most two. %%Further, if $e$ has multiplicity $2$ in $\Oscr$, %%then for some $f\in E$, %%$\{f\} \cup [e]$ is a $3$-element cocircuit of $\Oscr$. %%{\bf Can more can be said in this case?} %is simple. %\end{lemma} %% %\noindent{\bf Proof.} %Let $[e]$ be a parallel class of size at least two in a %minimally $r$-extremal $\Oscr$. %Deleting two elements $e,e' \in [e]$ from $\Oscr$ %must result in a coloop $f$, %for otherwise by Property ??, %$\phio(\Oscr) \le \phio(\Oscr\backslash\{e,e'\}) < \infty$ %which contradicts that $\Oscr$ is minimally $r$-extremal. %Thus either $ [e] = \{e,e',f\}$ is a cocircuit of $\Oscr$ %or $[e]=\{e,e'\}$ and $[e] \cup f$ is a cocircuit of $\Oscr$. %In the first case, $\Oscr = \theta$ since $\Oscr$ is connected. % %We argue the second case as follows. %{\bf This is sketchy and may be wrong.} %%Let $B$ be the cocircuit $[e] \cup f$ in $\Oscr$. %Let $\Oscr' = \Oscr\backslash e'$, and %let $\Oscr'' = \Oscr / [e]$. % %Since $e$,$f$ are coparallel in $\Oscr'$, %there is a bijective correspondence between cocircuits in $\Oscr$ %containing $f$ and those containing $[e]$. %Also there is a bijective correspondence between the strong %reorientations of $\Oscr''$ and those of $\Oscr'$, and %$\phio(\Oscr'') = \phio(\Oscr')$. %We aim to show $\phio(\Oscr') \ge \phio(\Oscr)$, %contradicting that the minimality of $\Oscr$. % %Each reorientation of $\Oscr$ naturally restricts to a reorientation %of $\Oscr'$. %Conversely, %each strong reorientation $\Oscr'_{\Ror}$ arises from %one of two strong reorientations, %say $\Oscr_{\Ror_1}$ and $\Oscr_{\Ror_2}$, %of $\Oscr$ in this way. %The two reorientations of $\Oscr$, %differ only in the sign of $e'$. %Assume that $\Oscr_{\Ror_1}$ is the reorientation in %which $e$ and $e'$ are in the same part of $([e]^+, [e]^-)$. % % %We shall show that for any optimal reorientation $\Oscr'_{\Ror}$ %of $\Oscr'$, %either $\Oscr_{\Ror_1}$ or $\Oscr_{\Ror_2}$ has %no cocircuit of imbalance greater than $t := \phio(\Oscr')$. %Suppose this is not the case. %Let $B_1$, $B_2$ be cocircuits in $[\Oscr]$ such that %$i(B_i) > t$ in $\Oscr_{\Ror_i}$ ($i=1,2$). %Then each $B_i$ is not a cocircuit in $\Oscr'_{\Ror}$, %so $B_i$ contains $[e]$, %and $B_i-e'$ is a cocircuit of $\Oscr'_{\Ror}$. %We assume $B_i = \{B_i^+, B_i^-\}$ is the signing of $B_i$ %in $\Oscr_{\Ror_i}$, where $|B_i^-| \le |B_i^+|$. %Since each $B_i-\{e'\}$ is not $t$-unbalanced %{\bf Defined yet?} %in $\Oscr'_{\Ror}$, %and observing the inequality %$$ %\frac {b-1}{a} < \frac{b}{a} < \frac{b-1}{a-1} %$$ %for $b > a$, %we must have %$e' \in B_1^+ \cap B_2^+$, so %$e \in B_1^+ \cap B_2^-$ and %$$ %|B_i - \{e'\}| \le t|B_i^-| < |B_i| %$$ %for $i=1,2$. %If $\Oscr$ were a directed graph, the situation would be as %depicted below. % % \begin{figure}[htb] % \epsfxsize=11.5truecm % \centeredgraphics{fig2.eps} % \caption{First caption} % \label{fig:2} % \end{figure} % %Let us write $B_i^0$ for $E(\Oscr)-B_i$, ($i=1,2$). %For $\sigma, \tau \in \{+,-,0\}$ let us write %$$ % \Nscr^{\sigma \tau} = B_1^\sigma \cap B_1^\tau . %$$ % %Each of the sets $\Nscr^{\sigma \tau}$ except $\Nscr^{00}$ %is depicted as a ``fat arrow'' labeled with $\sigma\tau$ %in the diagram, %where $e \in \Nscr^{+-}$ and $f \in \Nscr^{00}$. %The arc for $e'$ is dashed and not oriented since %$e'$ belongs to either $\Nscr^{+-}$ or $\Nscr^{-+}$ %depending on whether we are in $\Oscr_{\Ror_1}$ or $\Oscr_{\Ror_2}$. % % %The two ``wide fat arrows'' for $\Nscr^{+0}$ or $\Nscr^{0+}$ %are intended to suggest $|B_i^+| > (t-1)|B_i^-|$, $i=1,2$. %The fat arrows representing %$\Nscr^{+-}$ and $\Nscr^{-+}$ %have been shaded. %Let $g$ be any element belonging to one of %the ``unshaded wide arcs'', %$g \in % \Nscr^{+0} \cup \Nscr^{-0} \cup % \Nscr^{0+} \cup \Nscr^{0-} \cup % \Nscr^{++} \cup \Nscr^{++}$. %Let $N = B_1 \cup B_2$. %Depending on the location of $g$, %we may apply the strong elimination axiom with either %($X=B_1$, $Y=B_2$, $e$ and $f$) or %($X=B_2$, $Y=B_1$, $e'$ and $f$) %[we are cheating a bit here since we are really %%deleting $e'$ from both $\Oscr_{\Ror_1}$ and $\Oscr_{\Ror_2}$ %%to get the corresponding %applying the axiom to %$\Oscr'_{\Ror} := \Oscr_{\Ror_1}\backslash e' = \Oscr_{\Ror_2}\backslash e'$ %and also to $\Oscr'_{\Ror \Delta \{e\}}$]. %Thus for all such $f$, %there is a cocircuit $B_f \subseteq N-[e]$ in $\Oscr'$ which contains $f$, %and respecting the orientation. %This means that there are no coloops in the oriented matroid %minor obtained by contracting $\Oscr$ down to $\Nscr$ and %deleting $\Nscr^{+-} \cup \Nscr^{-+}$. % % % %Here is where we take a leap of faith, and assume that %there is a convex combination of the $B_f$ such that %every element of an unshaded wide arc is equally covered. %By an averaging argument, one of these will have imbalance %greater than $\phio(\Oscr)$. %\vspace{3cm} % %\QED % %We suspect that, %for $r\ge 3$, %every $r$-extremal reclass is simple, %but we do not have a proof of this. % \section{Low Rank} The \DEF{odd cogirth} of an oriented matroid $\Oscr$ is the least odd integer $2k+1$ such that $\Oscr$ has a cocircuit of cardinality $2k+1$. We define the \DEF{odd cogirth bound number} of $\Oscr$ to be the rational number $$ \ocb(\Oscr) = 2 + 1/k ,$$ where $2k+1$ is the odd cogirth of $\Oscr$. If $\Oscr$ has no odd cocircuits then we define its odd cogirth to be $\infty$ and $\ocb(\Oscr) = 2$. The imbalance of any signed cocircuit of size $2k+1$ is at least $(2k+1)/k$. Thus we have the following. \begin{proposition}% For any oriented matroid $\Oscr$ we have $\phio(\Oscr) \ge \ocb(\Oscr)$. \end{proposition}% % This bound is generally quite weak. It fails to be tight already for the orientations of the graphic matroid $M(K_4)$, and for the other orientations in Example~\ref{eg:U3,6}. However, the bound is exact for oriented matroids of low rank. \begin{lemma} \label{lem:rank2} Every oriented matroid $\Oscr$ of rank at most $2$ satisfies $\phio(\Oscr) = \ocb(\Oscr)$. In particular, $\phio(\Oscr) \le 3$ if $\Oscr$ is coloop-free. \end{lemma} \begin{proof} %We may assume that $\Oscr$ has no loops. If $\rk(\Oscr)=1$, then $\Oscr$ is an orientation of a single parallel class. %of size at least two. Orienting this cocircuit as equitably as possible gives $\phio(\Oscr) = \ocb(\Oscr)$. If the rank equals two, then we may affinely represent $\Oscr$ as a list of points $P = (p_e \mid e \in E)$ on the real number line. Let us label the elements with $e_1, \ldots ,e_n$ so that $p_{e_1} \le \ldots \le p_{e_m}$. For each $p \in P$ there is a corresponding cocircuit $B_p = \{e\in E \mid p_e \ne p\}$. We sign $B_p$ according to $$ B_p^+ = \{ e_i \mid p_{e_i} < p \mbox{ and $i$ is odd} \} \cup \{ e_i \mid p_{e_i} > p \mbox{ and $i$ is even} \}. $$ It is easy to verify that this gives an orientation of $\Oscr$, and that every cocircuit $B_e$ satisfies $|B_e^+|-|B_e^-| \in \{0, \pm 1\}$. It follows that $\imbal(B_e)$ equals $ 2$ if $|B_e|$ is even, and equals $2+1/k$ if $|B_e|=2k+1$. Therefore $\phio(\Oscr) = \ocb(\Oscr)$. \end{proof} \section{Random Resignings and Rank $3$} \label{sect:Rank 3} We shall make use of the Chernoff bound from probability theory (see e.g.\ \cite{AS}). \begin{lemma} If $X_1, \ldots , X_m = \pm 1$ are i.i.d.\ random variables with probability $1/2$, then for $\lambda > 0$ we have $$ \prob\left(\left|\sum_i X_i\right|>\lambda \sqrt{m} \right) < 2 e^{ -\lambda^2 / 2}. $$ \QED \end{lemma} \vspace{-2ex} % too much space Here is some convenient terminology. Let $A$ be a subset of a cocircuit~$B$, and let $\vB = \{B^+,B^-\}$ be a signing of $B$. For $s\ge2$, we say that $A$ is \DEF{$s$-unbalanced in $\vB$} if either one of $A \cap B^+$ and $ A \cap B^-$ is empty or $$ \frac{|A|}{\min\{|A \cap B^+|,|A \cap B^-|\}} > s. $$ If $\vB$ is a signed cocircuit in an oriented matroid $\Oscr$, and $B$ is $s$-unbalanced in $\vB$, then we say that $B$ is \DEF{$s$-unbalanced in $\Oscr$}. %The parameter of interest is therefore Therefore \begin{equation} \label{eq:referees} \phio(\Oscr) = \min_{\Ror\subseteq E} \inf\{ s\in \RR: \mbox{no cocircuit is $s$-unbalanced in $\Oscr_{\Ror}$} \}. \end{equation} % A \DEF{random resigning} of a subset~$R \subseteq E(\Oscr)$ is a reorientation $\Oscr_{\Ror}$ where $\Ror$ is uniformly selected among the subsets of~$R$. \begin{lemma} \label{lem-cher-app} \label{lem:randbound} Let $A$ be a nonempty subset of a cocircuit $B$ in $\Oscr$, and let~$R$ satisfy $A \subseteq R \subseteq E$. Let $\vec B$ be the signing of $B$ in a random resigning of $R$. Then for $s \ge 2$ the probability that $A$ is $s$-unbalanced in $\vB$ is less than $$ 2 \exp \left( -\left(1-\frac2s\right)^2 \frac{|A|}{2} \right). $$ \end{lemma} \begin{proof} We define random variables $\{X_e \mid e \in A \}$ by $$ X_e = \left\{\begin{array}{rl} 1 & \mbox{ if $e \in B^+$} \\ - 1 & \mbox{ if $e \in B^-$}. \end{array}\right. $$ Then $A$ is $s$-unbalanced in $\vB$ if and only if $|\sum_{e\in A} X_e|> (1-\frac2s)|A|$. Since $A \subseteq R$, the random variables are i.i.d.~among the resignings of $R$. The result follows by applying the Chernoff bound with $\lambda = \left(1-\frac2s\right) \sqrt{|A|}$. \end{proof} We shall now prove a bound on $\phio(\Oscr)$ in case $\Oscr$ has rank $3$. \smallskip Figure~\ref{fig:0} shows three oriented wiring diagrams which are all simple, except for one element of multiplicity two or three. More precisely, each example is the case $n=4$ of a family of wiring diagrams on $n+3$ elements. Orientations are given by the arrows shown. %With the elements labeled as shown, We say that these orientations are \DEF{alternating} with respect to % the sequence $e_1, e_2, \ldots, e_n, f_1, f_2, f_3$ and the equators shown. The reader will notice that the orientation described in the proof of Lemma~\ref{lem:rank2} is alternating in a similar sense. Alternating orientations of matroids of rank~$\le 3$ tend to result in good upper bounds on $\phio(\Oscr)$. \begin{figure}[htb] % \epsfxsize=11.3truecm % \epsfxsize=8.0truecm % \centeredgraphics{fig0.eps} \begin{center} \includegraphics[width=11.0cm]{fig0.eps} \end{center} \caption{Three wiring diagrams with alternating orientations. }% The bold line represents two or three parallel elements.} \label{fig:0} \end{figure} %%%%%%%%%%%%%%%%%%5 \begin{lemma} \label{lem:rank3} Let $\Oscr$ be a coloop-free oriented matroid of rank $3$. %If $|E(\Oscr)| \ge 19$, then Then $\phio(\Oscr) \le 17$. Moreover, if $\Oscr$ is simple and $n = |E(\Oscr)|$ is large, then $$ \phio(\Oscr) \le \max\left\{ \ocb(\Oscr), \, 2+O\left((n/\ln n)^{-1/3}\right)\right\}. $$ In particular, if $n \ge 159$ ($n \ge 427$), then $\phio(\Oscr) \le 4$ (resp.\ $\phio(\Oscr) \le 3$). \end{lemma} %%%%%%%%%%%%%%%%%%5 \begin{proof} We may assume $\Oscr$ has no loops. Suppose that $S = \{ f_1, f_2\}$ are parallel elements in $\Oscr$ such that $\Oscr\backslash S$ is coloop-free. By orienting $f_1$ and $f_2$ oppositely and using induction, one easily sees $\phio(\Oscr) \le \phio(\Oscr\backslash S) \le 17$. Thus, we may assume that $\Oscr\backslash S$ has a coloop for all such pairs and, hence, any two parallel elements of $\Oscr$ are contained in a cocircuit of size $3$. If $\Oscr$ is not simple, then $\Oscr$ has $n+3$ elements for some $n\ge 0$, and $\Oscr$ corresponds to one of the three wiring diagrams as drawn in Figure~\ref{fig:0} (the cocircuit is $\{f_1, f_2, f_3\}$). The alternating reorientations shown there, imply that $\phio(\Oscr) \le 3$ if $\Oscr$ has no coloops. Thus we may assume $\Oscr$ is simple. Let $k = \min\{|B| \mid B \in \Bscr(\Oscr) \}$ be the \DEF{cogirth} of $\Oscr$. Let $B_0$ be a cocircuit of size~$k$ in $\Oscr$. We may choose the equator of a wiring diagram to be near the vertex corresponding to $B_0$, so that the left half of the disk is as shown in Figure~\ref{fig:0.5} (the diagram is undetermined under the white box). We consider an alternating reorientation $\Oscr'$ of $\Oscr$ as shown in the diagram. % \begin{figure}[htb] % \epsfxsize=4.3truecm % \centeredgraphics{fig0.5.eps} \begin{center} \includegraphics[width=4.3cm]{fig0.5.eps} \end{center} \caption{An alternating reorientation $\Oscr'$ defined by a smallest cocircuit $B_0$.} \label{fig:0.5} \end{figure} By design, we have $ \imbal_{\Oscr'}(B_0) \le \ocb(\Oscr) \le 3$. Every other cocircuit $B\in\Bscr(\Oscr')-\{B_0\}$ contains all but possibly one element of $E-B_0$. Since $\Oscr'$ is alternating, we therefore have $|B^+|, |B^-| \ge \lfloor (n-k-1)/2 \rfloor$. Since $|B| \le n-2$, this implies $\imbal_{\Oscr'}(B) \le g(n,k)$ where $$ g(n,k) =\frac{n-2}{(n-k)/2 -1} = \frac{2n-4}{n-k-2} . $$ Thus the reorientation $\Oscr'$ shows that if $2 \le k \le n-3$, then \begin{equation} \label{eq:phio1} \phio(\Oscr) \le \max\left\{ \,\ocb(\Oscr) ,\, g(n,k) \,\right\}. \end{equation} We note that $\ocb(\Oscr) > g(n,k)$ only if $k \le \sqrt{n-2}$. %%%%%%%%%%%% Let $\Oscr_{\Ror}$ be a random resigning of $E(\Oscr)$. Clearly, $\Oscr$ has at most $n \choose 2$ cocircuits, all of which have size at least $k$. By Lemma~\ref{lem:randbound}, the probability that some cocircuit of $\Oscr_{\Ror}$ is $s$-unbalanced is less than % \begin{equation} \label{eq:prob} 2 {n \choose 2}\exp \left( -\left(1-\frac2{s}\right)^2 \frac{k}{2} \right). \end{equation} % Let $f(n,k)$ denote the least real number $s > 2$ such that this expression is less than or equal to $1$. One can verify that $f(n,k)$ is well defined for $k > 2 \ln \left(2{n \choose 2 }\right)$. When $s \ge f(n,k)$, at least one of the random reorientations $\Oscr_{\Ror}$ has no $s$-unbalanced cocircuits. Therefore by (\ref{eq:referees}), if $\,4 \ln n \le k \le n-2$, then \begin{equation} \label{eq:phio2} \phio(\Oscr) \le f(n,k). \end{equation} For fixed $n \ge 5$, we find that $g(n,k)$ is increasing as $k$ increases from $2$ to $n-3$, whereas $f(n,k)$ decreases with $k$, for $4 \ln n \le k \le n-2$. % % $\frac{\partial}{\partial k} g(n,k) >0$ for $2 \le k \le n-3$, %whereas % $\frac{\partial}{\partial k} f(n,k) <0$ for $4\ln n \le k \le n-2$. % The bounds in~(\ref{eq:phio1}) and~(\ref{eq:phio2}) are illustrated in Figure~\ref{fig:3} for $n=30$. %LUIS: fixed and clarified In the plot of $\ocb(\Oscr)$ versus $k$ in this figure reflects the fact $\ocb(\Oscr) = 2k/(k-1)$ if the cogirth $k$ is odd, but that one can only deduce %$2 \le \ocb(\Oscr) \le 2(k+1)/k$ $\ocb(\Oscr) \in \{2\}\cup\{2+1/i \mid i \ge k/2 \}$ if $k$ is even. %, and equal to 2 when $k$ is even. % %LUIS: Some funny bug, TeXShop can not handle figures within proof environment.-OK \begin{figure}[htb] % % \epsfxsize=9.0truecm % % \centeredgraphics{fig3.eps} \begin{center} \includegraphics[width=9.0cm]{fig3.eps} \end{center} \caption{$f(n,k)$, $g(n,k)$, and $\ocb(\Oscr)$ versus $k$, when $n=30$.} \label{fig:3} \end{figure} Using a computer algebra system, we find that $g(n,k) = f(n,k)$ when $$ k = k_0 = \sqrt[3]{2 (n-2)^2 \ln\left(n(n-1)\right)} . $$ We have shown $\phio(\Oscr) \le \max\{ \ocb(\Oscr), h(n)\}$ where $$ h(n) = g(n,k_0) = \frac {2n-4}{n\!-\!2-\!\sqrt[3]{2(n\!-\!2)^2\ln (n(n\!-\!1))} } % \le \frac {2n-4}{n-2-\sqrt[3]{(2n-4)^2\ln n} } = 2+O\!\left(\!\left(\frac{n}{\ln n}\right)^{-1/3}\right) . $$ Using the trivial bound $\phio(\Oscr) \le \max\{\,|B| \mid B \in \Bscr(\Oscr)\} \le n-2$ and the easily verified fact that $f(n,k_0) \le 17$ when $n\ge 19$, we have proven $ \phio(\Oscr) \le 17. $ We further find that $\phio(\Oscr) \le 4$ (resp.~$3$) provided that $n \ge 166$ (resp.~$712$). However, %there is an additional improvement to we can improve the above argument in case we are trying to prove $\phio(\Oscr)\le s$ for some $s \le 4$. When $n \ge 162$ one finds that $k_0 < (n-1)/2$, which roughly corresponds, by~(\ref{eq:prob}), to $s \le 4$. Since $\Oscr$ is simple, it contains at most one cocircuit of size less than $(n-1)/2$, and at most $$ {n \choose 2} - {{n-k}\choose 2} \le \frac{3n(n-2)}{8} $$ cocircuits of size at least $(n-1)/2$. For $s \ge \ocb(\Oscr)$, we may assume $k \ge (n-2)(s-2)/s$ since otherwise $\phio(\Oscr) \le s$ by~(\ref{eq:phio1}). Therefore, in case $k \le n/2-1$, %$\ocb(\Oscr) \le s \le 4$, we may replace~(\ref{eq:prob}) with the smaller quantity % Luis: I have put negative spaces due to overflow. $$ 2 \exp\!\left(\!-\!\left(\!1\!-\!\frac2{s}\right)^2 \!\frac{(n\!-\!2)(s\!-\!2)}{2s}\right) +2\! \left(\frac{3n(n\!-\!2)}{8} \right)\! \exp\!\left(\!-\!\left(\!1\!-\!\frac2{s}\right)^2\!\frac{n\!-\!1}{4} \right). $$ It is straight forward to verify that this expression is at most $1$ when $n \ge 427$ (for $s=3$), and when $n \ge 159$ (for $s=4$). %%%%%%% %The following could improve this to $\phio \le 16$ but I omit it. %Here is a slight improvement. %Suppose that the two smallest cocircuits $B_1, B_2 \in \Bscr(\Oscr)$ %have sizes $k_1$ and $k_2$ respectively. %We choose the equator as suggested in %Figure~\ref{fig0.5}. %Note the element containing the two vertices $x_1$, $x_2$ may not exist. %By considering the alternating orientation~$\Oscr''$ shown there, %one easily verifies %$$ %\imbal_{\Oscr''}(B_1) \le \frac{2k_1}{k_1-1} \qquad %\imbal_{\Oscr''}(B_2) \le \frac{2k_2}{k_2-2} %$$ %and that these imbalances never exceed $3$, even when $k_1$, $k_2$ are small. %Every other cocircuit $B \in \Bscr(\Oscr)-\{B_1,B_2\}$ %contains all but at most one element of both $B_1$ and $B_2$. %It follows that %$$ %|B^+| \ge \left\lfloor \frac{n-k_1-1}{2}\right\rfloor % + \left\lfloor \frac{n-k_2-1}{2}\right\rfloor % \ge n - \frac{k_1+k_2}{2} -2. %$$ %so %\begin{equation} %\label{eq:phio1A} %\imbal_{\Oscr''}(B) \le \max\left\{3,\frac{2n-4}{2n-k_1-k_2-4}\right\}. %\end{equation} %We repeat the previous argument %with~(\ref{eq:phio1A}) in place of~(\ref{eq:phio1}). % ...forget it... %%%%%%%% \end{proof} With extra work, the minor restriction that $\Oscr$ is simple can be omitted from the statement of Lemma~\ref{lem:rank3}. The bound %of Lemma~\ref{lem:rank3} $\phio(\Oscr) \le 17$ is probably far from optimal. %%%%%%% %Luis: If you do not like the following conjecture, % then uncomment the next three lines. %Indeed, we do not know of any coloop-free %rank $3$ oriented matroid $\Oscr$ for which $\phio(\Oscr) >4$. %Some experimental results appear in Section~\ref{sec:examples}. %%%%%%% \begin{conjecture} Every coloop-free oriented matroid $\Oscr$ of rank $3$ satisfies $\phio(\Oscr) \le 4$. \end{conjecture} \section{Dense Flats} \label{sec:dense flats} \nopagebreak % There are additional challenges when considering oriented matroids of rank greater than three. It is not clear how to define an ``alternating orientation'', so we shall resort to using random orientations. However a matroid of rank $4$ may have many small cocircuits, so we can not argue as in %the last part of the proof of Lemma~\ref{lem:rank3} to bound the probability of having an unbalanced cocircuit. We give here a way to address this problem. The following example helps to illustrate the forthcoming strategy. %\smallskip Let $G$ be graph obtained from the complete graph $K_{10}$ by replacing each vertex $v_i \in V(K_{10})$ with a copy, $K(i)$, of $K_{1000}$. For each $v_i v_j \in E(K_{10})$ there is an edge in $G$ joining an arbitrary vertex of $K(i)$ to an arbitrary vertex of $K(j)$. Each of the subgraphs $K(i)$ contains ${{1000}\choose 2}$ edges which form a flat, say $F_i$, in the polygon matroid $M(G)$. Because the graph~$G$ has cogirth only nine and a large number of cocircuits (about $2^{10000}$), a na\"{\i}ve application of Lemma~\ref{lem:randbound} would result in a very poor bound on $\phio(M(G_{20}))$. In general, a random orientation can not be shown to balance each of a large number of small cocircuits. The solution is to select one of the flats, say $F_1 = E(K(1))$, and to consider separately the cocircuits of $M(G)$ which intersect with $F_1$, and those that are disjoint from~$F_1$. Any cocircuit having an edge from $F_1$ has large cardinality, at least $999$, so there is good probability that they are all fairly well balanced in a random orientation of $G$. The cocircuits of $M(G)$ which are disjoint from $F_1$ are precisely the cocircuits of the contracted graph $G/F_1$. We select another flat, say $ F_2 = E(K(v_2)) \subseteq E(G/F_1)$, and partition the cocircuits of $G/F_1$ into those which contain an edge of $F_2$, and those which are disjoint from $F_2$. Again, cocircuits of the first type are large and easy to balance in a random orientation. After $10$ steps we are left with the graph $K_{10} = G / (F_1\cup\dots\cup F_{10})$. Although $K_{10}$ has small cocircuits, there are relatively few of them, so a probabilistic argument will again be successful. % To apply this type of argument to an arbitrary oriented matroid $\Oscr$, we must first define a suitable set of elements in~$\Oscr$ which can play the role of $F_i$ in this example. %equation~(\ref{eq:K10}). % Let $G_1$ be the complete graph $K_{10}$. % For $i\ge1$, let $G_{i+1}$ be the graph obtained from $G_i$ % by replacing each vertex $v \in V(G_i)$ with a copy % $K(v)$ of $K_{10}$. % For every edge $e \in E(G_i)$ joining $u$ to $v$, % there is an edge in~$G_{i+1}$, which is also labeled $e$, % and which joins an arbitrary vertex of % $K(u)$ to an arbitrary vertex of $K(v)$. % Therefore $|V(G_i)| = 10^i$ %% $|E(G_i)|={{10}\choose 2}\sum_{j=0}^{i-1}10^j$ % and % \begin{equation} % \label{eq:K10} % G_{i} = G_{i+1} /F_i % \mbox{\quad where \quad} F_i = \bigcup \{E(K(v)) \mid v\in V(G_i)\} % \end{equation} % We observe that $F_i$ is a flat of the matroid $M(G_{i+1})$. Recall % that {\em flats} are the closed sets (``subspaces'') of a matroid, % here meaning % that no cycle has all but one element in $F_i$. Because the graph % $G_{20}$ has cogirth nine only and a large number of cocircuits % (about $2^{10^{20}}$), a na\"{\i}ve application of % Lemma~\ref{lem:randbound} would result in a very poor bound on % $\phio(M(G_{20}))$. %%We can classify the edges of $G_{20}$ according to when they first %%appear in the sequence $G_1, G_2, \ldots G_{20}$. % However, we observe that any cocircuit in $G_{20}$ which is small, % say it has less than 17 edges, either has at least half of its edges % in $E(K(v))$ for some $v \in G_{19}$ or is disjoint from $F_{19}$. % \comment{Petr: This formulation now sounds much better\dots} %% can only contain edges which appear early in %%this sequence. %% the sequence $E(G_1)$, $E(G_2)$, \ldots, $E(G_{20})$. %% Thus there are relatively few small cocircuits in $G_{20}$. % With this observation, one can derive a much better %%analysis of the imbalances observed among cocircuits in a % bound on the imbalance of a random orientation of $M(G_{20})$, by % considering the set $F_{19}$ and the minor $G_{20}/F_{19}$ independently. % To apply this type % of argument to an arbitrary oriented matroid $\Oscr$, we must first % define a suitable set of elements in~$\Oscr$ which can play the role % of $F_i$ in equation~(\ref{eq:K10}). % %\smallskip %%%%%%%%%%%%%% Let $\Oscr$ be an oriented matroid with %ground set $E$. $E=E(\Oscr)$. A flat $F$ is \DEF{dense in~$\Oscr$} if $$ \frac{|F|}{|E|} \ge \frac{\rk(F)+1}{\rk(E)+1}. $$ A dense flat $F$ is \DEF{minimal} if no proper subflat of $F$ is dense in $\Oscr$. Since $E$ is dense and $\emptyset$ is not dense, $\Oscr$ has a minimal dense flat and all minimal dense flats are nonempty. % A cocircuit $B$ is \DEF{$F$-intersecting} if $B\cap F \ne \emptyset$. Let $\Bscr_F$ denote the set of $F$-intersecting cocircuits in $\Oscr$. We first show that a substantial portion of any $F$-intersecting cocircuit lies within $F$. \begin{lemma} \label{lem_dense} Let $F$ be a minimal dense flat in $\Oscr$, and let $B \in \Bscr_F$. Then $$ |B\cap F| > \frac{|E|}{\rk(E)+1}. $$ \end{lemma} % \begin{proof} Suppose not. Since the complement $(E-B)$ of the cocircuit $B$ is a matroid hyperplane and the intersection of two flats is a flat again, %LUIS: no need for this ref any more % (see~\cite[1.4 and 2.1.6]{oxley}), $B \cap F \ne \emptyset$ implies that $F' := F \cap ( E - B)$ is a proper subflat of $F$ in $\Oscr$ satisfying $$ \frac{|F'|}{|E|} = \frac{|F|}{|E|} - \frac{|B\cap F|}{|E|} \ge \frac{\rk( F)+1}{\rk(E)+1} - \frac{1}{\rk(E)+1} \ge \frac{\rk(F')+1}{\rk(E)+1}. $$ This contradicts that $F$ is minimally dense in~$\Oscr$. \end{proof} \medskip \begin{lemma} \label{lemma_main} %Let $R \subseteq E(\Oscr)$ and let $F \subseteq R$ be a minimal %dense flat in an oriented matroid $\Oscr$ of size $n$. Let $\Oscr$ be an oriented matroid of rank $r\ge 3$ and size $n$. Let $R \subseteq E(\Oscr)$ and $F \subseteq R$ be a minimal dense flat in $\Oscr$. Suppose that $t\in \RR$ satisfies $19 r^2 \ln r \le t \le n$. Then the probability that some $F$-intersecting cocircuit is $t$-unbalanced in a random resigning of $R$ is less than~$n^{-2}$. If ``$3$'' is replaced by $4$ or $5$, then ``$19$'' may be replaced by $14$ or $12$ respectively. \end{lemma} \begin{proof} %Let $\Bscr_F$ be the set of $F$-intersecting cocircuits in $\Oscr$, and Let $B\in \Bscr_F$. In any reorientation of $\Oscr$, if $B^+\ne \emptyset$, we have by Lemma \ref{lem_dense}, $$ \frac{|B|}{|B^+|} \le \frac{n}{|B^+|} \le \varrho\:\frac{|B \cap F|}{|B^+ \cap F|} $$ where $\varrho=r+1$. %LUIS reworded slightly The same inequality holds if we replace $B^+$ by $B^-$. Thus, in a random resigning of $R$, the probability that $B$ is $t$-unbalanced is at most the probability that $B \cap F$ is $\frac{t}{\varrho}$-unbalanced in $B$. By Lemmas~\ref{lem-cher-app} and~\ref{lem_dense} this probability is at most $$ 2 \exp \left( -\left(1-\frac{2\varrho}{t}\right)^2 \frac{|B \cap F|}{2}\right) \le 2 \exp \left( -\left(1-\frac{2\varrho}{t}\right)^2 \frac{n}{2\varrho}\right) =: P. $$ We aim to show \begin{equation} \label{eq_aim} n^2 |\Bscr_F| P <1. \end{equation} %Since any independent set of corank 1 determines a hyperplane, We estimate $ |\Bscr_F| \le {{n} \choose {r-1}} \le \frac{n^{\varrho-2}}{2}$ (for $r \ge 3$). Thus (\ref{eq_aim}) holds provided that $n^{\varrho}\cdot\frac P2<1$. Equivalently, we aim to show %, or equivalently $$ \varrho\ln n -\left(1-\frac{2\varrho}{t}\right)^2 \frac{n}{2\varrho}< 0 \,,$$ \begin{equation} \label{eq_aim2} 2 \frac{\ln n}{n} < \left( \frac1\varrho - \frac2t \right)^2. \end{equation} \comment{Petr: I think that the paper is now long, so we should add intermediate steps here\dots I have also replaced $\varrho$ by $\varrho$, which is easier to read.} For any integer $r_0 \ge 3$, let $f(r_0)$ be the smallest positive number such that every integer $r \ge r_0$ satisfies $$ %f(r_0) r^2 \ln r \le e^{\frac{-2}{(r_0+1)}} \, %f(r_0)\: r^2 \ln r \le e^{-\frac{1}{2}} \, % r^{\frac{f(r_0)\:r_0^2}{2(r_0+1)^2}}. f(r_0)\: r^2 \ln r \le e^{-1/2} \, r^{f(r_0)\:r_0^2/(2(r_0+1)^2)}. $$ % % It is straight forward to verify that for $r \ge 3$, % $$ % t_0 \le e^{-1/2} \, r^{9\cdot 19/32} % % e^{-2/(r+1)}. % $$ % It is straight forward to verify that $f(3) \le 19$, $f(4) \le 14$, $f(5) \le 12$, and that $f(r)\rightarrow 4$ slowly. Writing $t_0 = f(r_0)\: r^2 \ln r$, and $\varrho = r+1$, we have for $r \ge r_0 \ge 3$, $$ % 2/\varrho + \ln t_0 \le 1/2+\ln t_0 % \le \frac{9\cdot 19}{32}\ln r % \le \frac{19r^2}{2(r+1)^2}\ln r % = t_0/2\varrho. \ln t_0 \le \frac{f(r_0)\:r_0^2}{2(r_0+1)^2}\ln r - \frac12 \le \frac{f(r_0)\:r ^2}{2(r +1)^2}\ln r - \frac2{\varrho} = \frac{t_0}{2\varrho^2} - \frac2{\varrho} . $$ Together with $t_0 \le t \le n$, this completes the proof since the left hand side of (\ref{eq_aim2}) is at most $2 \frac{\ln t_0}{t_0}$, whereas the right hand side is at least $ \frac1{\varrho^2} - \frac4{\varrho \: t_0}$. \end{proof} %(In the application of this lemma, % most cocircuits of $\Oscr$ are $F$-intersecting.) \section{Proof of Main Theorem} Let $\Oscr$ be an oriented matroid. To prove the bound on $\phio(\Oscr)$, we shall construct an ordered partition $(F_0, F_1, \ldots , F_p)$ of $E(\Oscr)$ as follows. Let $F_0$ be a minimal dense flat in $\Oscr_0 = \Oscr $ and suppose we have constructed $F_0, F_1, \ldots , F_{k}$, for some $k \ge 0$. If $\bigcup_{i=0}^{k} F_i = E(\Oscr)$, then we set $p=k$ and output the list. % Otherwise let $F_{k+1}$ be a minimal dense flat in %LUIS This stuff is in section 2.3 now %the {\em contracted oriented matroid} (minor) the contracted oriented matroid (minor) %$\Oscr_k$ where $\Oscr_k$ is the nonempty contracted matroid $$ \Oscr_{k+1} := \Oscr \left/ \left(\bigcup_{i=0}^{k} F_i\right) = \Oscr_{k} / F_{k} \right. . $$ (See Section~\ref{sect:geom} for the geometric interpretation of contracting a flat.) %Geometrically speaking, the intersection of the pseudospheres in %$F_k$ yields a subsphere $S_{k+1}$ of $S_k$, the sphere of $\Oscr_k$. %As $F_k$ is a flat, no pseudosphere $S_e$ with $e \in E_{k+1}:=E \setminus %F_k$ can contain $S_{k+1}$. Thus, for each $e \in E_{k+1}$ $S_e \cap %S_{k+1}$ is a pseudohypersphere of $S_{k+1}$. This way we get an %arrangement for $\Oscr_k/F_k$. Since each $F_k$ is nonempty and $\Oscr$ is finite, this procedure must terminate. Any sequence $(F_0, F_1, \ldots , F_p)$ constructed in this way is called a \DEF{dense flat sequence} of $\Oscr$. Let $(F_0, F_1, \ldots , F_p)$ be a dense flat sequence for $\Oscr$. A cocircuit $B$ of $\Oscr$ is \DEF{of type $k$} if $k$ is the least index for which $B \cap F_k \ne \emptyset$. Thus the cocircuits in $\Oscr_k$ are precisely the cocircuits of type $\ge k$ in $\Oscr$. % %For $0 \le k \le p$, we Let $\Bscr_k$ be the set of cocircuits of type $k$ in $\Oscr$, let $n_k = |\Oscr_k|$ and let $r_k = r(\Oscr_k) = r(\Oscr)-\sum_{i=0}^{k-1} r(F_i)$. Figure~\ref{fig:1} may help the reader with these definitions and the proof that follows. \begin{figure}[htb] % \epsfxsize=6.5truecm % \epsfxsize=8.0truecm % \centeredgraphics{fig1.eps} \begin{center} \includegraphics[width=6.5cm]{fig1.eps} \end{center} \caption{A dense flat sequence and a cocircuit $B$ of type $2$} \label{fig:1} \end{figure} %%%%%%%%%%%%%%%%%%55 %\newpage %%%%%%%%%%%%%%%%%%55 \begin{theorem} For any oriented matroid $\Oscr$ of rank $r$ and without coloops, $$\phio(\Oscr) < 14 r^2 \ln r .$$ %where $r = \rk(\Oscr)$. \end{theorem} % \begin{proof} We show that $\Oscr$ has a reorientation in which no cocircuit is $t_0$-unbalanced, where $t_0=14 r^2 \ln r$. Let $(F_0, F_1, \ldots , F_p)$ be a dense flat sequence for $\Oscr$, with $\Oscr_k$, $\Bscr_k$, $n_k$, $r_k$ as defined as above. Let $q$ be the least integer for which either $r_q \le 3$ or $n_q \le t_0$. If $r_q \le 3$, then by Lemma~\ref{lem:rank3},~$\Oscr_q$ may be reoriented so that every cocircuit in~$\Oscr_q$ has imbalance at most~$17$. If $n_q \le t_0$, then in any totally cyclic orientation of~$\Oscr_q$, we have that every cocircuit has imbalance at most $t_0-2$. In any case we find a reorientation~$\Oscr'$ of~$\Oscr$ in which no cocircuit of type at least $q$ is $\max\{17, t_0-2\}$-unbalanced. We now randomly resign the all elements ``outside of $\Oscr_q$'', namely $R_0:=\cup_{i=0}^{q-1} F_i$, in $\Oscr'$ to obtain $\Oscr''$. We aim to show that with probability greater than zero, no cocircuit is $t_0$-unbalanced in $\Oscr''$. % %No cocircuit $B$ of type greater than $q$ is $t_0$-unbalanced %in $\Oscr'$ since %$$\frac{|B|}{|B-|},\frac{|B|}{|B^-|}\le \frac{t_0}{1}.$$ % By choice of $q$ we have $r_k \ge 4$ and $n_k > t_0$, for $0 \le k \le q-1$. So applying Lemma \ref{lemma_main} to $\Oscr_k$ and $F_k$ with $R = R_k:=\cup_{i=k}^{q-1} F_i$, we find that the probability that a cocircuit in $\Bscr_k$ is $t_0$-unbalanced in $\Oscr_k$ is at most $n_k^{-2}$. Note, that the random resigning of $R_0$ induces a random resigning of $R_k$. By definition each cocircuit from $\Bscr_k$ is contained in $E(\Oscr_k)$. % Therefore, the probability that some cocircuit in $\Bscr_k$ % is unbalanced in $\Oscr''$ also is the same. % Since $\big(\Bscr_0, \Bscr_1,\ldots, \Bscr_{q-1}, \Bscr(\Oscr_q)\big)$ is a partition of the cocircuits of $\Oscr''$, the probability that some cocircuit in $\Oscr''$ % Altogether, the probability that some cocircuit in $\Oscr''$ is $\max\{t_0,17\}$-unbalanced is at most $$ \sum_{k=0}^{q-1} n_k^{-2} \le \sum_{i=t_0+1}^{\infty} i^{-2} <1. $$ Thus $\phio(\Oscr) \le \max\{t_0,17\} = t_0$. \end{proof} \section{Small Examples} \label{sec:examples} Using an implementation by Lukas Finschi~\cite{F} of a simple reclass generator described in~\cite{FF}, together with a program of Timothy Mott~\cite{TM}, for calculating $\chio(\Oscr)$, we have found the following results. For various values of $n$ and $s$ we list in Table~\ref{tab:rank3} the number of coloop-free cosimple reclasses~$[\Oscr]$ of rank $3$ and size $n$ for which $\phio([\Oscr])=s$. In parentheses, we record the number of these which are reclasses of the uniform matroid $U_{n,3}$. If $\Oscr$ is not cosimple, we may contract any coparallel element to obtain a rank~$2$ oriented matroid with the same oriented flow number, which equals $\ocb(\Oscr)$ by Lemma~\ref{lem:rank2}. \comment{Luis: I can push this table to $n=9$ (500000 diagrams) with a little effort.} \comment{Petr: If this is really easy, I would welcome $n=9$ in the table, just to see ``large'' numbers which make our results look more important.} \begin{table} \begin{tabular}{c|rrrr} $s\backslash n$ & 5~~~ & 6~~~ & 7~~~~ & 8~~~~ \\ \hline 2 & 0 (0) & 1 (1) & 1 ( \,0) & 18 ( \ \ 3) \\ 5/2 & 0 (0) & 0 (0) & 137 (11) & 631 ( \ \ 0) \\ 3 & 1 (1) & 7 (0) & 57 ( \,0) & 5369 (132) \\ 4 & 0 (0) & 9 (3) & 11 ( \,0) & 11 ( \ \ 0) \\ \hline Total & 1 (1) & 17 (4) & 206 (11) & 6029 (135) \end{tabular} \caption{Number of cosimple reclasses with rank $3$, size $n$ and oriented flow number~$s$. In parentheses are listed the number of these which are uniform.} \label{tab:rank3} \end{table} \comment{Luis: Delete the following if you like.} For rank $4$, we find that, there are $143$ reclasses $[\Oscr]$ of size $7$. The number of these which have $\phio([\Oscr])=s$ is tabulated as follows, with parentheses indicating the number of which are uniform. $$ s=2: 1 (1) \qquad s=3: 12 (0) \qquad s=4: 130 (10). $$ %\comment{Luis: Winfried, I think you have more examples? %eg. a complete graph is not the worst for its rank.} % The lower bound given by the Betti number of complete graphs is not % the worst case. The following matrix due to Oliver Klein~\cite{oklein} % represents an oriented matroid $\Oscr_O$ of rank 5 and $\phio(\Oscr_O)=6$. % %$$\small\bordermatrix{~\cr % $$\matrix{ % &5&5&5&5&5&5&5&5&5&5&5&5&5&5&5&5\cr % & 0 &-1& 0& 0& 0& 0& 1& 1& 0& 1& 0& 1& 1&-1& 1&-2\cr % & 0& 1& -1& 0& 0& 0& 1& 1& 1&-1& 1& 0& 0& 0& 0&-1\cr % & 0& 1& 0&5& 6& 1&-1& 1& 0& 1& 1& 1& 1& 1& 0& 0\cr % & 1& 1& 0& 0& 0& 2& 0& 1& 0& 8& 0& 2& 1& 1&-1& 1} % $$ % However, wee do not know of any family of oriented matroids which shows that % $\phio(\Oscr) > \Theta(\sqrt{\rk(\Oscr)})$. A natural question is whether the lower bound given by the Betti number of complete graphs is the worst case or not. We consider this question rather hard, and so we make no conjectures here. However, we do not know of any construction of oriented matroids which would show that $\phio(\Oscr) > \Theta(\sqrt{\rk(\Oscr)})$. \comment{Luis: Should we make a possible conjecture that $\phio(\Oscr) = O\left(\sqrt{\rk(\Oscr)}\right)$ for $\Oscr$ coloop free? I am not so confident about this.} \comment{Winfried: I do not think so. If at all I would prefer $O\left(\rk(\Oscr)\right)$} \comment{Petr: I would also be careful as Winfried\dots} \subsection*{Acknowledgment} We thank the Pacific Institute of Mathematics for supporting the ``Thematic Programme on Flows, Cycles and Orientations'', Burnaby, 2000, where much of this work was done. We also thank Lukas Finschi for making available for us a program for generating all signed circuits of all simple reclasses, and Timothy Mott for his program for calculating $\chio(\Oscr)$. \begin{thebibliography}{99} % \bibitem{AS} N.~Alon and J.H.~Spencer, ``The Probabilistic Method,'' 2nd ed., John Wiley and Sons, New York, 2000. \bibitem{BLSWZ} A.~Bj\"orner, M.~Las Vergnas, B.~Sturmfels, N.~White and G.~Ziegler, ``Oriented Matroids,'' Encyclopedia of Mathematics and its Applications, 46, Cambridge University Press, Cambridge, 1993. \bibitem{BLV} R.~G.~Bland, M.~Las Vergnas, Orientability of matroids, J. Combin. Theory Ser. B, 24 (1978), 94--123. \bibitem{D} G.~A.~Dirac, The number of edges in critical graphs. Collection of articles dedicated to Helmut Hasse on his seventy-fifth birthday, II. J. Reine Angew. Math. 268/269 (1974), 150--164. \bibitem{F} L.~Finschi, Catalog of oriented matroids, \texttt{http://www.om.math.ethz.ch/?p=catom}\ %%. \bibitem{FF} L.~Finschi, K.~Fukuda, Generation of oriented matroids -- A graph theoretical approach, Discrete Comput. Geom.~27 (2002), 117--136. \bibitem{FoLa} J.~Folkman and J.~Lawrence, Oriented Matroids, J.~Combin. Theory Ser. B, 25 (1978), 199--236. \bibitem{GTZ} L.A.~Goddyn, M.~Tarsi, C.-Q.~Zhang, On $(k,d)$-colorings and fractional nowhere zero flows, J.~Graph Theory, 28 (1998), 155--161. \bibitem{Hof} A.~J.~Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, ``Combinatorial Analysis: Proc. Sympos. Appl. Math., Vol.10,'' R.~Bellman and M.~Hall Jr.~Eds, American Mathematical Society (1960), pp.~113--128. \bibitem{oxley} J.G.~Oxley ``Matroid Theory'' 2nd ed., Oxford University Press, Oxford, 1992. % \bibitem{oklein} O.~Klein, % ``Enummeration nicht notwendig uniformer % orientierter Matroide und untere Schranken f\"ur die zirkul\"are % Flusszahl,'' % Diploma Thesis, Universit\"at zu K\"oln, 2002. %\bibitem{Vin} A.~Vince, %Star chromatic number, %J.~Graph Theory, 12 (1988) 551--559. %\bibitem{White} N.~White (ed.), %``Theory of Matroids,'' %Cambridge University Press, Cambridge, 1986. \bibitem{Minty} G.~J.~Minty, A theorem on $n$-coloring the points of a linear graph, Amer. Math. Monthly 69 (1962) 623--624. \bibitem{Mandel} A.~Mandel, ``Topology of Oriented Matroids,'' Ph.D.~Thesis, University of Waterloo, 1982. \bibitem{TM} T.~Mott, NSERC Summer Student Project, Simon Fraser University, June 2002. \bibitem{Sey6} P.~D.~Seymour, Nowhere-zero $6$-flows, J. Combin. Theory Ser. B 30 (1981), 130--135. \bibitem{SeySurv} P.~D.~Seymour, Nowhere-zero flows. Appendix: Colouring, stable sets and perfect graphs. Handbook of combinatorics, Vol. 1, 2, 289--299, Elsevier, Amsterdam, 1995. \bibitem{Tu54} W.~T.~Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80--91. \bibitem{Zhu} X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371--410. \bibitem{Zhu2} X. Zhu, Construction of graphs with given circular flow number, preprint. \end{thebibliography} \end{article} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% ------Previous version:----- \documentclass[11pt,a4paper]{article} \usepackage{epsf,latexsym,amsfonts,epic,eepic} \sloppy \def\Bscr{{\cal B}} \def\Fscr{{\cal F}} \def\Oscr{{\cal O}} \def\Rscr{{\cal R}} \def\Yscr{{\cal Y}} \def\Pscr{{\cal P}} \def\Cscr{{\cal C}} \def\Lscr{{\cal L}} \def\Qscr{{\cal Q}} \def\Gscr{{\cal G}} \def\Hscr{{\cal H}} % some set symbols \def\R{\mathbb{R}} \def\N{\mathbb{N}} \def\prob{\mathop{\rm Prob}} \newtheorem{definition}{Definition}[section] \newtheorem{theorem}[definition]{Theorem} \newtheorem{proposition}[definition]{Proposition} \newtheorem{corollary}[definition]{Corollary} \newtheorem{lemma}[definition]{Lemma} \newtheorem{example}[definition]{Example} \def\proof{\par\medbreak\noindent{\bf Proof.}\enspace} \def\endproof{ {~~} \hfill $\Box$ \par\addvspace{\bigskipamount}} \def\noproof{\par\vspace*{-\bigskipamount}\endproof} \def\whcomment{$\bullet\bullet\bullet\bullet\bullet\bullet\bullet$} \title{The Fractional Flow Number of an Orientable Matroid% %x \footnote{I would like to have the word ``matroid'' in the title. PH. Peter should get his matroid. My title had hyperplane arrangements. WH} } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \author{L.~Goddyn% % , P.~Hlin\v{e}n\'y% \footnote{\tt hlineny@member.ams.org}% , W.~Hochst\"attler% % } %\keywords{Nowhere-Zero Flows, Oriented % Matroids, Sphere Systems, Topology, Matroids, Geometry} %\classification{AMS 1991}{05B35, 06B30, 51D20, 52B30, 52B40, 57N50} \begin{document} \maketitle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{abstract} The fractional flow number ............ The first two sections were written (so far) by WH, the next two by PH, and the last section should be decided. Luis should review the introduction. The ``*******''-marked notes are by PH. The ``\whcomment''-marked notes are by WH. \end{abstract} \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The circular chromatic number $\chi^\ast(G)$ of a graph, introduced by Vince~\cite{Vin} as star chromatic number, is a non-negative rational number satisfying $\lceil \chi^\ast(G)\rceil=\chi(G)$ where $\chi(G)$ is the chromatic number. Goddyn, Tarsi and Zhang~\cite{GTZ} introduced the matroid dual $\phi^\ast(G)$ of this parameter, which we call the fractional flow number, and generalized its definition to regular matroids. They observed that, as a consequence of Hoffman's Lemma~\cite{Hof} about the existence of an integer circulation with upper and lower bounds, in a regular matroid we always have \begin{equation}\label{cflownum} \phi^\ast(G)=\min_{\vec{G}}\,\max_{B\in\Bscr}\, \frac{|B|}{\min\{|B^+|,|B^-|\}} \end{equation} where the first minimum is taken over all orientations of $G$, the maximum varies over all cocircuits (bonds) $B$ of $G$, and $B^+$, $B^-$ are the forward and backward, respectively, arcs of $B$. Regarding equation (\ref{cflownum}) as a definition they, furthermore, pointed out that the notion of the fractional flow number can be extended to orientable matroids; and they asked whether in general this parameter is bounded by a function of the rank of the matroid. (On the other hand, the fractional flow number is clearly bounded by the corank plus one.) Here, we answer this question to the affirmative: \begin{theorem} \label{thmain} There exists a function $f$ such that the fractional flow number of a coloop-free oriented matroid of rank $k\geq3$ is at most~$f(k)$. In particular, $f(3)\leq37$ and $f(k)\leq 8(r+1)^2\ln2(r+1)$ for $k>3$. \end{theorem} The paper is organized as follows. In Section~\ref{basics} we introduce the required background on oriented matroids. As a first non-trivial result we present a bound on the fractional flow number of pseudoline arrangements (i.e.~rank-$3$ oriented matroids) in Section~\ref{lines}, and generalize this result to higher dimensions (higher ranks of matroids) in Section~\ref{arrangements}. Finally, in Section~\ref{small} we try to analyze ``small cases'' of the previous proofs in order to get some precise results. Our notation should be fairly standard, in the spirit of~\cite{orientedmatroids}. \section{Basics and Definitions}\label{basics} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% While general matroids are frequently considered as set systems, an oriented matroid always ``is'' a topological object, it is realizable as a signed arrangement of pseudo spheres. %\begin{defin} \label{hyper} For $d\in \mathbb{Z}, d \ge -1$ let $S^d := \{x \in \R^{d+1} |\mid \| x \| = 1\}$ denote the $d$-dimensional standard sphere. If $f:S^d \to S^d$ is a homeomorphism then $f(S^{d-1}\times\{0\})$ is called a {\em pseudohypersphere of $S^d$}. If $H_e$ is a pseudo hypersphere of $S^d$, chosing one of the two components of $S^d \setminus H_e$ to be the {\em positive side} $H_e^+$ yields a {\em signed pseudo hypersphere $\vec{H_e}$}. We abbreviate $H_e^-:=S^d \setminus (H_e \cup H_e^+)$. Let $E$ be a finite set and $\vec\Hscr = (\vec{H_e})_{e\in E}$ be a family of signed pseudo hyperspheres of $S^d$ indexed by $E$. If $A \subseteq E$, we call $\bigcap_{f \in A} H_f$ the {\em flat} of $A$. Then $\vec\Hscr$ is called a {\em signed arrangement of pseudo spheres} if \begin{itemize} \item[(S1)] All flats are topological spheres, i.e.\ homeomorphic to $S^{\tilde d}$ for some $\tilde d$. \item[(S2)] If $F$ is a flat and $\vec{H_e}$ a signed pseudo hypersphere, where $F \not \subseteq \vec{H_e}$, then $H_e \cap F$ is a (topological) hypersphere of $F$ separating $F\setminus (H_e \cap F)$ into two connected components $F_1,F_2$ such that $F_1 \subseteq H_e^+$ and $F_2 \subseteq H_e^-$. {\footnotesize \item[*******] remarks: What about empty flats? $e\in E$ should be defined. What is $F^+,F^-$? It should be clearly stated whether such signing is given in advance or whether it follows from the situation. \item[\whcomment] remarks: The empty set is the sphere $S^{-1}$. This is now explicitely defined. $>$What is $F^+,F^-$? \\ By Jordan-Brouwer separation theorem (see a textbook on topology, e.g.\ Hocking and Young) any hypersphere $H$ of a sphere $S$ separates $S \setminus H$ into two connected components. Axiom S2 requires that these are on different sides of $H_e$. The signing $F+,F-$ makes sense only in the relative situation. If there is an element antiparallel element to $e$ then the relative roles of $F^+$ and $F^-$ are interchanged. Therefore I changed the names. I hope this makes it clearer. \item[*******] Now it sounds better\dots } \end{itemize} %\end{defin} There is an obvious map $X:S^d \to 2^{\pm E}:=\{0,+,-\}^E$ from the points of $S^d$ to the set of {\em signed vectors} on $E$, namely if $x \in S^d$ we define \[X(x):=\left\{ \begin{array}[h]{ll} + & \mbox{if }x \in H_e^+,\\ 0 & \mbox{if }x \in H_e,\\ - & \mbox{if }x \in H_e^-. \end{array}\right. \] These signed vectors derived from a signed arrangement $\vec\Hscr$, which we denote by $\Oscr(\vec\Hscr)$, form the set of covectors of an oriented matroid (see~\cite{orientedmatroids} 3.7.5). The inverse image of such a vector is called a {\em cell}. One of the earlist results on oriented matroids, due to Folkman and Lawrence~\cite{FoLa} and Edmonds and Mandel~\cite{Mandel}, is the topological representation theorem (see also~\cite{orientedmatroids} 5.2.1): \begin{theorem}[Folkman-Lawrence, Edmonds-Mandel] \label{thmodel} \mbox{Let $\Oscr\subseteq2^{\pm E}$.} Then $\Oscr$ is the set of covectors of a loop-free oriented matroid of rank $d+1$ if and only if $\Oscr=\Oscr(\vec\Hscr)$ is the set of signed vectors derived from some signed arrangement of pseudo spheres $\vec\Hscr=(\vec{H_e})_{e\in E}$ on $S^d$ such that $\bigcap_{e \in E}H_e=\emptyset$. \end{theorem} Note, that the supports of the signed vectors form the set of the incidence vectors of {\em open sets}, i.e.\ the complements of closed sets, of a matroid (see~\cite{white}). In particular, if $\vec\Hscr$ is {\em essential}, i.e.\ $\bigcap_{e \in E}H_e=\emptyset$, the support of a vector of a minimal non-empty cell is the complement of a hyperplane of the underlying matroid, i.e.\ it is a {\em cocircuit}. Accordingly we call the signed vectors of minimal cells cocircuit vectors. Clearly, the topology of a signed arrangement does not change if we interchange $H_e^+$ and $H_e^-$ on all $e$ in a subset $A \subseteq E$. In the oriented matroid this yields a {\em reorientation}, where the non-zero signs in the $A$-coordinates are inverted for all vectors. Thus, forgetting about the signature of the hyperspheres we get an {\em arrangement of pseudo spheres} as a topological model of a reorientation class of oriented matroids. \begin{figure}[htb] {\hfill\scriptsize {% Picture saved by xtexcad 2.4 \unitlength=0.660000pt \begin{picture}(524.00,119.00)(0.00,0.00) \put(200.00,108.00){\makebox(0.00,0.00){6}} \put(263.00,88.00){\makebox(0.00,0.00){3}} \put(173.00,67.00){\makebox(0.00,0.00){5}} \put(135.00,48.00){\makebox(0.00,0.00){2}} \put(88.00,108.00){\makebox(0.00,0.00){4}} \put(25.00,85.00){\makebox(0.00,0.00){1}} \put(474.00,63.00){\makebox(0.00,0.00){6}} \put(445.00,25.00){\makebox(0.00,0.00){5}} \put(484.00,25.00){\makebox(0.00,0.00){4}} \put(464.00,0.00){\makebox(0.00,0.00){3}} \put(502.00,64.00){\makebox(0.00,0.00){2}} \put(427.00,65.00){\makebox(0.00,0.00){1}} \put(465.00,48.00){\circle*{8.00}} \put(465.00,104.00){\circle*{8.00}} \put(520.00,12.00){\circle*{8.00}} \put(404.00,12.00){\circle*{8.00}} \put(465.00,49.00){\line(0,1){55.00}} \put(522.00,11.00){\line(-3,2){57.00}} \put(403.00,12.00){\line(5,3){60.00}} \put(521.00,12.00){\line(-1,0){118.00}} \put(465.00,106.00){\line(3,-5){56.00}} \put(402.00,11.00){\line(2,3){63.00}} \put(9.00,112.00){\circle*{8.00}} \put(279.00,111.00){\circle*{8.00}} \put(137.00,16.00){\circle*{8.00}} \put(227.00,75.00){\circle*{8.00}} \put(59.00,74.00){\circle*{8.00}} \put(146.00,75.00){\circle*{8.00}} \put(148.00,89.00){\circle*{8.00}} \put(42.00,75.00){\line(1,0){206.00}} \put(150.00,100.00){\line(-5,-31){15.00}} \put(2.00,117.00){\line(4,-3){144.00}} \put(291.00,119.00){\line(-3,-2){161.00}} \put(292.00,113.00){\line(-6,-1){251.00}} \put(0.00,113.00){\line(6,-1){246.00}} \end{picture}} \hfill} \caption{A pseudoline model of the orientable (self-dual) matroid $M(K_4)$.} \label{fig_mk4} \end{figure} \begin{example}[see \cite{orientedmatroids} Chapter 6]\label{exlines} \rm If $d=2$, taking a projective point of view, the arrangements of pseudo spheres are equivalent to arrangements of pseudolines. A finite collection $\Pscr=(P_e)_{e \in E}$ of simple closed curves in the projective plane is a {\em pseudoline arrangement} if any pair of these curves intersects in exactly one point where they (properly) cross. See also Figure~\ref{fig_mk4}. \end{example} Later we will refer to the fact that, if an oriented matroid does not have a coloop, it always has a {\em totally cyclic} reorientation, i.e.\ an orientation where any cocircuit vector has at least a $+$ and a $-$. This is not immediate from our geometric approach, but quite easy using duality. We will not formally introduce the dual of an oriented matroid here, references are in the sketch of the proof of the following lemma. \begin{lemma}[see \cite{orientedmatroids} 3.4.8]\label{totally_cyclic} Let $\Oscr$ be an oriented matroid. Then $\Oscr$ has a totally cyclic reorientation if and only if $\Oscr$ does not have a coloop. \end{lemma} \proof If $\Oscr$ has a coloop, then in any orientation the corresponding cocircuit vector has a single non-zero entry. Thus $M$ cannot have a totally cyclic orientation. Thus assume $\Oscr$ does not have a coloop. Let $\Oscr^\ast$ denote the dual $\Oscr$ (see \cite{orientedmatroids} 3.4.1). By assumption $\Oscr^\ast$ does not have a loop. Therefore, $\tilde \Oscr^\ast$ has a covector $X$ with full support (this follows from \cite{orientedmatroids} 3.2.2 (3) and the covector axiom 3.7.5 (V2)). Let $A$ denote the negative entries in $X$. Interchanging the signs on all elements of $A$ we derive a reorientation $_{\overline{A}}(\Oscr^\ast)$ that has an all positive covector. Thus by (see \cite{orientedmatroids} 3.4.8) its dual $_{\overline{A}}\Oscr$ is totally cyclic (dualization and reorientation commute see \cite{orientedmatroids} Exercise 3.14). \endproof \begin{description}{\small \item[\whcomment] I am not happy with this. But otherwise we have to introduce a lot more from oriented matroid theory and the any referee will ask us to delete it and give references only. The above trivial fact is nowhere stated explicitely. The intuition is best understood in graphs. We want an orientation without a positive cut. We may assume that the graph is two connected. Choose an ear decomposition and orient any ear in the same direction. This is a totally cyclic orientation. Any suggestions for a better presentation? \item[*********] Really difficult to read. But that may be enough for now\dots }\end{description} While a regular matroid has one unique reorientation class (\cite{orientedmatroids} 7.9.4), and thus a unique topological model, the situation is completely different in general. For example, the uniform matroids, which always can be realized as a hyperplane arrangement in general position, also give rise to non-realizable oriented matroids (see~\cite{orientedmatroids} 8.3). Therefore, when defining the fractional flow number of an oriented matroid we proceed in two steps. \begin{definition} \rm Let $M$ be a matroid on a finite set $E$, and $\Hscr=(H_e)_{e \in E}$ be an (unsigned) arrangement of pseudospheres with underlying matroid $M$ such that $M$ does not have a coloop. Let $\Cscr$ denote the set of signed cocircuits (*********** signed cocircuit vectors?), and let set $C^+:=\{e\in E\mid C(e)=+\}$, $C^-:=\{e\in E\mid C(e)=-\}$, where $C\in \Cscr$. Then we define the {\em fractional flow number $\phi^\ast$ of $\Hscr$} to be \begin{equation} \phi^\ast(\Hscr)=\min_{\vec{\Hscr}}\,\max_{C\in\Cscr}\, \frac{|C^+|+|C^-|}{\min\{|C^+|,|C^-|\}}\,, \label{hflownum} \end{equation} where the minimum is taken over all signatures $\vec\Hscr$ of $\Hscr$, and the {\em fractional flow number $\phi^\ast$ of $M$} to be \begin{equation} \label{mflownum} \phi^\ast(M)=\min_{\Hscr \mbox{ \footnotesize is an arrangement with } \atop \mbox{\footnotesize underlying matroid }M }\phi^\ast(\Hscr)\,. \end{equation} (Note that, by Lemma~\ref{totally_cyclic}, both fractional flow numbers above are finite.) \end{definition} Recall that, if the oriented matroid is essential, then a cocircuit corresponds to a single point $x$ on the sphere. The support (non-zero entries) of its signed vector $C_x$ correspond to hyperspheres not containing it. Denote by $C^\bullet_x=C^+_x \dot\cup C^-_x$ the support of $C_x$, where $C^+_x$ are the positive and $C^-_x$ the negative entries. We say that a cocircuit is {\em $f$-balanced} if $|C^\bullet_x|\le f\min\{|C^+_x|,|C^-_x|\}$. Thus, the geometric meaning of an orientation realizing the fractional flow number, i.e.\ an orientation where the minimum is attained, is a signing of the hyperspheres where all cocircuits are as balanced as possible. \section{Pseudoline Arrangements}\label{lines} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% In this section we discuss the case of rank-$3$ matroids in the setting of pseudoline arrangements, as proposed by Example~\ref{exlines}. We do this case separately to illustrate our proof technique % in an obvious geometric way, on an easy-to-imagine topological model, however, there is no significant difference in handling higher-rank situations. We start with a classical probabilistic result (see e.g.\ \cite{AS}): \begin{theorem}[Chernoff bound] Let $X_i$, $i=1,\dots,m$ be indepen\-dent random variables obtaining values $+1$ and $-1$ with probability~$\frac12$ each. Then $\prob(|X_1+\dots+X_m|>\lambda\sqrt{m})<2e^{-\lambda^2/2}$. \end{theorem} \vbox{ \begin{corollary} \label{probb} Let $X_i$, $i=1,\dots,m$ be independent random variables as above. Then $\prob(|X_1+\dots+X_m|>\varepsilon m)<2e^{-\varepsilon^2m/2}$. \end{corollary} \noproof} The idea of our proof is not difficult -- we sign each element according to an independent ``coin flip'', and we show that with nonzero probability this gives us reasonably balanced cocircuits. % (i.e.~an upper bound on the fractional flow number). \begin{proposition} \label{lineb} Let $\Hscr = ({H_e})_{e\in E}$ be an (unsigned) essential pseudoline arrangement, and suppose that the underlying matroid of~$\Hscr$ is coloop-free. If $|E|\geq37$, then $\phi^\ast(\Hscr)\leq37$. \\ Moreover, if $|E|\geq184$ ($\,481\,$), then $\phi^\ast(\Hscr)\leq4$ ($\,\phi^\ast(\Hscr)\leq3$, respectively). \end{proposition} \begin{proof} % First recall Example~\ref{exlines}. According to the previous section, we have to show that there exists an orientation $\vec\Hscr$ such that any cocircuit is $f$-balanced for $f=37$. We determine $\vec\Hscr$ by signing each pseudoline $H_e$, $e\in E$ of our arrangement independently in random by choosing each of the two pseudo halfplanes of $H_e$ with probability~$\frac12$. Let~$n=|E|$. A crossing point (i.e.~a minimal nonempty flat or a cocircuit in matroid terms) of $\Hscr$ is called a {\em vertex}. A vertex is {\em dense} if it is the intersection of more than $\frac{n+1}2$ pseudolines of~$\Hscr$. % A crossing point $x$ of $\Hscr$ is {\em balanced in $\vec\Hscr$} if % $|C_x^+|+|C_x^-|f$. Let $k\in\{0,1,\dots,r\}$ be the largest value for which there exists a set $F_i\subseteq E_i$ such that $F_i$ is a (matroidal) flat in the restriction of $M$ to $E_i$, the rank $r(F_i)\leq r-k$, and $|F_i|\geq\frac{r+1-k}{r+1}\,n_i$. Notice that $k=0$ is always defined, and that actually $k|F_i|-\frac{1}{r+1}n_i\geq\frac{r+1-k-1}{r+1}\,n_i$, a contradiction to our choice of $k$ and~$F_i$. \end{proof} % It follows from the previous definition, for any $x\in V_i\setminus V_{i+1}$, % $0\leq i|F_i|-\frac{1}{r+1}n_i$, % a contradiction to our choice of $k$. % Another important property of the definition is that a vertex % $x\in V_i$, $0f$ then follows by examining the growth rate % of the exponential part. Reader may easily verify that if $s\geq 2t\ln t$ and $t\geq50$, then $\frac{s}{\ln s+1}\geq t$. Thus $\frac{f}{\ln f+1}\geq2(r+1)^2$ for our choice of~$f$. Using that we derive: $$ \left(\frac{f-2r}f\right)^2\cdot\frac{f}{2(r+1)}- (r+1)\ln f =\frac{f}{2(r+1)}- \frac{2r}{r+1}+ \frac{2r^2}{f(r+1)}- (r+1)\ln f $$ \begin{equation}\label{expr5} \geq\frac{f}{2(r+1)}- (r+1)(1+\ln f) \geq 0 \end{equation} Together with a simple inequality $2f(f+1)\cdot{f\choose r-1}\leq f^{r+1}$ for $r>3$, the inequality (\ref{expr5}) proves (\ref{expr4}) for all $n_i\geq f$. (Consider the growth rate of the exponential part for $n_i>f$.) \end{proof} Finally, we may finish the proof of Proposition~\ref{higherb}. Notice that $n_0>n_1>\dots>n_{p-1}>f$, so $\sum_{i=0}^{p-1}\frac1{n_i(n_i+1)}\leq\sum_{i=1}^{n_0}\frac1{i(i+1)}<1$. Thus by Lemma \ref{proball}, the proba\-bility that $\vec\Hscr$ has an $f$-unbalanced circuit is smaller than~$1$. In other words, there is a signing that witnesses $\phi^\ast(\Hscr)\leq f$. \end{proof} Theorem~\ref{thmodel} together with Corollary~\ref{linebc} and Proposition~\ref{higherb} prove Theorem~\ref{thmain}, since possible loops in the matroid have no influence on the fractional flow number (they belong to no cocircuit). Actually, we have proven a stronger statement: \begin{theorem} There exists a function $f$ such that the fractional flow number of an essential arrangement of pseudo spheres of rank $k$ is at most~$f(k)$. In particular, $f(3)\leq37$ and $f(k)\leq 8(r+1)^2\ln2(r+1)$ for $k>3$. \end{theorem} \section{Small Cases and Remarks}\label{small} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% **************** \medskip we try to show precise result (4) for rank 3 -- the probabilisic argument from \ref{lines} can be refined by summing combination numbers instead of using Chernoff, and maybe by choosing exactly half of each sign, but that has sense to do only if we can match it by some affordable small-case analysis, \medskip we show some lower bounds -- duals of complete graphs, additionally, we show that in general the flow number does not go down when $|E|$ is huge (as somebody may think from \ref{lineb}) -- we take a direct sum of a small matroid of rank $r-2$ with big flow number and $U_{2,*}$, or if we insist on connectivity, then we add freely one more element, \medskip maybe remarks about diskrepancy for the matroids representable over the reals........ \subsection*{Acknowledgement} Nice workshop, Luis\dots \begin{thebibliography}{} \bibitem{orientedmatroids} {\sc A.~Bj\"orner, M.~Las Vergnas, B.~Sturmfels, N.~White and G.~Ziegler}, \newblock{{ ``Oriented Matroids,''} Cambridge University Press, Cambridge, 1993.} \bibitem{FoLa} {\sc J.~Folkman and J.~Lawrence}, \newblock Oriented Matroids, \newblock {\sl Journal of Combinatorial Theory, Series B} {\bf 25} (1978), 199-236. \bibitem{GTZ} {\sc L.A.~Goddyn, M.~Tarsi, C.-Q.~Zhang}, \newblock On $(k,d)$-colorings and fractional nowhere zero flows {\sl J.~Graph Theory} {\bf 28} (1998), 155-161. \bibitem{Hof} {\sc A. J. Hoffman}, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, {\em Combinatorial Analysis: Proceedings of the Tenth Symposium in Applied Mathematics of the American Mathematical Society}, R. Bellman and M. Hall Jr.\ Eds., American Mathematical Society (1960) 113-128. \bibitem{Mandel} {\sc A.~Mandel}, \newblock ``Topology of Oriented Matroids,'' \newblock {Ph.D.~Thesis, University of Waterloo, 1982.} \bibitem{Vin} {\sc A. Vince}, Star chromatic number, {\em J. Graph Theory} {\bf 12} (1988) 551-559. \bibitem{white} {\sc N.~White (ed.)}, \newblock{ {``Theory of Matroids,''} Cambridge University Press, Cambridge, 1986.} \end{thebibliography} \end{document}