Rutgers Discrete Mathematics Seminar

Title: Extremal graphs and graph limits

Speaker: Laszlo Lovasz, Eotvos Lorand University and IAS

Date: Tuesday, February 14, 2012 2:00pm

Location: Hill Center, Room 124, Rutgers University, Busch Campus, Piscataway, NJ

Abstract: Growing sequences of dense graphs have a limit object in terms of a symmetric measuable 2-variable function. A typical use of this fact in graph theory is the following: we want to prove a result, say an inequality betwee subgraph densities. We look at a sequence of counterexamples, and consider their limit. Often this allows clean formulations and arguments that would be awkward or impossible in the finite setting. We illustrate this by some results on Sidorenko's conjecture and "common graphs". This setting also allows us to pose and in some cases answer general questions about extremal graph theory: which inequalities between subgraph densities are valid, and what is the possible structure of extremal graphs.

See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math