The Grothendieck constant of random and pseudo-random graphs

DOI10.1016/J.DISOPT.2006.06.004zbMATH Open1151.90055OpenAlexW1967047762MaRDI QIDQ951106FDOQ951106

Authors: Noga Alon, Eli Berger 

Publication date: 29 October 2008

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2006.06.004

Recommendations

• An analogue of the Erdős-Gallai theorem for random graphs
• scientific article; zbMATH DE number 4099367
• Random graphs and the parity quantifier
• Random graphs and the parity quantifier
• Turán's theorem for pseudo-random graphs
• Random graph-homomorphisms and logarithmic degree
• Random graphons and a weak positivstellensatz for graphs
• The Lovász number of random graphs
• The Lovász Number of Random Graphs
• Random hypergraphs in pseudofinite fields

zbMATH Keywords

semidefinite programmingrandom graphsGrothendieck constant of a graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22)

Cites Work

• The ellipsoid method and its consequences in combinatorial optimization
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Explicit construction of linear sized tolerant networks
• Quadratic forms on graphs (extended abstract)
• A proof of alon's second eigenvalue conjecture

Cited In (7)

• Grothendieck’s Theorem, past and present
• Computing the Grothendieck constant of some graph classes
• The monoid of the random graph
• Quadratic forms on graphs
• Grothendieck-type inequalities in combinatorial optimization
• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Quadratic forms on graphs (extended abstract)

This page was built for publication: The Grothendieck constant of random and pseudo-random graphs

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