摘要：Let â"< be a t-regular hypergraph on n vertices and m edges. Let M be the m Ã- n incidence matrix of â"< and let us denote λ = max_{v â^^ ðY^âY,} 1/â-vâ- â-Mvâ-. We show that the discrepancy of â"< is O(â^St + λ). As a corollary, this gives us that for every t, the discrepancy of a random t-regular hypergraph with n vertices and m ⥠n edges is almost surely O(â^St) as n grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.
