Balanced Signings and the Chromatic Number of Oriented Matroids

Luis Goddyn^{*}

Department of Mathematics Simon Fraser University Burnaby, BC, Canada

                  E-mail: goddyn@math.sfu.ca

and

Petr Hliněný

Department of Computer Science, FEI VŠB – Technical University of Ostrava,

17. listopadu 15, 708 33 Ostrava, Czech Republic and Institute of Theoretical Computer Science† Charles University, Prague, Czech Republic

                  E-mail: petr.hlineny@vsb.cz

and

Winfried Hochstättler

Department of Mathematics BTU Cottbus, Cottbus, Germany

               E-mail: hochst@math.tu-cottbus.de

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 totally cyclic reorientation, a reorientation in which every signed cocircuit B = {B^{+}, B^{−}} satisfies B^{+}, B^{−} ≠ ∅. We show that, for some reorientation, every signed cocircuit satisfies

1/f(r) ≤ |B^{+}|/|B^{−}| ≤ f(r),

where f(r) ≤ 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) 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.

Key Words: Oriented matroid, pseudosphere configuration, hyperplane arrangements, flow, circular chromatic number, discrepancy, cocircuit, wiring diagram

1. INTRODUCTION

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 [8], 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 1 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 [8].

FIG. 1. 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 {{1, 5}, {3, 4}}.

We first state the result and some consequences, using a minimal set of definitions. Detailed definitions appear in Section 2. It is convenient to view an oriented matroid O to be a matroid in which every circuit C (and cocircuit B) has been partitioned C = C^{+} ∪ C^{−}, (and B = B^{+} ∪ B^{−}) subject to a standard orthogonality condition. Each such partition is an unordered pair {C^{+}, C^{−}}, where one of the parts may be empty. For I ⊆ E(O), the reorientation O_{I} of O is the new oriented matroid obtained from O by repartitioning each circuit C (and cocircuit B) according to the

* Supported in part by the National Sciences and Engineering Research Council of Canada, and the Pacific Institute for the Mathematical Sciences.

† Supported by Ministry of Education of the Czech Republic as project LN00A056.

rules

\begin{matrix}\{C^{+}, C^{−}\} ↦ \{C^{+} △ (I ∩ C), C^{−} △ (I ∩ C)\}  and \\ \{B^{+}, B^{−}\} ↦ \{B^{+} △ (I ∩ B), B^{−} △ (I ∩ B)\}. \end{matrix}  (1)

where “△” is the symmetric difference operator.

Theorem 1.1. Let O be an oriented matroid of rank at most r. There exists a reorientation O_{I} in which every cocircuit B of size at least two satisfies

|B^{+}|, |B^{−}| ≥ |B|/f(r)

where f(3) ≤ 17, and f(r) ≤ 14r^{2} ln r for r ≥ 3.

For ℝ-represented matroids, our result specializes to a new bound on the discrepancies ‘in ratio’ that occur among the Radon partitions of minimally dependent sets of real vectors of small corank. To be more precise:

Corollary 1.2. Let (v_{e} : e ∈ E) be a list of nonzero vectors in ℝ^{r}. Then it is possible to replace some of these vectors by their negatives such that, for any minimal sublist {v_{e} | e ∈ C}, C ⊆ E of linearly dependent vectors, every nontrivial real solution to ∑_{e∈C} α_{e}v_{e} = 0 has at least |C|/f(|E| − r) coefficients α_{e} of each sign, where f(s) ≤ 14s^{2} ln s.

We may restate this result in the dual. The support of a vector t = (t_{e}) ∈ ℝ^{E} is supp(t) = {e ∈ E | t_{e} ≠ 0}. The rowspace of a matrix A is the set of vectors of the form yA, where y is a row vector.

Corollary 1.3. Let A ∈ ℝ^{R×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 t in the rowspace of the resulting matrix, if |supp(t)| ≥ 2 and supp(t) is minimal among the nonzero vectors in the rowspace, then t contains at least |supp(t)|/f(r) positive and negative entries each, where f(r) ≤ 14r^{2} ln r.

We remark that, if (v_{e} : e ∈ E) are the columns of a real matrix A, then the sets C ⊆ E, and supp(t) ⊆ E referred to in Corollaries 1.2 and 1.3 are, respectively, the circuits and cocircuits of the oriented matroid represented by the matrix A.

If each column v_{e} of A is the difference of two unit vectors, then we are in the setting of graph theory: Here A ∈ ℝ^{V ×E} is the {0, ±1}-valued vertexedge incidence matrix of a directed graph G⃗ = (V, E). Multiplying v_{e} by −1 corresponds to reorienting the edge e in G⃗.

A formula of Minty [11] relates the graph chromatic number χ(G) to ratios of the form |C|/|C^{+}| seen among reorientations of a G. Here Corollary 1.2 further specializes to the observation that χ(G) ≤ f(rk^{∗}(G)) for any loopless graph G = (V, E), where rk^{∗}(G) = |E| − |V | + 1 is the corank, or the first Betti number of G. For graphs, the upper bound on f can be improved to χ(G) ≤ f(s) ≤ ⌊\sqrt{2s}⌋ + 2. (This follows without much difficulty from Dirac’s density result [4] for colour critical graphs.) This bound on χ(G) is (essentially) attained by complete graphs. The above discussion indicates that the best function f for our result satisfies

⌊\sqrt{2s}⌋ + 2 ≤ f(s) ≤ 14s^{2} ln s.

We do not attempt to further optimize the function f(s) of Theorem 1.1.

2. BACKGROUND AND DEFINITIONS

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 reader is referred to [10] for details on matroid theory, and to [2] for information on oriented matroids and their geometry. The experienced reader may prefer to skip to the fourth subsection, although a couple of our oriented-matroid terms are non-standard.

2.1. Matroids

A matroid M is a ground set E = E(M) together with a collection of subsets called independent sets. Independent sets are closed under taking subsets, and they satisfy a well-known exchange axiom. A maximal independent set is a basis of M. Minimal dependent sets in M are circuits. A loop is a circuit of size one. Two elements are parallel if they form a circuit. The parallel class [e] is the equivalence class of elements parallel to e ∈ E. A matroid is simple if it has no loops or parallel elements. The girth of M is the least cardinality of one of its circuits. The rank, rk(X), of a set X ⊆ E is the maximum cardinality of an independent subset of X. We write rk(M) = rk(E(M)) for the rank of the matroid. A 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 hyperplane of M is an (r(M) − 1)-flat. A connected component of M is a maximal subset of E in which any two elements are contained in some circuit of M. A matroid with one component is connected.

The complements of the bases of M form the bases of the dual matroid M^{∗}. We have E(M) = E(M^{∗}). The prefix “co” refers to sets or properties of the dual matroid. In particular, a set X ⊆ E has corank k, is a coloop, a cocircuit, or a 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 cosimple if M^{∗} is simple. A cocircuit of M is characterized as 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.

By deleting (or contracting) an element e of M, we obtain a new matroid M\e (or M/e) on the ground set E(M) − {e}. The circuits of M\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\S/T denotes a matroid obtained by successively deleting the elements in S and contracting those in T. The matroid M\S/T is well defined and is called a minor of M.

The cycle 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 graphic, and its dual is cographic. We have that M(G) is connected if and only if G is a 2-connected graph. A matroid M is 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 ℝ-representable if it can be represented by a real matrix. If M can be represented over any field, then M is regular. A regular matroid can be represented by a totally unimodular matrix A, a real matrix whose subdeterminants all belong to {0, ±1}. The {0, ±1}-valued incidence matrix of a directed graph is totally unimodular, so graphic (and cographic) matroids are regular.

2.2. Oriented Matroids

Among the several equivalent formulations of ‘oriented matroid’, the following, which is due to Bland and Las Vergnas [3] (cf. [2, Theorem 3.4.3]), is best suited to our purpose. A signing of a set X is an unordered partition X⃗ = {X^{+}, X^{−}} of X = X^{+} ∪ X^{−}, where either part may be empty. A pair (C⃗, B⃗) of signed sets is orthogonal if

(C^{+} ∩ B^{+}) ∪ (C^{−} ∩ B^{−}) = ∅ ⟺ (C^{+} ∩ B^{−}) ∪ (C^{−} ∩ B^{+}) = ∅. (2)

This terminology reflects the fact that, for any two orthogonal vectors in Euclidean space, either their supports are disjoint, or there is both a positive and a negative summand in their scalar product.

Any orientation of a graph G naturally signs each circuit and cocircuit of its cycle matroid M(G). Moreover, each signed circuit-cocircuit pair (C⃗, B⃗) in M(G) is orthogonal. Accordingly, we define an oriented matroid on the ground set E to be a triple O = (M, C⃗, B⃗) where

1. M is a matroid with ground set E, circuits C, and cocircuits B.

2. C⃗ = {C⃗ | C ∈ C} and B⃗ = {B⃗ | B ∈ B} are signings of the circuits and cocircuits such that each pair in C⃗ × B⃗ is orthogonal.

The oriented matroid O = (M, C⃗, B⃗) is called an orientation of M, and M is said to be orientable. Graphic matroids are orientable; we write O(G⃗) for the oriented matroid associated with a directed graph G⃗. More generally, matroids which are ℝ-representable are orientable. Moreover, every real matrix representation M = M[A] naturally induces an orientation O[A] of M. The signings of circuits C = C^{+} ∪ C^{−} in O[A] are the Radon partitions of minimally dependent sets of columns {v_{e} | e ∈ C} of A. Specifically, the Radon partition of C is determined by the signs of the real coefficients α_{e} in a non-trivial solution to ∑_{e∈C} α_{e}v_{e} = 0. The signings of cocircuits of O are determined by the sign patterns of nonzero vectors in the row-space of A having minimal support. 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 is regular. Every orientation of a regular matroid can be represented by a totally unimodular matrix.

Let O = (M, C⃗, B⃗) be an oriented matroid. For any I ⊆ E, the reorientation O_{I} defined by (1) is easily seen to be an oriented matroid. The operation O ↦ O_{I} is analogous to reversing a subset I of the edges of a directed graph. The orientations of M are partitioned into reorientation classes, where the class of O is defined to be [O] = {O_{I} | I ⊆ E}. For sake of brevity, we say that [O] is a 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 unoriented graph G is well defined by [O(G)] = [O(G⃗)] for some orientation G⃗ of G. For any connected component I of O, we have O_{I} = O. Indeed each reclass of M contains precisely 2^{|E|−ω} orientations of M, where ω is the number of connected components of M.

Matroidal notions such as connectedness, simplicity, flats, and the rank function rk(·) naturally carry over to oriented matroids and to reclasses. Matroid minors also carry over naturally: for disjoint subsets S, T ⊆ E(O), the minor O/S\T is the orientation of the matroid minor M/S\T obtained by restricting the signings in C⃗∪B⃗ to the circuits and cocircuits of M/S\T. The dual of O = (M, C⃗, B⃗) is defined by O^{∗} = (M^{∗}, B⃗, C⃗). An oriented matroid (M, C⃗, B⃗) is uniquely determined by either of the pairs (M, C⃗) or (M, B⃗).

2.3. Geometry

There is a bijective correspondence between simple reclasses [O] and topological objects called pseudosphere complexes. This is due to Folkman/Lawrence [7] and Edmonds/Mandel [12]. We describe a pseudosphere complex in the case O is ℝ-representable, and outline the construction for general reclasses [O]. We then specialize to rank 3 and the easy-to-visualize wiring diagrams.

Let O = O[A] where each column v_{e} of A is a vector in ℝ^{r}. Let S_{0} = {x ∈ ℝ^{r} | ||x|| = 1} be the unit (r − 1)-sphere. Each e ∈ E(O) corresponds to an (r − 2)-subsphere H_{e}, called a pseudohypersphere, and consisting of those vectors in S_{0} which are orthogonal to v_{e}. The positive side of H_{e} are the vectors in S_{0} having a positive scalar product with v_{e}. The pseudosphere complex S = S[O] is the family of subspheres of S_{0} that can be obtained as intersections of pseudohyperspheres. Each subsphere in S is a k-sphere for some k, and is called a k-pseudosphere. Evidently, a k-flat F of O corresponds to the set of pseudohyperspheres {H_{e} | e ∈ F } which contain a particular (r − k − 1)-pseudosphere in S. This correspondence between flats and pseudospheres is bijective. In particular, the hyperplanes of O correspond to 0-spheres in S. (A 0-sphere consists of two “antipodal” points of S_{0}.) Accordingly, each 0-sphere S ∈ S corresponds to a cocircuit B = {e ∈ E | H_{e} ∩ S = ∅}. The signing B = B^{+} ∪ B^{−} is found by determining, for each e ∈ B, which of the two points of S lies on the positive side of H_{e}. A reorientation O_{I} corresponds to interchanging the positive and negative sides of H_{e}, for each e ∈ I. Thus the complex S is well defined by the reclass [O].

The pseudosphere complex of a general simple reclass [O] of rank r is similarly defined, except that pseudospheres are no longer constrained to lie on subspaces of ℝ^{r}. Instead, pseudospheres are topological subspheres of S_{0} which are subject to certain axioms. 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 pseudosphere complexes can be found in [7].

Deleting an element e of O corresponds to deleting the pseudohypersphere H_{e} in the construction of S[O]. Contracting e in O corresponds to restricting the complex S[O] to those pseudospheres contained in H_{e}. Here H_{e} plays the role of S_{0} and the pseudohyperspheres of S[O/e] are the (r − 2)-pseudospheres {H_{e} ∩ H_{f} | f ∈ E − {e}}. Thus contracting a flat F in O corresponds to restricting S to those pseudospheres contained in S_{F}, where S_{F} is the pseudosphere in S corresponding to F. Here, the cocircuits of O/F correspond bijectively to those 0-pseudospheres in O which are contained in S_{F}. We have rk(O/F) = rk(O) − rk(F).

In a rank-3 pseudosphere complex S = S[O], the pseudohyperspheres are simple closed curves on a 2-sphere S_{0}. Any two such curves “cross” at a 0-pseudosphere in S. The axioms ensure that S_{2} contains an equator, a simple closed curve K in general position such that every 0-pseudosphere has one point on each side of K. By restricting the complex to one side of K, we obtain an affine representation of S called a wiring diagram. A wiring diagram is a set of smooth plane curves {C_{e} | e ∈ 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 a vertex which corresponds to the cocircuit {e ∈ E | C_{e} ∌ x} ∈ B(O). An oriented matroid in [O] is determined by designating, for each e ∈ 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}. See Figure 1 for an example. If O 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. Because of the choice in selecting the equator K, several wiring diagrams may correspond to the same oriented matroid. The curves C_{e} may be drawn as straight lines if and only if O is ℝ-representable.

2.4. Oriented Flow Number

We define the imbalance or log-discrepancy of a signed set X⃗ = {X^{+}, X^{−}}, where X = X^{+} ∪ X^{−} ⊆ E, by

2 ≤ imbal(X⃗) = \frac{|X|}{min\{|X^{+}|, |X^{−}|\}} ≤ ∞.

Here, the value ∞ indicates that one of X^{+}, X^{−} is empty.

Minty [11] considered the graph invariant

χ_{o}(G) := min_{G⃗} max_{C⃗} imbal(C⃗),

where G⃗ varies over the set of orientations of G, and C⃗ varies over the set of signed circuits in G⃗. He showed that the graph chromatic number is given by χ(G) = ⌈χ_{o}(G)⌉. The invariant χ_{o}(G), now called the circular chromatic number, has several equivalent definitions and has seen a flurry of recent interest (see [17] for a survey). Within graph theory, this invariant is more usually denoted by χ_{c} or χ^{∗}, but we use χ_{o} to emphasize the viewpoint of orientations.

The definition of χ_{o} 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 oriented flow number of an oriented matroid to be

ϕ_{o}(O) := min_{O_{I}} max_{B⃗} imbal(B⃗),

where O_{I} varies over the set of reorientations of O, and B⃗ varies over the signed cocircuits in O_{I}. The oriented flow number of any reclass [O] is well defined by ϕ_{o}([O]) = ϕ_{o}(O). If a matroid M has a unique reclass [O] (e.g. if M is regular), then ϕ_{o}(M) is well defined to equal ϕ_{o}([O]). Thus χ_{o}(G) = ϕ_{o}(M^{∗}(G)) where M^{∗}(G) denotes the (cographic) dual of the cycle matroid M(G). In general, the oriented flow number of an orientable matroid M is not well defined.

Example 2.1. The uniform matroid U_{3,6} is orientable and has precisely four reclasses, [O_{i}], 1 ≤ i ≤ 4 (see e.g. [5]), whose wiring diagrams are shown in Figure 2.

O_{1}  O_{2}  O_{3}  O_{4}

FIG. 2. The four reclasses of the uniform matroid U_{3,6}.

The first diagram shows an orientation with imbalance 2. We claim that the other three reclasses have no such orientation. Let P be an 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 leads to an easy contradiction. Since all cocircuits have size 4, the oriented flow number of [O_{i}] equals 2 or 4. Therefore ϕ_{o}([O_{1}]) = 2 and ϕ_{o}([O_{i}]) = 4 for i = 2, 3, 4.

In case M is graphic, ϕ_{o}(M) = ϕ_{c}(G) is the circular flow number of a graph G. This graph invariant, essentially introduced by Tutte [16], is also of contemporary interest [15, 18]. Seymour [14] showed that ϕ_{c}(G) ≤ 6 for any 2-edge connected graph G. More generally, there is an algebraic description of the oriented flow number ϕ_{o}(M) of any regular matroid implicit in the work of Hoffman [9], and made explicit in [8]. In particular, if A is a totally unimodular matrix representing the regular matroid M, then

ϕ_{o}(M) = inf{α ∈ ℝ | ∃x ∈ ℝ^{E}, Ax = 0, 1 ≤ |x_{e}| ≤ α − 1 for e ∈ E }.

If O has a coloop, then ϕ_{o}(O) = ∞. The converse also holds, since every coloop-free oriented matroid has a totally cyclic reorientation, one in which every signed cocircuit B⃗ satisfies B^{+}, B^{−} ≠ ∅. With this terminology, we may restate our main result.

Theorem 2.1. For any coloop-free oriented matroid O of rank r,

ϕ_{o}(O) ≤ 14r^{2} ln r.

We may define the ‘chromatic number’ of O to be the invariant

χ_{o}(O) = ϕ_{o}(O^{∗}).

Incidentally, χ_{o}(O) is much easier than ϕ_{o}(O) to bound by a function of the rank r = rk(O). Since no circuit of O has cardinality more than r + 1, no circuit of O has imbalance greater than r + 1 in a totally cyclic orientation of O^{∗}. It follows that χ_{o}(O) ≤ r + 1 for any loopless oriented matroid O of rank r. This bound is best possible since it is achieved when O is (an orientation of) the complete graph M(K_{r+1}).

3. LOW RANK

The odd cogirth of an oriented matroid O is the least odd integer 2k + 1 such that O has a cocircuit of cardinality 2k + 1. We define the odd cogirth bound number of O to be the rational number

ocb(O) = 2 + 1/k,

where 2k + 1 is the odd cogirth of O. If O has no odd cocircuits then we define its odd cogirth to be ∞ and ocb(O) = 2. The imbalance of any signed cocircuit of size 2k + 1 is at least (2k + 1)/k. Thus we have the following.

Proposition 3.1. For any oriented matroid O we have ϕ_{o}(O) ≥ ocb(O).

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 2.1. However, the bound is exact for oriented matroids of low rank.

Lemma 3.2. Every oriented matroid O of rank at most 2 satisfies ϕ_{o}(O) = ocb(O). In particular, ϕ_{o}(O) ≤ 3 if O is coloop-free.

Proof. If rk(O) = 1, then O is an orientation of a single parallel class. Orienting this cocircuit as equitably as possible gives ϕ_{o}(O) = ocb(O).

If the rank equals two, then we may affinely represent O as a list of points P = (p_{e} | e ∈ E) on the real number line. Let us label the elements with e_{1}, …, e_{n} so that p_{e_{1}} ≤ … ≤ p_{e_{m}}. For each p ∈ P there is a corresponding cocircuit B_{p} = {e ∈ E | p_{e} ≠ p}. We sign B_{p} according to

B_{p}^{+} = {e_{i} | p_{e_{i}} < p and i is odd} ∪ {e_{i} | p_{e_{i}} > p and i is even}.

It is easy to verify that this gives an orientation of O, and that every cocircuit B_{e} satisfies |B_{e}^{+}|−|B_{e}^{−}| ∈ {0, ±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 ϕ_{o}(O) = ocb(O).

4. RANDOM RESIGNINGS AND RANK 3

We shall make use of the Chernoff bound from probability theory (see e.g. [1]).

Lemma 4.1. If X_{1}, …, X_{m} = ±1 are i.i.d. random variables with probability 1/2, then for λ > 0 we have

Prob (|∑_{i} X_{i}| > λ\sqrt{m}) < 2e^{−λ^{2}/2}.

Here is some convenient terminology. Let A be a subset of a cocircuit B, and let B⃗ = {B^{+}, B^{−}} be a signing of B. For s ≥ 2, we say that A is s-unbalanced in B⃗ if either one of A ∩ B^{+} and A ∩ B^{−} is empty or

\frac{|A|}{min\{|A ∩ B^{+}|, |A ∩ B^{−}|\}} > s.

If B⃗ is a signed cocircuit in an oriented matroid O, and B is s-unbalanced in B⃗, then we say that B is s-unbalanced in O. Therefore

ϕ_{o}(O) = min_{I⊆E} inf{s ∈ ℝ : no cocircuit is s-unbalanced in O_{I}}. (3)

A random resigning of a subset R ⊆ E(O) is a reorientation O_{I} where I is uniformly selected among the subsets of R.

Lemma 4.2. Let A be a nonempty subset of a cocircuit B in O, and let R satisfy A ⊆ R ⊆ E. Let B⃗ be the signing of B in a random resigning of R. Then for s ≥ 2 the probability that A is s-unbalanced in B⃗ is less than

2 exp (− (1 − \frac{2}{s})^{2} \frac{|A|}{2}) .

Proof. We define random variables {X_{e} | e ∈ A} by

X_{e} = \{ \begin{matrix}1 & if e ∈ B^{+} \\ −1 & if e ∈ B^{−}. \end{matrix}

Then A is s-unbalanced in B⃗ if and only if | ∑_{e∈A} X_{e}| > (1 − \frac{2}{s})|A|. Since A ⊆ R, the random variables are i.i.d. among the resignings of R. The result follows by applying the Chernoff bound with λ = (1 − \frac{2}{s}) \sqrt{|A|}.

We shall now prove a bound on ϕ_{o}(O) in case O has rank 3.

Figure 3 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. We say that these orientations are alternating with respect to the equators shown. The reader will notice that the orientation described in the proof of Lemma 3.2 is alternating in a similar sense. Alternating orientations of matroids of rank ≤ 3 tend to result in good upper bounds on ϕ_{o}(O).

FIG. 3. Three wiring diagrams with alternating orientations.

Lemma 4.3. Let O be a coloop-free oriented matroid of rank 3. Then ϕ_{o}(O) ≤ 17. Moreover, if O is simple and n = |E(O)| is large, then

ϕ_{o}(O) ≤ max {ocb(O), 2 + O ((n/ ln n)^{−1/3})} .

In particular, if n ≥ 159 (n ≥ 427), then ϕ_{o}(O) ≤ 4 (resp. ϕ_{o}(O) ≤ 3).

Proof. We may assume O has no loops. Suppose that S = {f_{1}, f_{2}} are parallel elements in O such that O\S is coloop-free. By orienting f_{1} and f_{2} oppositely and using induction, one easily sees ϕ_{o}(O) ≤ ϕ_{o}(O\S) ≤ 17. Thus, we may assume that O\S has a coloop for all such pairs and, hence, any two parallel elements of O are contained in a cocircuit of size 3. If O is not simple, then O has n + 3 elements for some n ≥ 0, and O corresponds to one of the three wiring diagrams as drawn in Figure 3 (the cocircuit is {f_{1}, f_{2}, f_{3}}). The alternating reorientations shown there, imply that ϕ_{o}(O) ≤ 3 if O has no coloops. Thus we may assume O is simple.

Let k = min{|B| | B ∈ B(O)} be the cogirth of O. Let B_{0} be a cocircuit of size k in O. 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 4 (the diagram is undetermined under the white box). We consider an alternating reorientation O′ of O as shown in the diagram.

FIG. 4. An alternating reorientation O′ defined by a smallest cocircuit B_{0}.

By design, we have imbal_{O′}(B_{0}) ≤ ocb(O) ≤ 3. Every other cocircuit B ∈ B(O′) − {B_{0}} contains all but possibly one element of E − B_{0}. Since O′ is alternating, we therefore have |B^{+}|, |B^{−}| ≥ ⌊(n − k − 1)/2⌋. Since |B| ≤ n − 2, this implies imbal_{O′}(B) ≤ g(n, k) where

g(n, k) = \frac{n − 2}{(n − k)/2 − 1} = \frac{2n − 4}{n − k − 2}.

Thus the reorientation O′ shows that if 2 ≤ k ≤ n − 3, then

ϕ_{o}(O) ≤ max { ocb(O), g(n, k) } . (4)

We note that ocb(O) > g(n, k) only if k ≤ \sqrt{n − 2}.

Let O_{I} be a random resigning of E(O). Clearly, O has at most \binom{n}{2} cocircuits, all of which have size at least k. By Lemma 4.2, the probability that some cocircuit of O_{I} is s-unbalanced is less than

2\binom{n}{2} exp (− (1 − \frac{2}{s})^{2} \frac{k}{2} ) . (5)

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 (2\binom{n}{2}). When s ≥ f(n, k), at least one of the random reorientations O_{I} has no s-unbalanced cocircuits. Therefore by (3), if 4 ln n ≤ k ≤ n − 2, then

ϕ_{o}(O) ≤ f(n, k). (6)

For fixed n ≥ 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 ≤ k ≤ n − 2. The bounds in (4) and (6) are illustrated in Figure 5 for n = 30. In the plot of ocb(O) versus k in this figure reflects the fact ocb(O) = 2k/(k − 1) if the cogirth k is odd, but that one can only deduce ocb(O) ∈ {2} ∪ {2 + 1/i | i ≥ k/2} if k is even.

FIG. 5. f(n, k), g(n, k), and ocb(O) versus k, when n = 30.

Using a computer algebra system, we find that g(n, k) = f(n, k) when

k = k_{0} = ^{3} \sqrt{2(n − 2)^{2} ln (n(n − 1))}.

We have shown ϕ_{o}(O) ≤ max{ocb(O), h(n)} where

h(n) = g(n, k_{0}) = \frac{2n − 4}{n−2 − ^{3} \sqrt{2(n−2)^{2} ln(n(n−1))}} = 2 + O((\frac{n}{ln n})^{−1/3}) .

Using the trivial bound ϕ_{o}(O) ≤ max{ |B| | B ∈ B(O)} ≤ n − 2 and the easily verified fact that f(n, k_{0}) ≤ 17 when n ≥ 19, we have proven ϕ_{o}(O) ≤ 17.

We further find that ϕ_{o}(O) ≤ 4 (resp. 3) provided that n ≥ 166 (resp. 712). However, we can improve the above argument in case we are trying to prove ϕ_{o}(O) ≤ s for some s ≤ 4. When n ≥ 162 one finds that k_{0} < (n − 1)/2, which roughly corresponds, by (5), to s ≤ 4. Since O is simple, it contains at most one cocircuit of size less than (n − 1)/2, and at most

\binom{n}{2} − \binom{n − k}{2} ≤ \frac{3n(n − 2)}{8}

cocircuits of size at least (n − 1)/2. For s ≥ ocb(O), we may assume k ≥ (n − 2)(s − 2)/s since otherwise ϕ_{o}(O) ≤ s by (4). Therefore, in case k ≤ n/2 − 1, we may replace (5) with the smaller quantity

2 exp(−(1− \frac{2}{s})^{2} \frac{(n−2)(s−2)}{2s}) + 2(\frac{3n(n−2)}{8})exp(−(1− \frac{2}{s})^{2} \frac{n−1}{4}) .

It is straight forward to verify that this expression is at most 1 when n ≥ 427 (for s = 3), and when n ≥ 159 (for s = 4).

With extra work, the minor restriction that O is simple can be omitted from the statement of Lemma 4.3. The bound ϕ_{o}(O) ≤ 17 is probably far from optimal.

Conjecture 4.4. Every coloop-free oriented matroid O of rank 3 satisfies ϕ_{o}(O) ≤ 4.

5. DENSE FLATS

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 proof of Lemma 4.3 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.

Let G be graph obtained from the complete graph K_{10} by replacing each vertex v_{i} ∈ V (K_{10}) with a copy, K(i), of K_{1000}. For each v_{i}v_{j} ∈ 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 \binom{1000}{2} edges which form a flat, say F_{i}, in the cycle matroid M(G). Because the graph G has cogirth only nine and a large number of cocircuits (about 2^{10000}), a naïve application of Lemma 4.2 would result in a very poor bound on ϕ_{o}(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})) ⊆ 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} ∪ … ∪ 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 O, we must first define a suitable set of elements in O which can play the role of F_{i} in this example.

