The theta number of simplicial complexes
From MaRDI portal
Publication:2317686
DOI10.1007/S11856-019-1880-8zbMATH Open1419.90109arXiv1704.01836OpenAlexW2963296861MaRDI QIDQ2317686FDOQ2317686
Alberto Passuello, Christine Bachoc, Anna Gundert
Publication date: 12 August 2019
Published in: Israel Journal of Mathematics (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1704.01836
[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Lov%EF%BF%BD%EF%BF%BDsz+theta+number&go=Go Lov��sz theta number]
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Semidefinite Programming
- Spectra of graphs
- On the Shannon capacity of a graph
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- Isoperimetric inequalities for Ramanujan complexes and topological expanders
- Ramanujan complexes and high dimensional expanders
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Singularities, expanders and topology of maps. II: From combinatorics to topology via algebraic isoperimetry
- Homological connectivity of random 2-complexes
- Isoperimetric inequalities in simplicial complexes
- p-adic curvature and the cohomology of discrete subgroups of p-adic groups
- Mixing Properties and the Chromatic Number of Ramanujan Complexes
- Bounded degree cosystolic expanders of every dimension
- Handbook on semidefinite, conic and polynomial optimization
- The sphere packing problem in dimension \(24\)
- Computing upper bounds for the packing density of congruent copies of a convex body
- Enumeration of \({\mathbb{Q}}\)-acyclic simplicial complexes
- Approximation Algorithms and Semidefinite Programming
- Spectral techniques applied to sparse random graphs
- Intersecting families of permutations
- The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
- Simplicial and cellular trees
- On Laplacians of random complexes
- A Moore bound for simplicial complexes
- Triangle-intersecting families of graphs
- Simplicial complexes: Spectrum, homology and random walks
- Spectra of combinatorial Laplace operators on simplicial complexes
- Spectral Gaps of Random Graphs and Applications
- The sphere packing problem in dimension 8
- Hardness of embedding simplicial complexes in \(\mathbb R^d\)
- The Lovász Number of Random Graphs
- On the chromatic number of a simplicial complex
- On expansion and topological overlap
- 2-complexes with large 2-girth
- Fourier Analysis on Finite Groups and the Lovász ϑ-Number of Cayley Graphs
Cited In (6)
- Title not available (Why is that?)
- Spectral upper bound on the quantum k-independence number of a graph
- Conic linear optimization for computer-assisted proofs. Abstracts from the workshop held April 10--16, 2022
- On the spectrum and linear programming bound for hypergraphs
- High dimensional Hoffman bound and applications in extremal combinatorics
- Spectrum of signless 1-Laplacian on simplicial complexes
This page was built for publication: The theta number of simplicial complexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2317686)
