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