|
Session 27. Probabilistic and Extremal Combinatorics
|
Harmonious Coloring of Hypergraphs |
Bart\l omiej Bosek, Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Poland
|
The talk is based on the joint work with Sebastian Czerwiński (University of Zielona Góra), Jarosław
Grytczuk (Jagiellonian University,), and Paweł Rzążewski (Warsaw University of Technology)
|
|
|
A harmonious coloring of a hypergraph is a coloring of its vertices such that
- two different vertices contained in common hyperedge have different colors,
- sets of colors of all vertices from two different hyperedges are different sets.
We prove that every \(k\)-uniform hypergraph, with maximal degree \(\Delta\) and with \(m\) hyperedges, is harmoniously
colored by
\[
O\left({ \frac{k}{k-1}\sqrt[k]{\left({k-1}\right)k! \Delta m} + \Delta^2 + \left({k-1}\right)\Delta }\right)
\]
colors.
This is almost tight, since the obvious lower bound is of order \(\Omega ( \sqrt[k]{k!m})\).
The proof uses entropy compression argument - a novel method inspired by the algorithmic version of the
Lovász Local Lemma due to Moser and Tardos.
We will also discuss several related problems, for instance legitimate coloring of hypergraphs, strong
coloring of graphs, etc.
|
|
| Print version |
|