Let O be an oriented matroid with E = E(O). A flat F is dense in O if

\frac{|F |}{|E|} ≥ \frac{rk(F) + 1}{rk(E) + 1}.

A dense flat F is minimal if no proper subflat of F is dense in O. Since E is dense and ∅ is not dense, O has a minimal dense flat and all minimal dense flats are nonempty. A cocircuit B is F -intersecting if B ∩F ≠ ∅. Let B_{F} denote the set of F -intersecting cocircuits in O. We first show that a substantial portion of any F -intersecting cocircuit lies within F.

Lemma 5.1. Let F be a minimal dense flat in O, and let B ∈ B_{F}. Then

|B ∩ F | > \frac{|E|}{rk(E) + 1}.

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, B ∩ F ≠ ∅ implies that F′ := F ∩ (E − B) is a proper subflat of F in O satisfying

\frac{|F′|}{|E|} = \frac{|F |}{|E|} − \frac{|B ∩ F |}{|E|} ≥ \frac{rk(F) + 1}{rk(E) + 1} − \frac{1}{rk(E) + 1} ≥ \frac{rk(F′) + 1}{rk(E) + 1}.

This contradicts that F is minimally dense in O.

Lemma 5.2. Let O be an oriented matroid of rank r ≥ 3 and size n. Let R ⊆ E(O) and F ⊆ R be a minimal dense flat in O. Suppose that t ∈ ℝ satisfies 19r^{2} ln r ≤ t ≤ 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.

