Fractional flow number of a matroid
by
Petr Hliněný
School of Mathematical and Computing Sciences, Victoria University
Coauthors: Luis Goddyn, Winfried Hochstättler

The circular chromatic number of a graph, introduced by Vince as a star chromatic number, is a non-negative rational number whose ceiling is the usual chromatic number. Goddyn, Tarsi and Zhang introduced the matroid dual \phi ^* (G) of this parameter, which we call the fractional flow number. They proved that the fractional flow number of a graph G can be expressed as

\phi * (G)= min [G\vec]    max B in B    \frac|B| min {|B+|, |B-|}

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 this equation 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. A restricted version of this question may also be viewed as a discrepancy-type problem for an arrangement of hyperplanes.

Using a probabilistic argument, we prove:

Theorem. There exists a function f such that the fractional flow number of a coloop-free oriented matroid of rank k is at most f(k). In particular, f(3) <= 37 and f(k) <= 8(r+1)²ln2(r+1).

Date received: October 29, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafn-21.