Algebraic Tools in Combinatorial Geometry and Topology

Abstract

In this thesis we study combinatorial problems through the lenses of the exterior alge- bra. This algebra is a natural object to model set systems as well as simplicial complexes. Moreover, it is possible to translate the classical operations from the combinatorial set- ting to the setting of exterior algebra. For example, set intersection and the classical boundary map from topology. Often this point of view makes it possible to translate the combinatorial problem to a problem regarding the dimension of certain vector space. The latter one might turn up to be easier since we can study the dimension of a vector space with linear maps. We follow such approach in this thesis. In the first part we study the weak saturation problem introduced by Bollobás in the 60's. This problem consists in, given a host graph F and a pattern graph H, to determine the minimum number of infected edges of F one has to start with in order for the infection to spread, according to the pattern H, to the whole host graph F. We study this problem when the host and the pattern are complete uniform multipartite hypergraphs. Next, we work on a generalization of a theorem by Helly regarding intersecting pat- terns of convex sets. Concretely, given a finite family of convex sets in Rd partitioned into d + 1 colors classes such that a...

V této práci se zabýváme kombinatorickými problémy optikou Grassmanovy alge- bry. Tato algebra je přirozenou matematickou strukturou pro modelování množinových systémů i simpliciálních komplexů. Umožňuje navíc převést operace z kombinatorických struktur do Grassmanovy algebry. Například operace jako množinový průnik nebo stan- dardní hraniční operátor z topologie. To nám často umožňují převést kombinatorický problém na problém týkající se dimenze určitého vektorového prostoru, což se může uká- zat jako jednodušší přístup, protože poté můžeme zkoumat dimenzi vektorového prostoru pomocí lineárních zobrazení. Takový přístup uplatňujeme i v této práci. V první části zkoumáme problém slabé saturace, který zavedl Bollobás v 60. letech. Jedná se o následující problém. Pro zadaný "hostitelský" graf F a "vzorový" graf H je potřeba určit minimální počet "nakažených" hran grafu F, se kterými je třeba začít, aby se infekce rozšířila na celý hostitelský graf F podle vzorového grafu H. Konkrétně nás zajímá případ, kdy hostitelské i vzorové grafy jsou úplné uniformní multipartitní hypergrafy. Dále se zabýváme zobecněním Hellyho věty, která se týká průsečíkových struktur kon- vexních množin. Konkrétně se ptáme na následující otázku. Je-li zadán konečný systém konvexních množin v Rd rozdělených do d+1 tříd barev tak, že...