Discrete methods in computer science - Cooper, Jacob (2022)
V této disertační práci je předloženo řešení tří otevřených problémů na rozhraní kombinatoriky a teoretické informatiky. Řešení všech tří problémů jsou založena na nových postupech a metodách, u kterých předpokládáme další využití v oblasti kombinatoriky a teoretické informatiky. Konkrétně vyvineme nové metody pro vnořování hypergrafů do hypergrafů s pozitivní uniformní hranovou hustotou a použijeme tyto metody pro vyřešení otevřeného problému o uniformní turánovského hustotě hypergrafů formulovaného C. Reiherem. Druhý problém, jehož řešení předkládáme, je vyřešení otázky F. Garbeho a kol. o charakterizaci kvazináhodných latinských čtverců, které je založeno na analytických metodách pro studium asymptotických vlastností kombinatorických objektů. Třetí problém patří do oblasti parametrizované složitosti. Navrhneme algoritmus pro hledání rozkladů matroidů a použijeme jej pro návrh efektivních parametrizovaných algoritmů pro problém celočíselného programování, jejichž vstupy mají skrytou