Optimization Online


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

Christine Bachoc(bachoc***at***math.u-bordeaux1.fr)
Evan DeCorte(p.e.b.decorte***at***tudelft.nl)
Fernando Mario de Oliveira Filho(fmario***at***mi.fu-berlin.de)
Frank Vallentin(f.vallentin***at***tudelft.nl)

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.

Keywords: independence number/ratio, measurable chromatic number, infinite graph, adjacency operator, Lovasz theta-number, Hoffman bound

Category 1: Linear, Cone and Semidefinite Programming


Download: [PDF]

Entry Submitted: 01/06/2013
Entry Accepted: 01/06/2013
Entry Last Modified: 01/06/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society