Komputerowa weryfikacja dwukolorowalności liniowych k-jednostajnych hipergrafów

Hipergraf nazywamy dwukolorowalnym wtedy i tylko wtedy, gdy można pokolorować jego wierzchołki tak, by żadna hiperkrawędź nie była monochromatyczna. W tej pracy skupiamy się na problemie dwukolorowania dla pewnej podklasy k-jednostajnych liniowych hipergrafów. Mianowicie, hipergrafów, które spełniają następującą własność: dla każdego podzbioru wierzchołków V rozmiar zbioru hiperkrawędzi indukowanych przez V jest co najwyżej |V|. Znane są kontrprzykłady, które pokazują, że w wyżej wymienionej klasie hipergrafy 2-jednostajne i 3-jednostajne nie są dwukolorowalne. Nie wiadomo jednak, czy takie kontrprzykłady istnieją w przypadku k-jednostajnych hipergrafów dla k >=4. W tej pracy dokonaliśmy postępu w kierunku rozwiązania tego problemu przy użyciu podejścia komputerowego. Udało nam się potwierdzić, że obecnie jedyny znany kontrprzykład dla 3-jednostajnych hipergrafów jest rzeczywiście najmniejszy. Co ważniejsze, znaleźliśmy inne większe kontrprzykłady w przypadku 3-jednostajnych hipergrafów, które nie były wcześniej znane. Ponadto potwierdziliśmy, że każdy 4-jednostajny hipergraf o maksymalnie 17 wierzchołkach jest dwukolorowalny.

Hypergraph is called 2-colorable if and only if it is possible to color its vertices such that no hyperedge is monochromatic. In this work we focus on the problem of 2-colorability for a subclass of k-uniform linear hypergraphs. Namely, hypergraphs that satisfy the following property: for every subset of vertices V the size of a set of hyperedges induced by V is at most |V|. There are known counterexamples which show that in the above-mentioned class 2-uniform and 3-uniform hypergraphs are not 2-colorable. But it is still unknown whether such counterexamples exist in the case of k-uniform hypergraphs for k >=4. In this paper we make progress towards resolving this problem using a computational approach. We were able to confirm that the currently only known counterexample for 3-uniform hypergraphs is indeed the smallest. More importantly, we found different bigger counterexamples in the case of 3-uniform hypergraphs which were not previously known. Furthermore, we confirmed that every 4-uniform hypergraph with up to 17 vertices is 2-colorable.