|
Session 27. Probabilistic and Extremal Combinatorics
|
Improved algorithms for colorings of simple hypergraphs |
Jakub Kozik, Jagiellonian University, Poland
|
The talk is based on the joint work with Dmitry Shabanov (Lomonosov Moscow State University, Moscow Russia)
|
|
|
The famous Lovász Local Lemma was derived in the paper of P. Erdős and Lovász to prove that any \(n\)-uniform non-\(r\)-colorable hypergraph \(H\) has maximum edge degree at least
\[
\Delta(H)\geqslant \frac 14 r^{n-1}.
\]
A long series of papers is devoted to the improvement of this classical result for different classes of uniform hypergraphs.
In our work we deal with colorings of simple hypergraphs, i.e. hypergraphs in which every two distinct edges share at most one vertex.
By using a multipass random recoloring we show that any simple \(n\)-uniform non-\(r\)-colorable hypergraph \(H\) has maximum edge degree at least
\[
\Delta(H)\geqslant c\cdot n \, r^{n-1},
\]
where \(c>0\) is an absolute constant.
Furter applications of our technique yields an improvements of Szabo's lower bounds for Van der Waerden numbers.
We also extend the main result to \(b\)-simple hypergraphs.
|
|
| Print version |
|
