Title: The largest common subtree of two random trees
Abstract: Given two large random graphs, what is the size and structure of their largest common induced subgraph? This question has been a growing topic of interest in the probability and combinatorics communities in recent years, with the problem having been studied for a few different models of random graphs. In this talk, we will discuss the case where the two graphs are independent Bienaymé-Galton-Watson trees with finite-variance offspring distributions, conditioned to have size n. The main result is a scaling limit for the size of the largest common subtrees of two such random trees under some light assumptions. Based on joint work with Omer Angel, Caelan Atamanchuk, Serte Donderwinkel, and Robin Khanfir.
Reza Gheissari
Email