The smallestn-uniform hypergraph with positive discrepancy |
| |
Authors: | N Alon D J Kleitman C Pomerance M Saks P Seymour |
| |
Institution: | 1. Tel Aviv University Ramat Aviv, 69978, Tel Aviv, Israel 2. Massachusetts Institute of Technology, 02139, Cambridge, MA, USA 3. Bell Communications Research, 07960, Morristown, NJ, USA
|
| |
Abstract: | A two-coloring of the verticesX of the hypergraphH=(X, ε) by red and blue hasdiscrepancy d ifd is the largest difference between the number of red and blue points in any edge. A two-coloring is an equipartition ofH if it has discrepancy 0, i.e., every edge is exactly half red and half blue. Letf(n) be the fewest number of edges in ann-uniform hypergraph (all edges have sizen) having positive discrepancy. Erd?s and Sós asked: isf(n) unbounded? We answer this question in the affirmative and show that there exist constantsc 1 andc 2 such that $$\frac{{c_1 \log (snd(n/2))}}{{\log \log (snd(n/2))}} \leqq f(n) \leqq c_2 \frac{{\log ^3 (snd(n/2))}}{{\log \log (snd(n/2))}}$$ where snd(x) is the least positive integer that does not dividex. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|