On the Discrepancy of Combinatorial Rectangles

Noga Alon; Benjamin Doerr; Tomasz Łuczak; Tomasz Schoen

doi:10.1002/rsa.10055

On the Discrepancy of Combinatorial Rectangles

Noga Alon, Benjamin Doerr, Tomasz Łuczak, Tomasz Schoen

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

Abstract

Let ℬ_n^d denote the family which consists of all subsets S₁ × ... × S_d, where S_i, ⊆ [n], and S_i ≠ Ø, for i = 1, ..., d. We compute the L₂-discrepancy of ℬ_n^d and give estimates for the L_p-discrepancy of ℬ_n^d for 1 ≤ p ≤ ∞.

Original language	English
Pages (from-to)	205-215
Number of pages	11
Journal	Random Structures and Algorithms
Volume	21
Issue number	3-4
DOIs	https://doi.org/10.1002/rsa.10055
Publication status	Published - 1 Jan 2002
Externally published	Yes

Keywords

Discrepancy
Probabilistic method

Access to Document

10.1002/rsa.10055

Cite this

@article{d6af346070c34071837d402fe141ffe1,

title = "On the Discrepancy of Combinatorial Rectangles",

abstract = "Let ℬnd denote the family which consists of all subsets S1 × ... × Sd, where Si, ⊆ [n], and Si ≠ {\O}, for i = 1, ..., d. We compute the L2-discrepancy of ℬnd and give estimates for the Lp-discrepancy of ℬnd for 1 ≤ p ≤ ∞.",

keywords = "Discrepancy, Probabilistic method",

author = "Noga Alon and Benjamin Doerr and Tomasz {\L}uczak and Tomasz Schoen",

year = "2002",

month = jan,

day = "1",

doi = "10.1002/rsa.10055",

language = "English",

volume = "21",

pages = "205--215",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

number = "3-4",

}

TY - JOUR

T1 - On the Discrepancy of Combinatorial Rectangles

AU - Alon, Noga

AU - Doerr, Benjamin

AU - Łuczak, Tomasz

AU - Schoen, Tomasz

PY - 2002/1/1

Y1 - 2002/1/1

N2 - Let ℬnd denote the family which consists of all subsets S1 × ... × Sd, where Si, ⊆ [n], and Si ≠ Ø, for i = 1, ..., d. We compute the L2-discrepancy of ℬnd and give estimates for the Lp-discrepancy of ℬnd for 1 ≤ p ≤ ∞.

AB - Let ℬnd denote the family which consists of all subsets S1 × ... × Sd, where Si, ⊆ [n], and Si ≠ Ø, for i = 1, ..., d. We compute the L2-discrepancy of ℬnd and give estimates for the Lp-discrepancy of ℬnd for 1 ≤ p ≤ ∞.

KW - Discrepancy

KW - Probabilistic method

U2 - 10.1002/rsa.10055

DO - 10.1002/rsa.10055

M3 - Article

AN - SCOPUS:0036441781

SN - 1042-9832

VL - 21

SP - 205

EP - 215

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 3-4

ER -

On the Discrepancy of Combinatorial Rectangles

Abstract

Keywords

Access to Document

Fingerprint

Cite this