Proof. Let B ∈ B_{F}. In any reorientation of O, if B^{+} ≠ ∅, we have by Lemma 5.1,

\frac{|B|}{|B^{+}|} ≤ \frac{n}{|B^{+}|} ≤ ϱ \frac{|B ∩ F |}{|B^{+} ∩ F |}

where ϱ = r +1. 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 ∩ F is \frac{t}{ϱ}-unbalanced in B. By Lemmas 4.2 and 5.1 this probability is at most

2 exp (− (1 − \frac{2ϱ}{t})^{2} \frac{|B ∩ F |}{2}) ≤ 2 exp (− (1 − \frac{2ϱ}{t})^{2} \frac{n}{2ϱ}) =: P.

We aim to show

n^{2}|B_{F} |P < 1. (7)

We estimate |B_{F} | ≤ \binom{n}{r−1} ≤ \frac{n^{ϱ−2}}{2} (for r ≥ 3). Thus (7) holds provided that n^{ϱ} · \frac{P}{2} < 1. Equivalently, we aim to show

ϱ ln n − (1 − \frac{2ϱ}{t})^{2} \frac{n}{2ϱ} < 0 ,

2\frac{ln n}{n} < (\frac{1}{ϱ} − \frac{2}{t})^{2} . (8)

For any integer r_{0} ≥ 3, let f(r_{0}) be the smallest positive number such that every integer r ≥ r_{0} satisfies

