Fox et al introduced the model of c-closed graphs, a distribution-free model motivated by motivated by one of the most universal signatures of social networks, triadic closure. Previous literature shows that the number of maximal cliques and maximal complete bipartite graphs in any c-closed graph on n vertices is always polynomial in n. In this work, we enumerate maximal blow-ups of an arbitrary graph H in c-closed graphs. We prove that given any finite graph H, the number of maximal blow-ups of H in any c-closed graph on n vertices always at most polynomial in n. When considering induced blow-ups of a finite graph H, we provide a characterization of graphs H when the bound is always polynomial in n. A similar general theorem is also proved when H is infinite.
Enumerating patterns in Social Networks in A Distribution-Free Model
Fan Wei, Duke University
Authors: Gabbie Bourla, Fan Wei
2023 AWM Research Symposium
Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]