Balancing Covectors

Laura Chávez-Lomelí Affiliation

Luis Goddyn SFU

Winfried Hochstättler FernUniversität in Hagen

July 23, 2008

Abstract

Recently, Goddyn, Hochstättler and Hliněný proved that the oriented flow number introduced by Goddy, Tarsi and Zhang for an oriented matroid of rank r is bounded by 14r^{2} ln r. We improve this bound by showing that any oriented matroid without a coloop admits a reorientation such the imbalance of each covector is at most 3r − 1. In particular this yields a new upper bound for the oriented flow number.

1 Introduction

This paper is concerned with a generalization of the graph chromatic number to geometric hyperplane arrangements and to oriented matroids. There are at least two ways to extend the definition of graph chromatic number to the class of oriented matroids [3, 4]. One consequence of our main result is a significant improvement in the upper bound derived in [2] regarding the the oriented flow number. Moreover, the argument in this paper is somewhat easier than the probablisitic method used in [2].

Although the our result uses the slightly arcane language of oriented matroids, the specialization of the result to represented oriented matroids is easily accessible to a nonspecialist.

Theorem 1. Let A be a real matrix of rank r such that deleting any of its columns preserves its rank. It is possible to multiply some columns of A by −1 so that, for every vector t in the row space of the resulting matrix, the number of positive entries in t is at most 3r −2 times the number of negative entries in t.

Before stating the general result, we review some terminology and notation for oriented matroids using a variation of that used in the standard reference [1]. A signed subset X of a ground set E is a subset \underline{X} ⊆ E (the support of X) together with an ordered partition (X^{+}, X^{−}) of \underline{X}, where either of the parts may be empty. If L is an ordinary subset of E, then X ∩ L denotes the signed subset with support \underline{X} ∩E and partition (X^{+}∩L, X^{−}∩L).

An oriented matroid O on the ground set E can be presented as a set L of covectors. Each covector in L is a signed subset of E, and L satisfies the covector axioms listed in [1, §4.1.1]. If F ⊆ E, then the reorientation O_{F} of O specified by F is the oriented matroid obtained from O by replacing each covector (X^{+}, X^{−})by (X^{+} △ (F ∩ \underline{X}), X^{−} △ (F ∩ \underline{X})), where △ is the symmetric difference operator. The restriction O.F of O to F is the oriented matroid on ground set F which is the result of replacing each covector (X^{+}, X^{−}) by (X^{+} ∩ F, X^{−} ∩ F). The imbalance of a signed subset X is defined to be

imbal(X) = min \{\frac{|\underline{X}|}{|X^{+}|}, \frac{|\underline{X}|}{|X^{−}|}\} ,

if both X^{+} and X^{−} are non-empty. It is convenient to define the imbalance of X to be ∞ if exactly one of X^{+}, X^{−} is empty and 0 if both are. It is well-known that any oriented matroid without coloops admits a totally cyclic reorientation. In a totally cyclically oriented matroid, any covector X satisfies X^{+} ≠ ∅ ≠ X^{−}, and hence imbal(X) ≤ |\underline{X}|.

Theorem 2. Every oriented matroid O of rank r and having no coloop has a reorientation in which every covector has imbalance at most 3r − 1.

For an oriented matroid O we denote by C^{∗} its set of cocircuits. Since cocircuits are just the covectors of minimal non-empty support, as a corollary of Theorem 2 we derive a considerable improvement on the upper bound of the oriented flow number of an oriented matroid without coloop. For an oriented matroid O the oriented flow number ϕ_{o}(O) is defined as

ϕ_{o}(O) := min_{F ⊆E} max_{D∈C^{∗}(O_{F})} imbal(D).

This invariant was is introduced in [3] as a generalization of (the dual of) the circular chromatic number. In [2] an upper bound of 14r^{2} ln r for an oriented matroid of rank r was derived using the probabilistic method.

Corollary 3. Let O be an oriented matroid of rank r without coloops. Then ϕ_{o}(O) ≤ 3r − 1.

2 Proof of Theorem 2

