IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Introduction to the edit distance in graphs

  • Feb. 16, 2017
  • 4:30 p.m.
  • LeConte 412

Abstract

The edit distance is a very simple and natural metric on the space of graphs. In the edit distance problem, we fix a hereditary property of graphs and compute the asymptotically largest edit distance of a graph from the property. This quantity is very difficult to compute directly, but in many cases it can be derived as the maximum of what is known as the edit distance function. Szemeredi's regularity lemma, strongly-regular graphs, constructions related to the Zarankiewicz problem -- all these play a role in the computing of edit distance functions. In this talk, we give an overview of some of the major results in the literature and connections to other problems in extremal graph theory.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC