A two-coloring of the vertices V of the hypergraph H=(V,E) by red and blue has discrepancy d if d is the largest difference between the number of red and blue points in any edge. Let f(n) be the fewest number of edges in an n-uniform hypergraph without a coloring with discrepancy 0. Erdős and Sós asked: is f(n) unbounded? N. Alon, D. J. Kleitman, C. Pomerance, M. Saks and P. Seymour [1] proved upper and lower bounds in terms of the smallest non-divisor (snd) of n (see (1)). We refine the upper bound as follows: f(n)≤clog⁡sndn.

Original languageEnglish
Pages (from-to)353-359
Number of pages7
JournalJournal of Combinatorial Theory. Series B
Volume139
DOIs
StatePublished - 1 Nov 2019

    Research areas

  • Hypergraph colorings, Hypergraph discrepancy, Prescribed matrix determinant

    Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

ID: 41502534