Distinguished Lectures Series - Talk II: Limits of Dense Graphs: Algorithms And Extremal Graph Theory

Prof. László Lovász (Eötvös Loránd University in Budapest, Hungary)

Wednesday, 01.05.2013, 13:30

Room 337-8 Taub Bld.

the classical algorithmic problems must be rephrased, and a new kind of complexity theory emerges. Much of this has been worked out in the theory of "Graph Property Testing" in computer science, where we assume that information about such graphs is obtained by an appropriate sampling procedure. Graph limits offer a new perspective on this field, along with some new results.

Many questions in extremal graph theory can be phrased like this: what is the maximum of a certain linear combination of densities of given graphs in any graph G? Answers to such questions are often quite difficult. Graph limits make it possible to pose and in some cases answer some general questions about extremal graphs: Which inequalities between subgraph densities are valid? Can all valid inequalities be proved using just Cauchy-Schwarz? Is there always an extremal graph? Which graphs are extremal?

Talk III by Prof. László Lovász will be on May 2, 14:30-15:30, Taub Building 337

The lecture is for mathematically minded audience.

Bio:

László Lovász, born in 1948 in Budapest, is a Hungarian-American mathematician, best known for his work in combinatorics, combinatorial optimization, graph theory and their impact on computer science, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010. He received the Fulkerson Prize twice (1982, 2012), Hungary's Széchenyi Grand Prize (2008), Bolyai prize (2007), Gödel Prize (2001).

Lovász received his Candidate of Sciences degree in 1970 at Hungarian Academy of Sciences. His advisor was Tibor Gallai. Until 1975, Lovász worked at the Eötvös University, between 1975-1982 he led the Department of Geometry at the University of Szeged.

In 1982 he returned to the Eötvös University, where he created the Department of Computer Science.

Lovász was a professor at Yale University during the 1990s and was a collaborative member of the Microsoft Research Center until 2006. He returned to Eötvös Loránd University, Budapest, where he was the director of the Mathematical Institute (2006-2011). He served as president of the International Mathematical Union between January 1, 2007 and December 31, 2010.

Youtube Interview: Avi Wigderson interviews László Lovász.

Many questions in extremal graph theory can be phrased like this: what is the maximum of a certain linear combination of densities of given graphs in any graph G? Answers to such questions are often quite difficult. Graph limits make it possible to pose and in some cases answer some general questions about extremal graphs: Which inequalities between subgraph densities are valid? Can all valid inequalities be proved using just Cauchy-Schwarz? Is there always an extremal graph? Which graphs are extremal?

Talk III by Prof. László Lovász will be on May 2, 14:30-15:30, Taub Building 337

The lecture is for mathematically minded audience.

Bio:

László Lovász, born in 1948 in Budapest, is a Hungarian-American mathematician, best known for his work in combinatorics, combinatorial optimization, graph theory and their impact on computer science, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010. He received the Fulkerson Prize twice (1982, 2012), Hungary's Széchenyi Grand Prize (2008), Bolyai prize (2007), Gödel Prize (2001).

Lovász received his Candidate of Sciences degree in 1970 at Hungarian Academy of Sciences. His advisor was Tibor Gallai. Until 1975, Lovász worked at the Eötvös University, between 1975-1982 he led the Department of Geometry at the University of Szeged.

In 1982 he returned to the Eötvös University, where he created the Department of Computer Science.

Lovász was a professor at Yale University during the 1990s and was a collaborative member of the Microsoft Research Center until 2006. He returned to Eötvös Loránd University, Budapest, where he was the director of the Mathematical Institute (2006-2011). He served as president of the International Mathematical Union between January 1, 2007 and December 31, 2010.

Youtube Interview: Avi Wigderson interviews László Lovász.