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

3 Scopus citations

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 (US)
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
State	Published - 2002
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
General Mathematics
Computer Graphics and Computer-Aided Design
Applied Mathematics

Keywords

Discrepancy
Probabilistic method

Access to Document

10.1002/rsa.10055

Cite this

@article{88f48c61271b483da378ccd3fef127a5,

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",

doi = "10.1002/rsa.10055",

language = "English (US)",

volume = "21",

pages = "205--215",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "John Wiley and Sons Ltd",

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

Y1 - 2002

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

UR - http://www.scopus.com/inward/record.url?scp=0036441781&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036441781&partnerID=8YFLogxK

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

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this