Boolean formulae, hypergraphs and combinatorial topology

DOI10.1016/J.TOPOL.2010.08.016MaRDI QIDQ712196zbMATH OpenOpenAlexFDO

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

Alexander dualBoolean formulaediscrete Morse theorydiscrete vector fieldsindependence complexP/NP questiontheta complex

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 1775445 (Why is no real title available?)
• scientific article; zbMATH DE number 2103273 (Why is no real title available?)
• Limit, logic, and computation
• Morse theory for cell complexes
• Simplicial complexes of graphs

Cited in

(8)

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

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)