Spectral bounds for the independence ratio and the chromatic number of an operator

Abstract

We define the independence ratio and the chromatic number for bounded, self-adjoint operators on an L^2-space by extending the definitions for the adjacency matrix of finite graphs. In analogy to the Hoffman bounds for finite graphs, we give bounds for these parameters in terms of the numerical range of the operator. This provides a theoretical framework in which many packing and coloring problems for finite and infinite graphs can be conveniently studied with the help of harmonic analysis and convex optimization. The theory is applied to infinite geometric graphs on Euclidean space and on the unit sphere.

(v2) 21 pages, revision based on suggestions by referee, accepted in Israel Journal of Mathematics

Cited by in corpus (9)

• Independent sets, cliques, and colorings in graphons
• Graphical Designs and Extremal Combinatorics
• Coloring the Voronoi tessellation of lattices
• Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs
• Lower bounds for the measurable chromatic number of the hyperbolic plane
• On symmetry adapted bases in trigonometric optimization
• Orbit spaces of Weyl groups acting on compact tori: a unified and explicit polynomial description
• A recursive Lovász theta number for simplex-avoiding sets
• A recursive theta body for hypergraphs