Leírás
Abstract: The edit distance between two graphs on the vertex set $\{1,\ldots,n\}$ is defined to be the size of the symmetric difference of the edge sets, divided by ${n\choose 2}$. The edit distance function of a hereditary property $\mathcal{H}$ is a function of $p\in[0, 1]$ that measures, in the limit, the maximum edit distance between a graph of density $p$ and $\mathcal{H}$.
In the following talks, we will address results and open problems on:
* The role of Szemerédi's regularity lemma and colored regularity graphs
* Computing the edit distance function for specific hereditary properties
* The behavior of the edit distance function for the hereditary property of excluding a random graph
* Connections between the edit distance function and Turán theory in the degenerate case
* The difficulties in generalizing the edit distance function to other metrics or other combinatorial objects such as hypergraphs