Generalizations and Applications of the Lovász theta number

by Frank Vallentin (U. Cologne)

Tuesday May 13, 2025, 2:00 PM → 4:00 PM Europe/Paris

Salle J. Cavailles (1R2-132) (IMT)

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

In the first part of the talk, I will discuss strengthenings and applications in coding theory and discrete geometry of the Lovász theta number. In concrete applications, harmonic analysis will be key to performing explicit computations.

In the second part of the talk (based on joint work with Davi Castro-Silva, Fernando M. de Oliveira Filho, and Lucas Slot), I will show how one can recursively define a Lovász theta number for uniform hypergraphs. In particular, I will illustrate the use of our new definition by giving a proof of Mantel's theorem about triangle-free sets in graphs, and by providing upper bounds for the independence ratio of triangle-avoiding sets in the binary Hamming cube, as well as for simplex-avoiding sets on the unit sphere and in Euclidean space.