Balanced Signings and the Chromatic Number of Oriented Matroids

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F06%3A00016918" target="_blank" >RIV/00216224:14330/06:00016918 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Balanced Signings and the Chromatic Number of Oriented Matroids
Original language description
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^2ln(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$.
Czech name
Vyvážená znaménka a barevnost orientovaných matroidů
Czech description
Zabýváme se problémem reorientace orientovatelného matroidu tak, aby všechny kocyckly byly co nejvíce balancované. Geometricky toto odpovídá omezení diskrepancí nad všemi Radonovými rozklady závislé množiny vektorů. Pro grafy to znamená omezení barevnosti funkcí jeho koranku.

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)