Hereditary discrepancies in different numbers of colors II

Benjamin Doerr; Mahmoud Fouz

doi:10.1137/090669620

Hereditary discrepancies in different numbers of colors II

Benjamin Doerr
, Mahmoud Fouz

Max-Planck-Institut fur Informatik
Universität des Saarlandes

Research output: Contribution to journal › Article › peer-review

Abstract

We bound the hereditary discrepancy of a hypergraph H in two colors in terms of its hereditary discrepancy in c colors. We show that herdisc(H, 2) ≤ Kc herdisc(H, c), where K is some absolute constant. This bound is sharp apart from the absolute constant.

Original language	English
Pages (from-to)	1205-1213
Number of pages	9
Journal	SIAM Journal on Discrete Mathematics
Volume	24
Issue number	3
DOIs	https://doi.org/10.1137/090669620
Publication status	Published - 26 Oct 2010
Externally published	Yes

Keywords

Coloring of hypergraphs
Discrepancy
Hypergraphs

Access to Document

10.1137/090669620

Cite this

@article{b99333580dc1468da87a9db155f97495,

title = "Hereditary discrepancies in different numbers of colors II",

abstract = "We bound the hereditary discrepancy of a hypergraph H in two colors in terms of its hereditary discrepancy in c colors. We show that herdisc(H, 2) ≤ Kc herdisc(H, c), where K is some absolute constant. This bound is sharp apart from the absolute constant.",

keywords = "Coloring of hypergraphs, Discrepancy, Hypergraphs",

author = "Benjamin Doerr and Mahmoud Fouz",

year = "2010",

month = oct,

day = "26",

doi = "10.1137/090669620",

language = "English",

volume = "24",

pages = "1205--1213",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Hereditary discrepancies in different numbers of colors II

AU - Doerr, Benjamin

AU - Fouz, Mahmoud

PY - 2010/10/26

Y1 - 2010/10/26

N2 - We bound the hereditary discrepancy of a hypergraph H in two colors in terms of its hereditary discrepancy in c colors. We show that herdisc(H, 2) ≤ Kc herdisc(H, c), where K is some absolute constant. This bound is sharp apart from the absolute constant.

AB - We bound the hereditary discrepancy of a hypergraph H in two colors in terms of its hereditary discrepancy in c colors. We show that herdisc(H, 2) ≤ Kc herdisc(H, c), where K is some absolute constant. This bound is sharp apart from the absolute constant.

KW - Coloring of hypergraphs

KW - Discrepancy

KW - Hypergraphs

U2 - 10.1137/090669620

DO - 10.1137/090669620

M3 - Article

AN - SCOPUS:77958091270

SN - 0895-4801

VL - 24

SP - 1205

EP - 1213

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

Hereditary discrepancies in different numbers of colors II

Abstract

Keywords

Access to Document

Fingerprint

Cite this