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

DOI10.1007/s11856-014-1070-7zbMath1302.05047arXiv1301.1054OpenAlexW3100415765MaRDI QIDQ466129

Christine Bachoc, Evan DeCorte, Frank Vallentin, Fernando Mário de Oliveira Filho

Publication date: 24 October 2014

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.1054

zbMATH Keywords

infinite geometric graphs on Euclidean spaceinfinite geometric graphs on the unit sphere

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Infinite graphs (05C63)

Related Items (10)

A recursive Lovász theta number for simplex-avoiding sets ⋮ Independent sets, cliques, and colorings in graphons ⋮ New directions in real algebraic geometry. Abstracts from the workshop held March 19--24, 2023 ⋮ Graphical designs and extremal combinatorics ⋮ Odd distances in colourings of the plane ⋮ Polynomial configurations in sets of positive upper density over local fields ⋮ On a generalization of the Hadwiger-Nelson problem ⋮ Coloring the Voronoi tessellation of lattices ⋮ Lower bounds for the measurable chromatic number of the hyperbolic plane ⋮ The density of sets avoiding distance 1 in Euclidean space

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A quantitative version of Steinhaus' theorem for compact, connected, rank-one symmetric spaces
• Fourier analysis, linear programming, and densities of distance avoiding sets in \(\mathbb R^n\)
• On coloring the odd-distance graph
• Lower bounds for measurable chromatic numbers
• The sandwich theorem
• Spectral characterizations of the Lovász number and the Delsarte number of a graph
• Distance sets corresponding to convex bodies
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• The odd-distance plane graph
• Triangle-intersecting families of graphs
• On the theta number of powers of cycle graphs
• Theta Bodies for Polynomial Ideals
• Grothendieck inequalities for semidefinite programs with rank constraint
• The Mathematical Coloring Book
• Approximate graph coloring by semidefinite programming
• A comparison of the Delsarte and Lovász bounds
• On the Shannon capacity of a graph
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• Intersecting families of permutations
• Quadratic forms on graphs

This page was built for publication: Spectral bounds for the independence ratio and the chromatic number of an operator