# Random Apollonian Networks

Simulation of a Random Apollonian Networks (RANs)

In this work, we analyze fundamental properties of Random Apollonian Networks, a popular random graph model which generates planar graphs with power law properties. Specifically, we analyze the following properties:

• the degree distribution,
• the $k$ largest degrees, the $k$ largest eigenvalues ($k$ is a constant),
• the diameter.

# Rainbow Connectivity

Random regular graphs. An edge colored graph $G$ is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this work we study the rainbow connection of the random $r$-regular graph $G=G(n,r)$ of order~$n$, where $r\ge 4$ is a constant. We prove that with probability tending to one as $n$ goes to infinity the rainbow connection of $G$ satisfies $rc(G)=O(\log n)$, which is best possible up to a hidden constant.

Note: The optimal result for 3-regular random graphs was proved by Michael Molloy.

Random Erdős–Rényi graphs.  We prove optimal results for rainbow connectivity at the connectivity threshold.

# Motif Expanders

In our work “Scalable motif-aware community detection” we introduce the concept of triangle expanders, that serves as the theoretical basis of the theory behind motif based clustering.