|
Celem referatu jest przedstawienie pewnego wyniku dotyczącego
pakowania hipergrafów. Znany jest wynik pakowania dowolnego hipergrafu w swoje dopełnienie: ze względu na hipergrafy 1-jednorodne, ograniczenie rozmiaru pakowalnego hipergrafu nie
może być lepsze niż
 , gdzie n jest rzędem hipergrafu. Okazuje się, że jeśli rozważymy hipergraf
bez singletonów i ich dopełnień, to jego pakowanie istnieje, o ile
rozmiar jest co najwyżej n - 2. Zatem i tym razem hipergrafy
jednorodne wyznaczają ograniczenie rozmiaru.
|
|