| 1. |
- Hultman, Axel, et al.
(författare)
-
From Bruhat intervals to intersection lattices and a conjecture of Postnikov
- 2009
-
Ingår i: Journal of combinatorial theory. Series A (Print). - : Elsevier BV. - 0097-3165 .- 1096-0899. ; 116:3, s. 564-580
-
Tidskriftsartikel (refereegranskat)abstract
- We prove the conjecture of A. Postnikov that (A) the number of regions in the inversion hyperplane arrangement associated with a permutation w is an element of (sic)(n). is at most the number of elements below w in the Bruhat order, and (B) that equality holds if and only if w avoids the patterns 4231, 35142, 42513 and 351624. Furthermore, assertion (A) is extended to all finite reflection groups. A byproduct of this result and its proof is a set of inequalities relating Betti numbers of complexified inversion arrangements to Betti numbers of closed Schubert cells. Another consequence is a simple combinatorial interpretation of the chromatic polynomial of the inversion graph of a permutation which avoids the above patterns.
|
|
| 2. |
- Jonsson, Jakob, 1972-
(författare)
-
Simplicial Complexes of Graphs
- 2005
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 3. |
- Linusson, Svante, et al.
(författare)
-
Complexes of graphs with bounded matching size
- 2008
-
Ingår i: Journal of Algebraic Combinatorics. - : Springer Science and Business Media LLC. - 0925-9899 .- 1572-9192. ; 27:3, s. 331-349
-
Tidskriftsartikel (refereegranskat)abstract
- For positive integers k, n, we investigate the simplicial complex NMk(n) of all graphs G on vertex set [n] such that every matching in G has size less than k. This complex (along with other associated cell complexes) is found to be homotopy equivalent to a wedge of spheres. The number and dimension of the spheres in the wedge are determined, and (partially conjectural) links to other combinatorially defined complexes are described. In addition we study for positive integers r, s and k the simplicial complex BNMk(r, s) of all bipartite graphs G on bipartition [r] boolean OR [(s) over bar] such that there is no matching of size k in G, and obtain results similar to those obtained for NMk(n).
|
|
