Research output: Contribution to journal › Article › peer-review
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.
Original language | English |
---|---|
Pages (from-to) | 353-359 |
Number of pages | 7 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 139 |
DOIs | |
State | Published - 1 Nov 2019 |
ID: 41502534