The smallest n-uniform hypergraph with positive discrepancy
type: Item
instance of: scholarly article
title: The smallest n-uniform hypergraph with positive discrepancy
zbMATH Open document ID: 0629.05053
DOI: 10.1007/BF02579446
author: Paul Seymour
author: Noga Alon
author: Daniel J. Kleitman
author: Carl Pomerance
author: Michael Saks
published in: Combinatorica
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4023334
zbMATH Keywords: vertex coloring
zbMATH Keywords: hypergraph
zbMATH Keywords: discrepancy
zbMATH Keywords: two coloring
reviewed by: Jack E. Graver
MaRDI profile type: Publication
cites work: Regular hypergraphs, Gordon's lemma, Steinitz' lemma and invariant theory
cites work: Balanced two-colorings of finite sets in the square. I
cites work: ``Integer-making'' theorems
cites work: ON THE ‘HIGH-INDICES THEOREM’ OF HARDY AND LITTLEWOOD
cites work: Discrepancy of set-systems and matrices
cites work: Q5526189
cites work: Six Standard Deviations Suffice
description: scientific article; zbMATH DE number 4023334