On small n-uniform hypergraphs with positive discrepancy

2017/06/17 by Cherkashin, Danila, Petrov, Fedor
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1706.05539

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ős and Sós 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 (snd) of n. We refine the upper bound as follows: f (n) ≤ c log snd n.

Related

• Improved Lower Bounds for Property B
• On some generalizations of the property B-problem of an n-uniform hypergraph
• On small non-uniform hypergraphs without property B
• Tight Lower Bound for Multicolor Discrepancy
• Discrepancies of perfect matchings in hypergraphs