# On the Lovasz Theta-number of Almost Regular Graphs with Application to Erdos-Renyi Graphs

Tuesday, January 16, 2007 - 11:00am - 11:50am

EE/CS 3-180

Etienne De Klerk (Katholieke Universiteit Brabant (Tilburg University))

We consider k-regular graphs with loops, and study the Lovasz

theta-numbers and Schrijver theta'-numbers of the

graphs that result when the loop edges are removed. We show that the

theta-number dominates a recent eigenvalue upper bound on the

stability number due to Godsil and Newman [C.D. Godsil and M.W.

Newman. Eigenvalue bounds for independent sets. Journal of

Combinatorial Theory B, to appear].

As an application we compute the theta and theta' numbers of certain instances of

Erdos-Renyi graphs. This computation exploits the graph symmetry using the methodology introduced in

[E. de Klerk, D.V. Pasechnik and A. Schrijver. Reduction of symmetric semidefinite programs using the regular *-representation.

Mathematical Programming B, to appear]. The computed values are strictly better than the Godsil-Newman eigenvalue bounds.

(Joint work with Mike Newman, Dima Pasechnik, and Renata Sotirov.)

theta-numbers and Schrijver theta'-numbers of the

graphs that result when the loop edges are removed. We show that the

theta-number dominates a recent eigenvalue upper bound on the

stability number due to Godsil and Newman [C.D. Godsil and M.W.

Newman. Eigenvalue bounds for independent sets. Journal of

Combinatorial Theory B, to appear].

As an application we compute the theta and theta' numbers of certain instances of

Erdos-Renyi graphs. This computation exploits the graph symmetry using the methodology introduced in

[E. de Klerk, D.V. Pasechnik and A. Schrijver. Reduction of symmetric semidefinite programs using the regular *-representation.

Mathematical Programming B, to appear]. The computed values are strictly better than the Godsil-Newman eigenvalue bounds.

(Joint work with Mike Newman, Dima Pasechnik, and Renata Sotirov.)