Let P be a monotone property of directed graphs on n vertices, and let $\Delta_n^{P}$ denote the abstract simplicial complex whose simplices are the edge sets of graphs having property P. We prove the following: If "P = acyclic,' then $\Delta_n^{P}$ is homotopy equivalent to the (n-2)-sphere. If "P = not strongly connected,' then $\Delta_n^{P}$ has the homotopy type of a wedge of (n-1)! spheres of dimension 2n-4. The lattice of all posets on {1,2,...,n} plays an important role in the analysis. We also discuss some other properties of directed graphs from this point of view.

Article Free Access Share on Linear decision trees: volume estimates and topological bounds Authors: Anders Björner Royal Institute of Technology, Stockholm, Sweden S-100 44 Royal Institute of Technology, Stockholm, Sweden S-100 44View Profile , László Lovász Eötvös Loránd University, Budapest, Hungary H-1088, Princeton University, Princeton, NJ Eötvös Loránd University, Budapest, Hungary H-1088, Princeton University, Princeton, NJView Profile , Andrew C. C. Yao Princeton University, Princeton, NJ Princeton University, Princeton, NJView Profile Authors Info & Claims STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of ComputingJuly 1992 Pages 170–177https://doi.org/10.1145/129712.129730Published:01 July 1992Publication History 41citation642DownloadsMetricsTotal Citations41Total Downloads642Last 12 Months28Last 6 weeks4 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF