Boolean formulae, hypergraphs and combinatorial topology |
| |
Authors: | James Conant Oliver Thistlethwaite |
| |
Institution: | a University of Tennesse, Department of Mathematics, Knoxville, TN, United States b Department of Mathematics, University of California, Riverside, United States |
| |
Abstract: | With a view toward studying the homotopy type of spaces of Boolean formulae, we introduce a simplicial complex, called the theta complex, associated to any hypergraph, which is the Alexander dual of the more well-known independence complex. In particular, the set of satisfiable formulae in k-conjunctive normal form with ?n variables has the homotopy type of Θ(Cube(n,n−k)), where Cube(n,n−k) is a hypergraph associated to the (n−k)-skeleton of an n-cube. We make partial progress in calculating the homotopy type of theta for these cubical hypergraphs, and we also give calculations and examples for other hypergraphs as well. Indeed studying the theta complex of hypergraphs is an interesting problem in its own right. |
| |
Keywords: | Independence complex Boolean formulae Theta complex Discrete Morse theory |
本文献已被 ScienceDirect 等数据库收录! |
|