Boolean formulae, hypergraphs and combinatorial topology

DOI10.1016/J.TOPOL.2010.08.016zbMATH Open1206.57026arXiv0808.0739OpenAlexW2963271523MaRDI QIDQ712196FDOQ712196

Authors: James Conant, Oliver Thistlethwaite Edit this on Wikidata

Publication date: 28 October 2010

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Morse theory for cell complexes
• Simplicial complexes of graphs
• Complexes of directed trees and independence complexes
• Complexes of directed trees
• A user's guide to discrete Morse theory
• P/NP , and the quantum field computer
• Limit, logic, and computation
• Title not available (Why is that?)

Cited In (8)

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

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)