f(r_{0}) r^{2} ln r ≤ e^{−1/2} r^{f(r_{0}) r_{0}^{2}/(2(r_{0}+1)^{2})}.

It is straight forward to verify that f(3) ≤ 19, f(4) ≤ 14, f(5) ≤ 12, and that f(r) → 4 slowly. Writing t_{0} = f(r_{0}) r^{2} ln r, and ϱ = r + 1, we have for r ≥ r_{0} ≥ 3,

ln t_{0} ≤ \frac{f(r_{0}) r_{0}^{2}}{2(r_{0} + 1)^{2}} ln r − \frac{1}{2} ≤ \frac{f(r_{0}) r^{2}}{2(r + 1)^{2}} ln r − \frac{2}{ϱ} = \frac{t_{0}}{2ϱ^{2}} − \frac{2}{ϱ}.

Together with t_{0} ≤ t ≤ n, this completes the proof since the left hand side of (8) is at most 2\frac{ln t_{0}}{t_{0}} , whereas the right hand side is at least \frac{1}{ϱ^{2}} − \frac{4}{ϱ t_{0}} .

6. PROOF OF MAIN THEOREM

Let O be an oriented matroid. To prove the bound on ϕ_{o}(O), we shall construct an ordered partition (F_{0}, F_{1}, …, F_{p}) of E(O) as follows. Let F_{0} be a minimal dense flat in O_{0} = O and suppose we have constructed F_{0}, F_{1}, …, F_{k}, for some k ≥ 0. If ⋃_{i=0}^{k} F_{i} = E(O), then we set p = k and output the list. Otherwise let F_{k+1} be a minimal dense flat in the contracted oriented matroid (minor)

