DOI

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.

Язык оригиналаанглийский
Страницы (с-по)353-359
Число страниц7
ЖурналJournal of Combinatorial Theory. Series B
Том139
DOI
СостояниеОпубликовано - 1 ноя 2019

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Дискретная математика и комбинаторика
  • Математика и теория расчета

ID: 41502534