Universität zu Köln

Bachoc, Christine, Gundert, Anna and Passuello, Alberto (2019). The theta number of simplicial complexes. Isr. J. Math., 232 (1). S. 443 - 482. JERUSALEM: HEBREW UNIV MAGNES PRESS. ISSN 1565-8511

Full text not available from this repository.

Abstract

We introduce a generalization of the celebrated Lovasz 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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Bachoc, Christine UNSPECIFIED UNSPECIFIED UNSPECIFIED Gundert, Anna UNSPECIFIED UNSPECIFIED UNSPECIFIED Passuello, Alberto UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-145595
DOI:	10.1007/s11856-019-1880-8
Journal or Publication Title:	Isr. J. Math.
Volume:	232
Number:	1
Page Range:	S. 443 - 482
Date:	2019
Publisher:	HEBREW UNIV MAGNES PRESS
Place of Publication:	JERUSALEM
ISSN:	1565-8511
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language SPHERE PACKING PROBLEM; SPECTRA Multiple languages Mathematics Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/14559