Talk information

Date: Sunday, May 29, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Maksim Zhukovskii (Weizmann and MIPT)
Title: Extremal Independence in Discrete Systems

Abstract:

Let $G$ be a graph with several vertices $v_1,\ldots,v_r$ being roots. A $G$-extension of $u_1,\ldots,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 Lovász Local Lemma. These bounds imply a general result on the convergence of maxima of dependent random variables.