KTH/SU Mathematics Colloquium
Noga Alon, Tel Aviv University
The structure of graphs and Grothendieck-type Inequalities
I will describe a connection between a classical inequality of
Grothendieck and questions that arise in the study of the structure
of large graphs. The investigation of this connection suggests the
definition of a new graph parameter, called the Grothendieck constant
of a graph, whose study is motivated by algorithmic applications
and leads to an improvement of a recent result of Kashin and Szarek,
and to a solution of a problem of Megretski and of Charikar and Wirth.
Most of the lecture will be based on recent joint work with A. Naor,
and with K. Makarychev, Y. Makarychev and A. Naor.