|
Sauer i Spencer udowodnili, że dwa grafy  i  rzędu n są pakowalne, gdy
 .
W dowodzie użyli prostego algorytmu, który w każdym kolejnym kroku polepsza bieżące pakowanie próbne przez proste zamiany i
po skończonej ilości kroków daje pakowanie właściwe. Dzięki podobnej argumentacji Rodl, Ruciński oraz
Taraz udowodnili twierdzenie o pakowaniu k-jednolitych hipergrafów, o którym będzie mowa na seminarium.
|
|