CWI Lectures - Frank Vallentin - Generalizations and Applications of the Lovász theta number
Centrum Wiskunde & Informatica Centrum Wiskunde & Informatica
1.19K subscribers
160 views
1

 Published On Nov 22, 2022

The theta number of Lovász of a graph, originally invented to determine the Shannon capacity of the pentagon, has been a source of inspiration for everybody working in the area of semidefinite programming (linear optimization over the convex cone of positive semidefinite matrices). By Lovász' sandwich theorem the theta number is sandwiched between the independence number of the graph and the chromatic number of the complementary graph.

In this lecture I will discuss generalizations, strengthenings, and applications of the Lovász theta number for infinite geometric graphs and hypergraphs. In concrete applications harmonic analysis will be key to perform explicit computations.

show more

Share/Embed