Ph.D. Public Lecture (Math) - Mohabat Tarkeshian

"Random graphs with a Markov flavour"

The theory of random graphs began in 1959 with seminal work by Erdős and Rényi. One of their first models described the probability of a graph occurring on a fixed set of vertices. Edges in this model are thought of as independent. That is, relationships between vertices are independent of relationships between other vertices. We add a Markov “twist” to this story by assuming local dependencies between relationships in a random graph. We do this by encoding a neighbourhood structure on a graph and imposing that dependencies arise in a random graph only when those relationships have overlapping neighbourhoods. We then relate this to general probability theory by characterizing when such a random graph model has the strongly Rayleigh property, a property that implies negative dependence. This is analyzed using a well-developed dictionary between probability distributions and polynomials, with the strongly Rayleigh property acting as the analogue of multivariate polynomial stability.