O_{k+1} := O /(⋃_{i=0}^{k} F_{i}) = O_{k}/F_{k} .

(See Section 2.3 for the geometric interpretation of contracting a flat.)

Since each F_{k} is nonempty and O is finite, this procedure must terminate. Any sequence (F_{0}, F_{1}, …, F_{p}) constructed in this way is called a dense flat sequence of O.

Let (F_{0}, F_{1}, …, F_{p}) be a dense flat sequence for O. A cocircuit B of O is of type k if k is the least index for which B ∩ F_{k} ≠ ∅. Thus the cocircuits in O_{k} are precisely the cocircuits of type ≥ k in O. Let B_{k} be the set of cocircuits of type k in O, let n_{k} = |O_{k}| and let r_{k} = r(O_{k}) = r(O) − ∑_{i=0}^{k−1} r(F_{i}). Figure 6 may help the reader with these definitions and the proof that follows.

Theorem 6.1. For any oriented matroid O of rank r and without coloops,

ϕ_{o}(O) < 14r^{2} ln r.

FIG. 6. A dense flat sequence and a cocircuit B of type 2

Proof. We show that O has a reorientation in which no cocircuit is t_{0}-unbalanced, where t_{0} = 14r^{2} ln r. Let (F_{0}, F_{1}, …, F_{p}) be a dense flat sequence for O, with O_{k}, B_{k}, n_{k}, r_{k} defined as above. Let q be the least integer for which either r_{q} ≤ 3 or n_{q} ≤ t_{0}. If r_{q} ≤ 3, then by Lemma 4.3, O_{q} may be reoriented so that every cocircuit in O_{q} has imbalance at most 17. If n_{q} ≤ t_{0}, then in any totally cyclic orientation of O_{q}, we have that every cocircuit has imbalance at most t_{0}−2. In any case we find a reorientation O′ of O 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 O_{q}”, namely R_{0} := ∪_{i=0}^{q−1}F_{i}, in O′ to obtain O′′. We aim to show that with probability greater than zero, no cocircuit is t_{0}-unbalanced in O′′. By choice of q we have r_{k} ≥ 4 and n_{k} > t_{0}, for 0 ≤ k ≤ q−1. So applying Lemma 5.2 to O_{k} and F_{k} with R = R_{k} := ∪_{i=k}^{q−1}F_{i}, we find that the probability that a cocircuit in B_{k} is t_{0}-unbalanced in O_{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 B_{k} is contained in E(O_{k}). Since (B_{0}, B_{1}, …, B_{q−1}, B(O_{q})) is a partition of the cocircuits of O′′, the probability that some cocircuit in O′′ is max{t_{0}, 17}- unbalanced is at most

∑_{k=0}^{q−1} n_{k}^{−2} ≤ ∑_{i=t_{0}+1}^{∞} i^{−2} < 1.

Thus ϕ_{o}(O) ≤ max{t_{0}, 17} = t_{0}.

7. SMALL EXAMPLES

TABLE 1. 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.

\begin{matrix}s\n & 5 & 6 & 7 & 8 \\ 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) \\ Total & 1 (1) & 17 (4) & 206 (11) & 6029 (135) \end{matrix}

