The Grothendieck constant of random and pseudo-random graphs

DOI10.1016/J.DISOPT.2006.06.004MaRDI QIDQ951106zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

semidefinite programmingrandom graphsGrothendieck constant of a graph

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3124239 (Why is no real title available?)
• A proof of alon's second eigenvalue conjecture
• Explicit construction of linear sized tolerant networks
• Quadratic forms on graphs (extended abstract)
• The ellipsoid method and its consequences in combinatorial optimization
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(7)

• Computing the Grothendieck constant of some graph classes
• Grothendieck’s Theorem, past and present
• 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)