The smallest n-uniform hypergraph with positive discrepancy

N. Alon, D. J. Kleitman, C. Pomerance, M. Saks, P. Seymour

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

A two-coloring of the vertices X of the hypergraph H=(X, ε) by red and blue has discrepancy d if d is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition of H if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Let f(n) be the fewest number of edges in an n-uniform hypergraph (all edges have size n) having positive discrepancy. Erdo{combining double acute accent}s and Sós asked: is f(n) unbounded? We answer this question in the affirmative and show that there exist constants c 1 and c 2 such that {Mathematical expression} where snd(x) is the least positive integer that does not divide x.

Original languageEnglish (US)
Pages (from-to)151-160
Number of pages10
JournalCombinatorica
Volume7
Issue number2
DOIs
StatePublished - Jun 1 1987
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'The smallest n-uniform hypergraph with positive discrepancy'. Together they form a unique fingerprint.

  • Cite this