Twierdzenie Dilwortha – twierdzenie kombinatoryczne o charakterze minimaksowym dotyczące struktury zbiorów częściowo uporządkowanych. Zgodnie z twierdzeniem Dilwortha w dowolnym skończonym zbiorze częściowo uporządkowanym maksymalna liczność antyłańcucha jest równa minimalnej liczbie łańcuchów, które pokrywają ten zbiór.
Twierdzenie to zostało sformułowane przez amerykańskiego matematyka Roberta Dilwortha, który opublikował jego dowód w 1950 roku.
Twierdzenie
Niech będzie relacją częściowego porządku na zbiorze . Łańcuchem nazywa się zbiór w którym każde dwa elementy są porównywalne, czyli zbiór jest uporządkowany liniowo przez relację Z kolei podzbiór w którym każde dwa elementy są nieporównywalne, nazywa się antyłańcuchem. Minimalna liczba łańcuchów, które pokrywają zbiór to najmniejsza taka liczba całkowita że istnieją łańcuchy dla których zachodzi .
Twierdzenie Dilwortha orzeka, że jeśli zbiór jest skończony, to maksymalna liczność (moc) antyłańcucha jest równa minimalnej liczbie łańcuchów, które pokrywają zbiór . Twierdzenie to jest prawdziwe również, gdy zbiór jest nieskończony, ale maksymalna moc antyłańcucha w tym zbiorze jest skończona.
Dowód Przedstawiony tu dowód indukcyjny podał Helge Tverberg w 1967 roku.