Pawel PRALAT - Asistant Director Communication systems
Date: - Location: Eurecom
Abstract: We study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with m random vertices selected with probabilities proportional to their current degrees. (Constant m is the only parameter of the model.) We prove that if m => 1260, then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that m => 29500. One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are ``older'' (i.e. are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting---sometimes called uniform attachment---in which vertices are added one by one and each vertex connects to $m$ older vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version. Bio: Dr. Pawel Pralat is an Assistant Director for Industry Liaison at the Fields Institute for Research in Mathematical Sciences and an Associate Professor at Ryerson University. His main research interests lie in graph theory with applications to real-world self-organizing networks such as the web graph or social networks. He is interested in both modelling and mining of complex networks with emphasis on connections to Big Data research questions. Since 2006, he has written 130+ papers with 100+ collaborators. The main strength of Dr. Pralat is his broad background, skills, tools he uses, and research interests. He is trained both in (theoretical and applied) computer science as well as mathematics (M.Eng. and M.A.Sc. in CS, Ph.D. in Mathematics and CS), has strong programming skills, gained through experience in collaboration with the private sector (Microsoft Research, Google, Motorola, Facebook, BlackBerry, etc.) as well as the government (Tutte Institute for Mathematics and Computing).
