On the Lovász -number of almost regular graphs with application to Erdős-Rényi graphs

DOI10.1016/J.EJC.2008.07.022MaRDI QIDQ1024280zbMATH OpenOpenAlexWikidataFDO

Authors Mike Newman, E. de Klerk, Dmitrii V. Pasechnik, Renata Sotirov

Publication date 17 June 2009

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2008.07.022

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• scientific article; zbMATH DE number 1507223
• scientific article; zbMATH DE number 1439404
• The Erdős-Faber-Lovász conjecture for weakly dense hypergraphs
• The Erdős-Faber-Lovász conjecture for dense hypergraphs
• The Lovász number of random graphs
• The Lovász Number of Random Graphs
• A generalization of the Hoffman-Lovász upper bound on the independence number of a regular graph
• scientific article; zbMATH DE number 5130735
• Algorithmic and explicit determination of the Lovász number for certain circulant graphs
• Local structure theorems for Erdős-Rényi graphs and their algorithmic applications

Cites work

• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 1101474 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• scientific article; zbMATH DE number 2232233 (Why is no real title available?)
• A comparison of the Delsarte and Lovász bounds
• Character tables of the association schemes of finite orthogonal groups acting on the nonisotropic points
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Eigenvalue bounds for independent sets
• Graphs from projective planes
• Graphs without quadrilaterals
• On Graphs that do not Contain a Thomsen Graph
• On the Shannon capacity of a graph
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• On the number of edges of quadrilateral-free graphs
• Reduction of symmetric semidefinite programs using the regular \(\ast\)-representation
• Symmetry groups, semidefinite programs, and sums of squares
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones

Cited in

(10)

• The asymptotic behaviour of Lovasz' \(\vartheta\) function for random graphs
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software
• Invariant Semidefinite Programs
• A relative bound for independence
• The independence number for polarity graphs of even order planes
• The Lovász theta function for random regular graphs and community detection in the hard regime
• scientific article; zbMATH DE number 1507223 (Why is no real title available?)
• On the chromatic number of the Erdős-Rényi orthogonal polarity graph
• Numerical block diagonalization of matrix \(\ast\)-algebras with application to semidefinite programming

Describes a project that uses

Uses Software

• SeDuMi

This page was built for publication: On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs

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