Probability and statistics seminar: On 1-independent random graphs

  • Date: –11:15
  • Location: Ångströmlaboratoriet, Lägerhyddsvägen 1 64119
  • Lecturer: Victor Falgas-Ravry, Umeå universitet
  • Organiser: Matematiska institutionen
  • Contact person: Xing Shi Cai
  • Seminarium

Abstract: Let H be a connected graph. The p-random graph Hp is obtained by including each edge of H at random with probability p, independently of all the rest. The connectivity properties of Hp have been widely studied in random graph theory (in particular when H=Kn and Hp is the Erdős-Rényi random graph model) and in percolation theory (in particular when H is the square integer lattice ℤ2).

In this talk, I will be interested in studying the same connectivity properties but in a different class of random graph models, for which there may be some local dependencies between the edges. Formally, a 1-independent model (1-ipm) on H is a probability measure μ on the subgraphs of H such that in a μ-random graph Gμ, events supported on disjoint vertex-sets are independent. 

Consider a 1-ipm Gμ on H in which each edge is present with probability at least p. If H is finite, what can we say about the probability that Gμ is connected? If H is infinite, what can we say about the probability that Gμ contains an infinite connected component? I will report some recent (modest) progress on these questions and, time allowing, I will discuss some of the many open problems in the area.

Joint work with A. Nicholas Day and Robert Hancock.