The smallest n-uniform hypergraph with positive discrepancy
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.
- ``Integer-making theorems
- Balanced two-colorings of finite sets in the square. I
- Discrepancy of set-systems and matrices
- scientific article; zbMATH DE number 3238721 (Why is no real title available?)
- ON THE ‘HIGH-INDICES THEOREM’ OF HARDY AND LITTLEWOOD
- Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory
- Six Standard Deviations Suffice
- Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory
- Choosability and fractional chromatic numbers
- Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
- Path choosability of planar graphs
- On small \(n\)-uniform hypergraphs with positive discrepancy
- Discrepancy of random graphs and hypergraphs
- Partial Colorings of Unimodular Hypergraphs
- On non-adaptive majority problems of large query size
- Extremal problems in hypergraph colourings
- Discrepancy in graphs and hypergraphs
This page was built for publication: The smallest n-uniform hypergraph with positive discrepancy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1093653)
