The smallest n-uniform hypergraph with positive discrepancy (Q1093653)

Let \(H=(X,E)\) denote the hypergraph with vertex set X and edge set E. We say that H is n-uniform if each edge contains exactly n-vertices. The discrepancy of a two coloring of the vertices of H is the maximum over all edges of the difference between the numbers of vertices of that edge in the two color class. The discrepancy of the hypergraph H is the minimum discrepancy over all two colorings of the vertex set of H. Thus, for example a hypergraph H has discrepancy zero if it admits a two coloring of its vertices which colors exactly half of the vertices of each edge with one color and half with the other. Let f(n) be the fewest number edges in an n-uniform hypergraph which has positive discrepancy. Obviously \(f(n)=1\) for n odd. For n even, the authors prove several results. For example, if \(n=4k\), then there exist constants \(c_ 1\) and \(c_ 2\) such that: \[ \frac{c_ 1\log (snd(2k))}{\log \log (snd(2k))}\leq f(4k)\leq \frac{c_ 2\log^ 3(snd(2k))}{\log \log (snd(2k))}, \] where snd(x) is the least positive integer that does not divide x.