On the Discrepancy of Combinatorial Rectangles

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

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

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 ≤ ∞.

Original languageEnglish (US)
Pages (from-to)205-215
Number of pages11
JournalRandom Structures and Algorithms
Volume21
Issue number3-4
DOIs
StatePublished - Jan 1 2002
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Keywords

  • Discrepancy
  • Probabilistic method

Fingerprint Dive into the research topics of 'On the Discrepancy of Combinatorial Rectangles'. Together they form a unique fingerprint.

  • Cite this