Mathematics Seminar - Prof. Maksim Zhukovskii

Title: Extremal independence in discrete random systems

Abstract:

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. Study of G-extensions in random graphs is in particular motivated by the problem of axiomatization of first order almost sure theories. 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.