## Combinatorics Seminar - Spring '20

When: Sunday, May 29,
10am

Where: 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 Lovasz Local Lemma. These bounds imply a general result on the convergence of
maxima of dependent random variables.