Mathematics – Algebraic Topology
Scientific paper
2008-08-05
Mathematics
Algebraic Topology
Added discussion of independence complex and new computer calculations. Added coauthor Oliver Thistlethwaite. To appear in Top
Scientific paper
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 less than or equal to n variables has the homotopy type of Theta(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.
Conant James
Thistlethwaite Oliver
No associations
LandOfFree
Boolean formulae, hypergraphs and combinatorial topology does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Boolean formulae, hypergraphs and combinatorial topology, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Boolean formulae, hypergraphs and combinatorial topology will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-27297