On small n-uniform hypergraphs with positive discrepancy
classification
🧮 math.CO
keywords
discrepancybluehypergraphmboxnumberuniformupperalon
read the original abstract
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\H{o}s and S\'os asked: is $f(n)$ unbounded? N. Alon, D. J. Kleitman, C. Pomerance, M. Saks and P. Seymour proved upper and lower bounds in terms of the smallest non-divisor ($\mbox{snd}$) of $n$. We refine the upper bound as follows: $$f (n) \leq c \log \mbox{snd}\ {n}.$$
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.