Vyvážená znaménka a barevnost orientovaných matroidů

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Balanced Signings and the Chromatic Number of Oriented Matroids

Popis výsledku v původním jazyce

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$.

Název v anglickém jazyce

Balanced Signings and the Chromatic Number of Oriented Matroids

Popis výsledku anglicky

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$.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2006

Kód důvěrnosti údajů

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

Název periodika

Combin. Prob. Computing

ISSN

0963-5483

e-ISSN

—

Svazek periodika

15

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

17

Strana od-do

523

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—