An \(L_p\) version of the Beck-Fiala conjecture
type: Item
instance of: scholarly article
title: An \(L_p\) version of the Beck-Fiala conjecture
zbMATH Open document ID: 0923.05002
published in: European Journal of Combinatorics
publication date: 1999-07-01T00:00:00Z
review text: \textit{J. Beck} and \textit{P. Fiala} [Discrete Appl. Math. 3, 1--8 (1981; Zbl 0473.05046)] conjectured that for any set system \({\mathcal S}\) of maximum degree \(t\) on a finite ground set \(X\), a coloring \(\chi:X\to\{-1, +1\}\) exists such that \(|\chi(S) |=O(\sqrt t)\) holds for all \(S\in {\mathcal S}\), where \(\chi(S)=\sum_{x\in S}\chi(x)\). The author proves the weaker statement, namely that for any fixed \(p\geq 1\), a coloring exists such that the \(p\)-th degree average of \(|\chi(S)|\) over \(S\in{\mathcal S}\) is \(O(\sqrt t)\).
reviewed by: Robert F. Tichy
Mathematics Subject Classification ID: 05D05
Mathematics Subject Classification ID: 11K38
zbMATH DE Number: 1212319
zbMATH Keywords: Beck-Fiala conjecture
zbMATH Keywords: set system
zbMATH Keywords: coloring
author: Jiří Matoušek
MaRDI profile type: Publication
full work available at URL: eujc.1997.0162
OpenAlex ID: W2077872360
Wikidata QID: Q123148082
DOI: 10.1006/EUJC.1997.0162
Recommended article: On a generalization of the Beiter conjecture
Recommended article: A note on the Beck-Fiala theorem
Recommended article: On the Beck-Fiala theorem
Recommended article: Beck's conjecture and multiplicative lattices
Recommended article: On a conjecture of A. Bezdek
Recommended article: Q3676259
Recommended article: An Improvement of the Beck–Fiala Theorem
Recommended article: A relative version of the Beilinson-Hodge conjecture
Recommended article: Q4205484
Recommended article: An \(L^ p\)-version of a theorem of D. A. Raikov
description: scientific article; zbMATH DE number 1212319