Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
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)≤clogsndn.
Язык оригинала | английский |
---|---|
Страницы (с-по) | 353-359 |
Число страниц | 7 |
Журнал | Journal of Combinatorial Theory. Series B |
Том | 139 |
DOI | |
Состояние | Опубликовано - 1 ноя 2019 |
ID: 41502534