67 citations · 244 across the 17 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.DS2021★ 1 cited
Local Computation Algorithms for Coloring of Uniform Hypergraphs
Andrzej Dorobisz, Jakub Kozik
We present a progress on local computation algorithms for two coloring of -uniform hypergraphs. We focus on instances that satisfy strengthened assumption of Local Lemma of the…
math.CO2021
Random hypergraphs and property B
Lech Duraj, Jakub Kozik, Dmitry Shabanov
In 1964 Erdős proved that $(1+\oh{1})) \frac{\eul \ln(2)}{4} k^2 2^{k}$ edges are sufficient to build a -graph which is not two colorable. To this day, it is not known whether t…
cs.DM2021
Improving Gebauer's construction of 3-chromatic hypergraphs with few edges
Jakub Kozik
In 1964 Erdős proved, by randomized construction, that the minimum number of edges in a -graph that is not two colorable is . To this day, it is not known whether…