A circuit C in a connected matroid M is removable, if M \C is still connected and the rank of M \ C equals the rank of M. We denote by c(M) the circumference of M which is the cardinality of the largest circuit in M.

Lemma 4 (Lemos, Oxley[5]). Let M be a connected matroid of rank r. If |E(M)| ≥ 3(r + 1) − c(M), then M has a removable circuit.

The following almost trivial observation will prove helpful.

Proposition 5. Let X be a signed subset of E and E = E_{1} ˙∪ … ˙∪E_{k} a partition. Then

imbal(X) ≤ max{imbal(X ∩ E_{1}), …, imbal(X ∩ E_{k})}.

Proof of Theorem 2. Since no loop is contained in any covector, we may assume that M, the matroid underlying O, has no loops. By Proposition 5 we may furthermore assume that M is connected.

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

Assume now |E| ≥ 3r. If r = 1, then M is isomorphic to a graph with two vertices and |E| edges and an alternating reorientation yields an imbalance of the unique covector of O of at most \frac{2|E|}{|E|−1} ≤ 3 (see [2] for details). If r ≥ 2 then c(M) ≥ 3, hence

|E| ≥ 3(r + 1) − c(M),

and Lemma 4 yields a removable circuit. Inductively, we find circuits C_{1}, …, C_{k} which are pairwise disjoint such that, setting L = E \⋃_{i=1}^{k} C_{i}, the restriction M.L is still connected of rank r and |L| < 3r. Next, we choose a reorientation Õ of O such that each of Õ.L, Õ.C_{1}, …, Õ.C_{k} is totally cyclic.

Now, let X ∈ L(Õ) be an arbitrary covector. We partition X according to the above partition of the groundset E = C_{1} ˙∪ … ˙∪C_{k} ˙∪L into

X_{L} = X ∩ L, and X_{i} = X ∩ C_{i} for 1 ≤ i ≤ k.

Each X_{i} is a covector in O.C_{i} and hence

imbal(X_{i}) ≤ |\underline{X_{i}}| ≤ |C_{i}| ≤ r + 1 for all 1 ≤ i ≤ k

and similarly

imbal(X_{L}) ≤ |\underline{X_{L}}| ≤ |L| ≤ 3r − 1.

Finally, applying Proposition 5 yields

imbal(X) ≤ max {imbal(X_{L}), imbal(X_{1}), …, imbal(X_{k})} ≤ 3r − 1.

3 Concluding Remarks

Our proof suggests the definition of a new parameter related to the flow resp. chromatic number

ϕ_{L}(O) := min_{F ⊆E} max_{X∈L(O_{F})} imbal(X)

which measures the possibility to balance all covectors in an oriented matroid. It is not difficult to compute that

ϕ_{L}(O^{∗}(K_{n})) = \binom{n}{2} = r(O(K_{n})^{∗}) + χ(K_{n}) − 1

for the cographic matroid of the K_{n}. Hence, the bound for ϕ_{L}(O) derived in this paper is larger only by a factor of three from the value attained. It is far from the truth for the chromatic number of K_{n}, i.e. the flow number of K_{n}^{∗}. We conjecture that the cographic matroid of the complete graph is a worst case example for the flow number and hence finish with the question:

Question 6. Is there an oriented matroid of rank r such that

ϕ_{o}(O) ≥ 2 + \sqrt{2r}.

References

[1] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler, Oriented matroids, Cambridge University Press, March 1993.

[2] Luis Goddyn, Petr Hliněný, and Winfried Hochstättler, Balanced signings and the chromatic number of oriented matroids, Comb. Probab. Comput. 15 (2006), no. 4, 523–539.

[3] Luis A. Goddyn, Michael Tarsi, and Cun-Quan Zhang, On (k,d)-colorings and fractional nowhere zero flows, Journal of Graph Theory 28 (1998), 155–161.

[4] Winfried Hochstättler and Jaroslav Nešetřil, Antisymmetric flows in matroids, Eur. J. Comb. 27 (2006), no. 7, 1129–1134.

[5] Manoel Lemos and James Oxley, On removable circuits in graphs and matroids, Journal of Graph Theory 30 (1999), 51–66.