Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Directed subgraph complexes. | Directed subgraph complexes Axel Hultman Fachbereich Mathematik und Informatik Philipps-Universităt Marburg D-35032 Marburg Germany axel@ Submitted Nov 25 2003 Accepted Oct 18 2004 Published Oct 26 2004 Mathematics Subject Classifications 05C20 05C40 55P15 Abstract Let G be a directed graph and let AAGCY be the simplicial complex whose simplices are the edge sets of acyclic subgraphs of G. Similarly we define A AC to be the simplicial complex with the edge sets of not strongly connected subgraphs of G as simplices. We show that AAGCY is homotopy equivalent to the n 1 k -dimensional sphere if G is a disjoint union of k strongly connected graphs. Otherwise it is contractible. If G belongs to a certain class of graphs the homotopy type of ANSC is shown to be a wedge of 2n 4 -dimensional spheres. The number of spheres can easily be read off the chromatic polynomial of a certain associated undirected graph. We also consider some consequences related to finite topologies and hyperplane arrangements. 1 Introduction A monotone property of a directed or undirected graph is one which is preserved under deletion of edges. Hence the set of all graphs on a particular vertex set n say that satisfy a monotone property form a simplicial complex whose vertex set is the set of edges of the graphs. In numerous recent papers see . 1 5 6 10 11 14 15 the topological properties of such complexes of graphs have been studied. Although most papers have dealt with complexes of all graphs having a particular property P it is indeed natural to study the complex of all subgraphs of a given graph that satisfy P. The purpose of this paper is to study directed graph complexes of this type. The properties that we Partially supported by the European Commission s IHRP Programme grant HPRN-CT-2001-00272 Algebraic Combinatorics in Europe . THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R75 1 focus on are acyclicity and strong non-connectivity. Both were studied by Bjorner .
