Quadratic forms on graphs

DOI10.1007/s00222-005-0465-9zbMath1082.05051OpenAlexW2030987833MaRDI QIDQ5896810

Yury Makarychev, Noga Alon, Konstantin Makarychev, Assaf Naor

Publication date: 21 March 2006

Published in: Inventiones Mathematicae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00222-005-0465-9

zbMATH Keywords

approximation algorithmchromatic numberperfect graphGram matricesintegrality gapGrothendieck constantGrothendieck inequality

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Quadratic and bilinear forms, inner products (15A63)

Related Items

Nonlinear absolutely summing operators revisited, Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms, Grothendieck-Type Inequalities in Combinatorial Optimization, Estimates for the asymptotic behaviour of the constants in the Bohnenblust–Hille inequality, Fast Heuristics and Approximation Algorithms, An observation on the Gram matrices of systems of uniformly bounded functions and a problem of Olevskii, Computing the Grothendieck constant of some graph classes, A generalized Grothendieck inequality and nonlocal correlations that require high entanglement, Unnamed Item, Moment inequalities for sums of random matrices and their applications in optimization, Spectral bounds for the independence ratio and the chromatic number of an operator, The Hilbertian tensor norm and entangled two-prover games, New Bell inequalities for the singlet state: Going beyond the Grothendieck bound, Grothendieck’s Theorem, past and present, An axiomatic duality framework for the theta body and related convex corners, Quantitative geometry, Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization, The Grothendieck Inequality Revisited, Approximate Kernel Clustering, Grothendieck constant is norm of Strassen matrix multiplication tensor, Grothendieck bound in a single quantum system

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
• Kneser's conjecture, chromatic number, and homotopy
• Matching theory
• Quick approximation to matrices and applications
• The ellipsoid method and its consequences in combinatorial optimization
• Bounding the vertex cover number of a hypergraph
• Explicit Ramsey graphs and orthonormal labelings
• Covering a hypergraph of subgraphs
• On the chromatic number of intersection graphs of convex sets in the plane
• On maximization of quadratic form over intersection of ellipsoids with common center
• Clustering with qualitative information
• Approximating the cut-norm via Grothendieck's inequality
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• Algorithms with large domination ratio
• Repeated communication and Ramsey graphs
• Absolutely summing operators in $ℒ_{p}$-spaces and their applications