##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Prof. Lutz Warnke

#### UC San Diego

## Extreme local statistics in random graphs: maximum tree extension counts

##### Abstract:

We consider a generalization of the maximum degree in random graphs. Given a rooted tree $T$, let $X_v$ denote the number of copies of T rooted at v in the binomial random graph $G_{n,p}$. We ask the question where the maximum $M_n = max \{X_1, ..., X_n\}$ of $X_v$ over all vertices is concentrated. For edge-probabilities $p=p(n)$ tending to zero not too fast, the maximum is asymptotically attained by the vertex of maximum degree. However, for smaller edge probabilities $p=p(n)$, the behavior is more complicated: our large deviation type optimization arguments reveal that the behavior of $M_n$ changes as we vary $p=p(n)$, due to different mechanisms that can make the maximum large.

Based on joint work with Pedro Araújo, Simon Griffiths and Matas Šileikis; see arXiv:2310.11661

### June 4, 2024

### 2:00 PM

APM 7321

Research Areas

Combinatorics Probability Theory****************************