The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs

DOI10.1007/BF02579314zbMath0526.05050OpenAlexW51435562MaRDI QIDQ594904

Ferenc Juhász

Publication date: 1982

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02579314

zbMATH Keywords

asymptotic behaviourrandom matrixShannon capacitytheta-function

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random matrices (algebraic aspects) (15B52)

Related Items (11)

Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem ⋮ Strong lift-and-project cutting planes for the stable set problem ⋮ The asymptotic behaviour of Fiedler's algebraic connectivity for random graphs ⋮ Quadratic forms on graphs ⋮ On Laplacian spectra of parametric families of closely connected networks with application to cooperative control ⋮ Exploring the relationship between max-cut and stable set relaxations ⋮ The minrank of random graphs over arbitrary fields ⋮ The theta number of simplicial complexes ⋮ Strengthening Chvátal-Gomory Cuts for the Stable Set Problem ⋮ Dynamic node packing

Cites Work

• The eigenvalues of random symmetric matrices
• On the Shannon capacity of a graph

This page was built for publication: The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs