Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-14T03:59:11.342Z Has data issue: false hasContentIssue false

Balanced Signings and the Chromatic Number of Oriented Matroids

Published online by Cambridge University Press:  07 June 2006

LUIS GODDYN
Affiliation:
Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada (e-mail: goddyn@math.sfu.ca)
PETR HLINĚNÝ
Affiliation:
Faculty of Informatics, Masaryk University, Botanická 68a, 60200 Brno, Czech Republic (e-mail: hlineny@fi.muni.cz)
WINFRIED HOCHSTÄTTLER
Affiliation:
Department of Mathematics, Fern Universität in Hagen, Hagen, Germany (e-mail: Winfried.Hochstaettler@fernuni-hagen.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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^- \neq \emptyset$. We show that, for some reorientation, every signed cocircuit satisfies \[1/f(r) \leq |B^+|/|B^-| \leq f(r)\], where $f(r) \leq 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$.

Information

Type
Paper
Copyright
2006 Cambridge University Press