Let G be a graph with several vertices v_1,..,v_r being roots. A G-extension of u_1,..,u_r in a graph H is a subgraph \hat G of H such that there exists a bijection from V(G) to V(\hat G) that preserves edges of G with at least one non-root vertex. In binomial random graphs, for sufficiently large edge probability p, the number of subgraphs isomorphic to a given graph G obeys both the law of large numbers and the central limit theorem. The maximum number of G-extensions obeys the law of large numbers as well. The talk is devoted to new results describing the limit distribution of the maximum number of G-extensions. Also, I am going to show some connections between the results on limit distributions of the numbers of small subgraphs and extensions and logical limit laws.
For Zoom information, please contact Sean at SEnglish (at) illinois (dot) edu.
