首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Asymptotics in percolation on high‐girth expanders
Authors:Michael Krivelevich  Eyal Lubetzky  Benny Sudakov
Abstract:We consider supercritical bond percolation on a family of high‐girth urn:x-wiley:rsa:media:rsa20903:rsa20903-math-0001‐regular expanders. The previous study of Alon, Benjamini and Stacey established that its critical probability for the appearance of a linear‐sized (“giant”) component is urn:x-wiley:rsa:media:rsa20903:rsa20903-math-0002. Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant and its 2‐core at any urn:x-wiley:rsa:media:rsa20903:rsa20903-math-0003. It was further shown in the previous study that the second largest component, at any urn:x-wiley:rsa:media:rsa20903:rsa20903-math-0004, has size at most urn:x-wiley:rsa:media:rsa20903:rsa20903-math-0005 for some urn:x-wiley:rsa:media:rsa20903:rsa20903-math-0006. We show that, unlike the situation in the classical Erd?s‐Rényi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size urn:x-wiley:rsa:media:rsa20903:rsa20903-math-0007 for urn:x-wiley:rsa:media:rsa20903:rsa20903-math-0008 arbitrarily close to 1. Moreover, as a by‐product of that construction, we answer negatively a question of Benjamini on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, for example, the existence of a linear path.
Keywords:bond percolation  high‐girth expanders  giant component  component sizes
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号