Quadratic forms on graphs

DOI10.1007/S00222-005-0465-9MaRDI QIDQ5896810zbMATH OpenOpenAlexFDO

Authors Noga Alon, Konstantin Makarychev, Yury 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 numberGram matricesGrothendieck constantGrothendieck inequalityintegrality gapperfect graph

Mathematics Subject Classification ID

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

Recommendations

• Quadratic forms on graphs (extended abstract)
• The Grothendieck constant of random and pseudo-random graphs
• Grothendieck-type inequalities in combinatorial optimization
• Computing the Grothendieck constant of some graph classes
• Towards computing the Grothendieck constant

Cites work

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

Cited in

(29)

• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Nonlinear absolutely summing operators revisited
• Grothendieck-type inequalities in combinatorial optimization
• Estimates for the asymptotic behaviour of the constants in the Bohnenblust–Hille inequality
• The Grothendieck inequality revisited
• Approximate kernel clustering
• New Bell inequalities for the singlet state: Going beyond the Grothendieck bound
• The UGC hardness threshold of the l_p Grothendieck problem
• Computing the Grothendieck constant of some graph classes
• Towards computing the Grothendieck constant
• Spectral bounds for the independence ratio and the chromatic number of an operator
• Fast heuristics and approximation algorithms
• An observation on the Gram matrices of systems of uniformly bounded functions and a problem of Olevskii
• The Hilbertian tensor norm and entangled two-prover games
• Quantitative geometry
• An axiomatic duality framework for the theta body and related convex corners
• Grothendieck’s Theorem, past and present
• Sharp kernel clustering algorithms and their associated Grothendieck inequalities
• Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
• Grothendieck bound in a single quantum system
• Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms
• Quadratic forms on graphs (extended abstract)
• scientific article; zbMATH DE number 7758351 (Why is no real title available?)
• A generalized Grothendieck inequality and nonlocal correlations that require high entanglement
• Moment inequalities for sums of random matrices and their applications in optimization
• Factorization norms and an inverse theorem for MaxCut
• Positive discrepancy, MaxCut, and eigenvalues of graphs
• Large cuts in hypergraphs via energy
• Cluster editing parameterized above modification-disjoint P₃-packings

This page was built for publication: Quadratic forms on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896810)