Other formats:
BibTeX
LaTeX
RIS
@article{637585,
author = {Hliněný, Petr and Hochstattler, Winfried and Goddyn, Luis},
article_location = {UK},
article_number = {4},
keywords = {orientable matroid; chromatic number; wiring diagram; balanced signing},
language = {eng},
issn = {0963-5483},
journal = {Combin. Prob. Computing},
title = {Balanced Signings and the Chromatic Number of Oriented Matroids},
url = {http://dx.doi.org/10.1017/S096354830500742X},
volume = {15},
year = {2006}
}
TY - JOUR
ID - 637585
AU - Hliněný, Petr - Hochstattler, Winfried - Goddyn, Luis
PY - 2006
TI - Balanced Signings and the Chromatic Number of Oriented Matroids
JF - Combin. Prob. Computing
VL - 15
IS - 4
SP - 523
EP - 523
PB - Cambridge Univ. Press
SN - 09635483
KW - orientable matroid
KW - chromatic number
KW - wiring diagram
KW - balanced signing
UR - http://dx.doi.org/10.1017/S096354830500742X
N2 - 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$.
ER -
HLINĚNÝ, Petr, Winfried HOCHSTATTLER and Luis GODDYN. Balanced Signings and the Chromatic Number of Oriented Matroids. \textit{Combin. Prob. Computing}. UK: Cambridge Univ. Press, 2006, vol.~15, No~4, p.~523-539. ISSN~0963-5483.
|
