On the chromatic number of set systems (Q2748418)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the chromatic number of set systems |
scientific article; zbMATH DE number 1659408
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the chromatic number of set systems |
scientific article; zbMATH DE number 1659408 |
Statements
On the chromatic number of set systems (English)
0 references
10 February 2002
0 references
extremal set theory
0 references
uniform hypergraphs
0 references
property B
0 references
An \((r,l)\) system is an \(r\)-uniform hypergraph in which every set of \(l\) vertices lies in at most one edge. The problem is: what is the minimum number of edges in an \((r,l)\)-system that is not \(k\)-colourable. This question in the case of \(l=2\) is due to Paul Erdős and L. Lovász. This paper gives an essentially identical lower and upper bound (up to constants) for this minimum. The proofs are probabilistic.
0 references
