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

被引：0
作者：
Christine Bachoc
Evan DeCorte
Fernando Mário de Oliveira Filho
Frank Vallentin
机构：
[1] Université Bordeaux I,Institut de Mathématiques de Bordeaux
[2] Technical University of Delft,Delft Institute of Applied Mathematics
[3] Universidade de São Paulo,Departamento de Ciência da Computação Instituto de Matemática e Estatística
[4] Universität zu Köln,Mathematisches Institut
来源：
Israel Journal of Mathematics | 2014年 / 202卷
关键词：
Adjacency Matrix; Chromatic Number; Numerical Range; Distance Graph; Invariant Probability Measure;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We define the independence ratio and the chromatic number for bounded, self-adjoint operators on an L2-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.
引用
收藏
页码：227 / 254
页数：27
相关论文
共 42 条
  • [1] Alon N.(2006)Quadratic forms on graphs Inventiones Mathematicae 163 499-522
  • [2] Makarychev K.(2009)The odd-distance plane graph Discrete & Computational Geometry 42 132-141
  • [3] Makarychev Y.(2009)Lower bounds for measurable chromatic numbers Geometric and Functional Analysis 19 645-661
  • [4] Naor A.(2012)Triangle intersecting families of graphs Journal of the European Mathematical Society (JEMS) 14 841-885
  • [5] Ardal H.(2011)Intersecting families of permutations Journal of the American Mathematical Society 24 649-682
  • [6] Maňuch J.(2000)Spectral characterizations of the Lovász number and the Delsarte number of a graph Journal of Algebraic Combinatorics 12 131-142
  • [7] Rosenfeld M.(2010)Theta bodies for polynomial ideals SIAM Journal of Optimization 20 2097-2118
  • [8] Shelah S.(1984)Polynomial algorithms for perfect graphs Annals of Discrete Mathematics 21 325-356
  • [9] Stacho L.(1998)Approximate graph coloring by semidefinite programming Journal of the ACM 45 246-265
  • [10] Bachoc C.(1998)The Lovász theta function and a semidefinite programming relaxation of vertex cover SIAM Journal on Discrete Mathematics 11 196-204
12345