The Theta Number of Simplicial Complexes
| Autor: | Anna Gundert, Alberto Passuello, Christine Bachoc |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Semidefinite programming
FOS: Computer and information sciences 55U10 05C65 05C69 05C15 05C50 Discrete Mathematics (cs.DM) General Mathematics 010102 general mathematics 0102 computer and information sciences 01 natural sciences Upper and lower bounds Mathematics::Algebraic Topology Graph Cohomology Combinatorics Simplicial complex 010201 computation theory & mathematics Optimization and Control (math.OC) FOS: Mathematics Mathematics - Combinatorics Chromatic scale Combinatorics (math.CO) 0101 mathematics Mathematics - Optimization and Control Computer Science - Discrete Mathematics Mathematics Independence number |
| DOI: | 10.48550/arxiv.1704.01836 |
| Popis: | We introduce a generalization of the celebrated Lov\'asz theta number of a graph to simplicial complexes of arbitrary dimension. Our generalization takes advantage of real simplicial cohomology theory, in particular combinatorial Laplacians, and provides a semidefinite programming upper bound of the independence number of a simplicial complex. We consider properties of the graph theta number such as the relationship to Hoffman's ratio bound and to the chromatic number and study how they extend to higher dimensions. Like in the case of graphs, the higher dimensional theta number can be extended to a hierarchy of semidefinite programming upper bounds reaching the independence number. We analyze the value of the theta number and of the hierarchy for dense random simplicial complexes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|