The proof of Po'sa - Seymour Conjecture
Spekaer: Prof. E. Szemeredi (Abel Prize winner (2012)), Alfred Renyi Institute of Mathemastics, Hungarian Academy of Sciences and Department of Computer Sciences, Rutgers University.

Time:  9h30, Wednesday 30 July 2014
Venue: Room 301, Building A5, Institute of Mathematics, VAST, 18 Hoang Quoc Viet, Cau Giay, Ha Noi.
Abstract:  In 1974  Paul Seymour conjectured that any graph G of order  $n$  and minimum degree at least  $(k/k+1)n$  contains the $k-th$ power of a Hamiltonian cycle. This conjecture was proved with the help of the Regularity Lemma – Blow-up  Lemma method for  $n \ge n_0$ where $n_0$ is very large. Here we present another  proof that avoids the use of the Regularity Lemma and thus the resulting $n_0$ is much  smaller. The main ingredient is a new kind of connecting lemma.

 

E. Szemeredi was born  in Budapest, Hungary in 1940. He received his Ph. D. from Moscow State University  (Lomonosov) in 1970 under I. M. Gelfand. He has held various positions in US and Canada and received many prestigious prizes, among them the most notably Abel Prize  from the Norway Academy of Science and Letters  for his outstanding contributions to mathematics.

Professor Szemeredi has revolutionized  discrete mathematics by introducing ingenious and novel techniques and by solving many fundamental  problems. His work has  brought  combinatorics to the central stage of mathematics by revealing its deep connections to such fields as additive number theory, ergodic theory, theoretical computer science and incidence geometry.

Below there will be  a review of one of the many facets of his works 

In 1975, Szemeredi attracted  great  attention of many mathematicians by proving the Erdos-Turan conjecture, which says that in any set of integers of positive density, there exists an arithmetic progression of arbitrary length, later on it is Szemeredi Theorem. It is a big surprise, since even in the case of progessions of length 3 or 4, it required from Klaus Roth (Fields Medalist 1958) and Szemeredi himself a great effort. The proof given by Szemeredi can be considered as a

master piece in mathematics. On of the crucial steps is to establish the so-called Regularity Lemma, which became essential tool in the theory of large graphs in particular, and in  graph theory in general and it led to various solutions of many problems in other branches of mathematics.  Beyond its impact on discrete mathematics, Szemeredi Theorem has inspired outstanding mathematician Hillel Furstenberg to develop ergodic theory in many other directions, pointing out

unexpected relations with other branches of mathematics. Namely this fundamental connection  led to many new developments, including Green-Tao Theorem on the existence of an arbitrary long arithmetic progression consisting only of  primes.

 

Some of pictures Prof.  E. Szemeredi (Abel Prize winner (2012)) talk at the Institute of Mathematics, Hanoi

Back