Boolean formulae, hypergraphs and combinatorial topology

DOI10.1016/J.TOPOL.2010.08.016MaRDI QIDQ712196zbMATHOpenAlexFDO

Authors James Conant, Oliver Thistlethwaite

Publication date 28 October 2010

Published in Topology and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0808.0739

zbMATH Keywords

discrete Morse theoryAlexander dualindependence complexBoolean formulaediscrete vector fieldsP/NP questiontheta complex

Mathematics Subject Classification ID

General topology of complexes (57Q05) Combinatorial aspects of simplicial complexes (05E45) Group actions on combinatorial structures (05E18) Classification of homotopy type (55P15) Homotopy groups of special spaces (55Q52) Theory of computing (68Q99) General logic (03B99)

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 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.

Recommendations

• Homology of the Boolean complex
• scientific article; zbMATH DE number 3937107
• On the topology of a Boolean representable simplicial complex
• Homotopy type of the Boolean complex of a Coxeter system.
• scientific article; zbMATH DE number 517080

Cites work

• scientific article; zbMATH DE number 1775445 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• P/NP , and the quantum field computer
• A user's guide to discrete Morse theory
• Complexes of directed trees
• Complexes of directed trees and independence complexes
• Limit, logic, and computation
• Morse theory for cell complexes
• Simplicial complexes of graphs

Cited in

(8)

• On the topology of a Boolean representable simplicial complex
• Homology of the Boolean complex
• HOMOTOPY MODEL THEORY
• Boolean Structures
• Relative definability of boolean functions via hypergraphs
• On the capacity of Boolean graph formulæ
• Exact transversal hypergraphs and application to Boolean \(\mu\)-functions
• Threshold complexes and connections to number theory

This page was built for publication: Boolean formulae, hypergraphs and combinatorial topology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q712196)