Coloring t-dimensional m-Boxes

Geir Agnarsson; Benjamin Doerr; Tomasz Schoen

doi:10.1016/S0012-365X(00)00180-1

Coloring t-dimensional m-Boxes

Geir Agnarsson
, Benjamin Doerr
, Tomasz Schoen

University of Iceland
Christian-Albrechts-University Kiel
Adam Mickiewicz University/Faculty of Biology

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

Abstract

Call the set S₁ × ⋯ × S_t t-dimensional m-box if |S_i| = m for every i = 1,...,t. Let R_t(m, r) be the smallest integer R such that for every r-coloring of t-fold cartesian product of [R], one can find a monochromatic t-dimensional m-box. We give a lower and an upper bound for R_t(m, r). We also consider the discrepancy problem connected to this set-system. Among other bounds, we prove that the discrepancy of the hypergraph of all one-dimensional m-boxes in [R] × [R] is equal to θ(R^3/2) for m a constant fraction (less than 1/2) of R.

Original language	English
Pages (from-to)	21-33
Number of pages	13
Journal	Discrete Mathematics
Volume	226
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(00)00180-1
Publication status	Published - 1 Jan 2001
Externally published	Yes

Keywords

Box
Discrepancy
Grid
Ramsey theory

Access to Document

10.1016/S0012-365X(00)00180-1

Cite this

@article{f84aeb024740468e9e8c0b29914fc399,

title = "Coloring t-dimensional m-Boxes",

abstract = "Call the set S1 × ⋯ × St t-dimensional m-box if |Si| = m for every i = 1,...,t. Let Rt(m, r) be the smallest integer R such that for every r-coloring of t-fold cartesian product of [R], one can find a monochromatic t-dimensional m-box. We give a lower and an upper bound for Rt(m, r). We also consider the discrepancy problem connected to this set-system. Among other bounds, we prove that the discrepancy of the hypergraph of all one-dimensional m-boxes in [R] × [R] is equal to θ(R3/2) for m a constant fraction (less than 1/2) of R.",

keywords = "Box, Discrepancy, Grid, Ramsey theory",

author = "Geir Agnarsson and Benjamin Doerr and Tomasz Schoen",

year = "2001",

month = jan,

day = "1",

doi = "10.1016/S0012-365X(00)00180-1",

language = "English",

volume = "226",

pages = "21--33",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "1-3",

}

TY - JOUR

T1 - Coloring t-dimensional m-Boxes

AU - Agnarsson, Geir

AU - Doerr, Benjamin

AU - Schoen, Tomasz

PY - 2001/1/1

Y1 - 2001/1/1

N2 - Call the set S1 × ⋯ × St t-dimensional m-box if |Si| = m for every i = 1,...,t. Let Rt(m, r) be the smallest integer R such that for every r-coloring of t-fold cartesian product of [R], one can find a monochromatic t-dimensional m-box. We give a lower and an upper bound for Rt(m, r). We also consider the discrepancy problem connected to this set-system. Among other bounds, we prove that the discrepancy of the hypergraph of all one-dimensional m-boxes in [R] × [R] is equal to θ(R3/2) for m a constant fraction (less than 1/2) of R.

AB - Call the set S1 × ⋯ × St t-dimensional m-box if |Si| = m for every i = 1,...,t. Let Rt(m, r) be the smallest integer R such that for every r-coloring of t-fold cartesian product of [R], one can find a monochromatic t-dimensional m-box. We give a lower and an upper bound for Rt(m, r). We also consider the discrepancy problem connected to this set-system. Among other bounds, we prove that the discrepancy of the hypergraph of all one-dimensional m-boxes in [R] × [R] is equal to θ(R3/2) for m a constant fraction (less than 1/2) of R.

KW - Box

KW - Discrepancy

KW - Grid

KW - Ramsey theory

U2 - 10.1016/S0012-365X(00)00180-1

DO - 10.1016/S0012-365X(00)00180-1

M3 - Article

AN - SCOPUS:0242337567

SN - 0012-365X

VL - 226

SP - 21

EP - 33

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Coloring t-dimensional m-Boxes

Abstract

Keywords

Access to Document

Fingerprint

Cite this