
Open access
Date
2022-01-04Type
- Journal Article
ETH Bibliography
yes
Altmetrics
Abstract
The n-th tensor power of a graph with vertex set V is the graph on the vertex set V n, where two vertices are connected by an edge if they are connected in each coordinate. One powerful method for upper-bounding the largest independent set in a graph is the Hoffman bound, which gives an upper bound on the largest independent set of a graph in terms of its eigenvalues. In this paper we introduce the problem of upper-bounding independent sets in tensor powers of hypergraphs. We show that many prominent open problems in extremal combinatorics, such as the Turán problem for graphs and hypergraphs, can be encoded as special cases of this problem. We generalize the Hoffman bound to hypergraphs, and give several applications. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000526825Publication status
publishedExternal links
Journal / series
Algebraic CombinatoricsVolume
Pages / Article No.
Publisher
Centre MersenneSubject
Chromatic number; Independence ratio; hypergraph; Extremal set theoryOrganisational unit
08802 - Iozzi, Alessandra (Tit.-Prof.)
Funding
169106 - Continuous Bounded Cohomology and Applications (SNF)
Related publications and datasets
Is new version of: http://hdl.handle.net/20.500.11850/391252
More
Show all metadata
ETH Bibliography
yes
Altmetrics