Using an implementation by Lukas Finschi [5] of a simple reclass generator described in [6], together with a program of Timothy Mott [13], for calculating χ_{o}(O), we have found the following results.

For various values of n and s we list in Table 1 the number of coloopfree cosimple reclasses [O] of rank 3 and size n for which ϕ_{o}([O]) = s. In parentheses, we record the number of these which are reclasses of the uniform matroid U_{n,3}. If O 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(O) by Lemma 3.2.

For rank 4, we find that, there are 143 reclasses [O] of size 7. The number of these which have ϕ_{o}([O]) = s is tabulated as follows, with parentheses indicating the number of which are uniform.

s = 2 : 1(1)  s = 3 : 12(0)  s = 4 : 130(10).

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 ϕ_{o}(O) > Θ(\sqrt{rk(O)}).

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 χ_{o}(O).

REFERENCES

1. N. Alon and J.H. Spencer, “The Probabilistic Method,” 2nd ed., John Wiley and Sons, New York, 2000.

2. A. Björner, M. Las Vergnas, B. Sturmfels, N. White and G. Ziegler, “Oriented Matroids,” Encyclopedia of Mathematics and its Applications, 46, Cambridge University Press, Cambridge, 1993.

3. R. G. Bland, M. Las Vergnas, Orientability of matroids, J. Combin. Theory Ser. B, 24 (1978), 94–123.

