|
|
Algebraic Tools in Combinatorial Geometry and Topology
Bulavka, Denys ; Tancer, Martin (advisor) ; Benedetti, Bruno (referee) ; Holmsen, Andreas (referee)
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...
|
guest ::
