pith. sign in

arxiv: 1706.05539 · v2 · pith:DUFBDARLnew · submitted 2017-06-17 · 🧮 math.CO

On small n-uniform hypergraphs with positive discrepancy

classification 🧮 math.CO
keywords discrepancybluehypergraphmboxnumberuniformupperalon
0
0 comments X
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.