4. 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.

5. L. Finschi, Catalog of oriented matroids, http://www.om.math.ethz.ch/?p=catom

6. L. Finschi, K. Fukuda, Generation of oriented matroids – A graph theoretical approach, Discrete Comput. Geom. 27 (2002), 117–136.

7. J. Folkman and J. Lawrence, Oriented Matroids, J. Combin. Theory Ser. B, 25 (1978), 199–236.

8. L.A. Goddyn, M. Tarsi, C.-Q. Zhang, On (k, d)-colorings and fractional nowhere zero flows, J. Graph Theory, 28 (1998), 155–161.

9. 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.

10. J.G. Oxley “Matroid Theory” 2nd ed., Oxford University Press, Oxford, 1992.

11. G. J. Minty, A theorem on n-coloring the points of a linear graph, Amer. Math. Monthly 69 (1962) 623–624.

12. A. Mandel, “Topology of Oriented Matroids,” Ph.D. Thesis, University of Waterloo, 1982.

13. T. Mott, NSERC Summer Student Project, Simon Fraser University, June 2002.

14. P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981), 130–135.

15. P. D. Seymour, Nowhere-zero flows. Appendix: Colouring, stable sets and perfect graphs. Handbook of combinatorics, Vol. 1, 2, 289–299, Elsevier, Amsterdam, 1995.

16. W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math. 6 (1954) 80–91.

17. X. Zhu, Circular chromatic number: a survey, Discrete Math. 229 (2001) 371–410.

18. Z. Pan, X. Zhu, Construction of graphs with given circular flow numbers, J. Graph Theory 43 (2003) 304–318.