Andrzej Żak

O maksymalnych niehamiltonowskich hipergrafach

Mówimy, że hipergraf H jest maksymalnie niehamiltonowski, jeśli $H$ nie ma cyklu Hamiltona, ale dodanie do H dowolnej dodatkowej hiperkrawędzi powoduje powstanie cyklu Hamiltona w H. Interesuje nas najmniejsza liczba sat$_k(n,C_n)$ hiperkrawędzi jaką może mieć maksymalnie niehamiltonowski k-jednolity hipergraf rzędu n. Problem jest rozwiązany dla $k=2$ (czyli dla grafów). W przypadku $k\geq 3$ udało się uzyskać tylko pewne ograniczenia. Wyniki, które przedstawię, zostały osiągnięte wspólnie z G.Y. Katoną i A. Dudek.

Serdecznie zapraszamy wszystkich chętnych !