Teoria niezależności w kombinatoryce

Independence Theory in Combinatoryics: An Introductory Account with Applications to Graphs and Transversals to podręcznik matematyki na poziomie licencjackim dotyczący teorii matroidów . Został napisany przez Victora Bryanta i Hazel Perfect i opublikowany w 1980 roku przez Chapman & Hall.

Tematy

Głównym tematem teorii niezależności w kombinatoryce jest jednoczący charakter abstrakcji, aw szczególności sposób, w jaki teoria matroidów może ujednolicić koncepcję niezależności pochodzącą z różnych dziedzin matematyki. Ma pięć rozdziałów, z których pierwszy zawiera podstawowe definicje z teorii grafów , kombinatoryki i algebry liniowej , a drugi definiuje i wprowadza matroidy , zwanych w tej książce „przestrzeniami niepodległościowymi”. Jak sugeruje nazwa, są one definiowane głównie za pomocą ich niezależnych zbiorów, ale prezentowane są również równoważności z definicjami wykorzystującymi obwody, rangę matroidów i submodułową funkcję zbioru , podobnie jak sumy, drugorzędne, obcięcia i liczby podwójne matroidów.

Rozdział trzeci dotyczy matroidów graficznych , matroidów drzew rozpinających w grafach oraz algorytmu zachłannego dla minimalnych drzew rozpinających . Rozdział czwarty zawiera materiał na temat matroidów poprzecznych , które można opisać w kategoriach dopasowań grafów dwudzielnych , oraz dodatkowy materiał na temat teorii dopasowywania i zagadnień pokrewnych, w tym twierdzenie Halla o małżeństwie , twierdzenie Mengera (równoważność między minimalnymi przekrojami i maksymalnymi zbiorami rozłącznych ścieżek w grafach ), Kwadraty łacińskie i gammoidy . Ostatni rozdział dotyczy reprezentacji matroidowych wykorzystujących niezależność liniową w przestrzeniach wektorowych , oznaczonych jako dodatek i przedstawionych z mniejszą liczbą dowodów.

Zawiera wiele ćwiczeń o różnym stopniu trudności, z podpowiedziami i rozwiązaniami.

Publiczność i odbiór

Poziom tekstu jest odpowiedni dla kursów dla zaawansowanych studentów studiów licencjackich lub magisterskich, gdzie wymagana jest tylko podstawowa algebra liniowa, i obejmuje materiał na bardziej przystępnym i ogólnym poziomie niż inne teksty z teorii matroidów. Chociaż recenzent Dominic Welsh nie zgadza się z pominięciem w książce powiązanego tematu krat geometrycznych , nazywa ją „idealnym tekstem na kurs licencjacki z teorii kombinatorycznej”. Michael J. Ganley podobnie nazywa to „bardzo dobrym wprowadzeniem do dość trudnego tematu”.

Jednak recenzent W. Dörfler skarży się, że książka zawiera niewystarczające omówienie praktycznych zastosowań i brakuje odpowiedniej bibliografii. Innym zarzutem Bernharda Korte jest to, że tytuł książki jest mylący: „przestrzenie niezależności” często odnoszą się bardziej ogólnie do abstrakcyjnych uproszczonych kompleksów , podczas gdy książka koncentruje się bardziej konkretnie na matroidach. Korte powtarza również skargi innych recenzentów na brak omówienia zastosowań optymalizacji kombinatorycznej i powiązań z teorią sieci.