## Math Calendar

Subgraphs contain important information about network structures and their functions. We investigate the presence of subgraphs in several random graph models with infinite-variance degrees. We introduce an optimization problem that identifies the dominant structure of any given subgraph. The optimizer describes the degrees of the vertices that together span the most likely subgraph and allows us count and characterize all subgraphs.

We then show that this optimization problem easily extends to other network structures, such as local clustering, which expresses the probability that two neighbors of a vertex are connected. The optimization problem is able to find the behavior of clustering in a wide class of random graph models.

|| A_n ||_{r→p} := sup_{x\ in R^n, ||x||_r<1 } || A_n x ||_p for r,p>=1,

(see PDF: https://surfdrive.surf.nl/files/index.php/s/RNjWDCMREJbYgJE)

For different choices of r and p, this norm corresponds to key quantities that arise in di- verse applications including matrix condition number estimation, clustering of data, and finding oblivious routing schemes in transportation networks. This talk considers r → p norms of symmetric random matrices with nonnegative entries, including adjacency ma- trices of Erdo ̋s-Rényi random graphs, matrices with positive sub-Gaussian entries, and certain sparse matrices. For 1 < p r < ∞, the asymptotic normality, as n → ∞, of the appropriately centered and scaled norm ||An||_{r→p} is established. This is also shown to imply, as a corollary, asymptotic normality of the solution to the lp quadratic maxi- mization problem, also known as the lp Grothendieck problem for p> 2. Furthermore, a sharp l∞-approximation for the unique maximizing vector in the definition of ||An||_{r→p} is obtained, which may be of independent interest. In fact, the vector approximation result is shown to hold for a broad class of deterministic sequence of matrices having certain asymptotic expansion properties. The results obtained can be viewed as a generalization of the seminal results of Füredi and Komlós (1981) on asymptotic normality of the largest singular value of a class of symmetric random matrices, which corresponds to the special caser=p=2consideredhere. Inthegeneralcasewith1<pr<∞,thespectral methods are no longer applicable, which requires a new approach, involving a refined convergence analysis of a nonlinear power method and establishing a perturbation bound on the maximizing vector.

This is based on a joint work with Debankur Mukherjee (Georgia Tech) and Kavita Ramanan (Brown University).