Activities This Week

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 G* of H such that there exists a bijection from V(G) to V(G*) that maps v_i to u_i and preserves edges of G with at least one non-root vertex. It is well known that, in dense binomial random graphs, the maximum number of G-extensions obeys the law of large numbers. The talk is devoted to new results describing the limit distribution of the maximum number of G-extensions. To prove these results, we develop new bounds on the probability that none of a given finite set of events occur. Our inequalities allow us to distinguish between weakly and strongly dependent events in contrast to well-known Janson’s and Suen’s inequalities as well as Lovasz Local Lemma. These bounds imply a general result on the convergence of maxima of dependent random variables.