Let G be a finite graph with vertex set V and edge set E. A graph complex on G is an abstract simplicial complex consisting of subsets of E. In particular, we may interpret such a complex as a family of subgraphs of G. The subject of this thesis is the topology of graph complexes, the emphasis being placed on homology, homotopy type, connectivity degree, Cohen-Macaulayness, and Euler characteristic. We are particularly interested in the case that G is the complete graph on V. Monotone graph properties are complexes on such a graph satisfying the additional condition that they are invariant under permutations of V. Some well-studied monotone graph properties that we discuss in this thesis are complexes of matchings, forests, bipartite graphs, disconnected graphs, and not 2-connected graphs. We present new results about several other monotone graph properties, including complexes of not 3-connected graphs and graphs not coverable by p vertices. Imagining the vertices as the corners of a regular polygon, we obtain another important class consisting of those graph complexes that are invariant under the natural action of the dihedral group on this polygon. The most famous example is the associahedron, whose faces are graphs without crossings inside the polygon. Restricting to matchings, forests, or bipartite graphs, we obtain other interesting complexes of noncrossing graphs. We also examine a certain "dihedral" variant of connectivity. The third class to be examined is the class of digraph complexes. Some well-studied examples are complexes of acyclic digraphs and not strongly connected digraphs. We present new results about a few other digraph complexes, including complexes of graded digraphs and non-spanning digraphs. Many of our proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this thesis provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees, which we successfully apply to a large number of graph and digraph complexes. / QC 20100622

Cette thèse de doctorat a pour sujet les modèles de la théorie homotopique des types avec l'Axiome d'Univalence introduit par Vladimir Voevodsky. L'auteur prend pour cadre de travail les définitions de type-theoretic model category, type-theoretic fibration category (cette dernière étant la notion de modèle considérée dans cette thèse) et d'univers dans une type-theoretic fibration category, définitions dues à Michael Shulman. La problématique principale de cette thèse consiste à approfondir notre compréhension de la stabilité de l'Axiome d'Univalence pour les catégories de préfaisceaux, en particulier pour les groupoïdes équipés d'une involution. / This PhD thesis deals with some new models of Homotopy Type Theory and the Univalence Axiom introduced by Vladimir Voevodsky. Our work takes place in the framework of the definitions of type-theoretic model categories, type-theoretic fibration categories (the notion of model under consideration in this thesis) and universe in a type-theoretic fibration category, definitions due to Michael Shulman. The goal of this thesis consists mainly in the exploration of the stability of the Univalence Axiom for categories of functors , especially for groupoids equipped with involutions.

[pt] Enquanto a topologia do espaço de todas as curvas suaves imersas em 2-esfera começando e terminando em pontos dados e direções dadas é bem conhecido, é uma questão aberta entender o tipo de homotopia e dos seus subespaços consistindo as curvas com a curvatura restrita a um intervalo próprio aberto prescrito. Neste tese provamos que, sob certas circunstancias para os pontos e as direções inicial e final, estes subespaços não são homotopicamente equivalente ao espaço todo. Adicionalmente, fornecemos uma construção explicita dos geradores exóticos para algum grupo de homotopia e cohomologia. As dimensões desses geradores dependem das posições e das direções nas extremidades. Uma versão do princípio h foi usada na prova desses resultados. / [en] While the topology of the space of all smooth immersed curves in 2-sphere that start and end at given points in given direction is well known, it is an open problem to understand the homotopy type of its subspaces consisting of the curves whose geodesic curvatures are constrained to a prescribed proper open interval. In this article we prove that, under certain circumstances for endpoints and end directions, these subspaces are not homotopically equivalent to the whole space. Moreover, we give an explicit construction of exotic generators for some homotopy and cohomology groups. It turns out that the dimensions of these generators depend on endpoints and end directions. A version of the h-principle is used to prove these results.

No description available.