Geodesic
The Largest Component in Critical Random Intersection Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 921-946.

Voir la notice de l'article provenant de la source Library of Science

In this paper, through the coupling and martingale method, we prove the order of the largest component in some critical random intersection graphs is n^2/3 with high probability and the width of scaling window around the critical probability is n^−1/3; while in some graphs, the order of the largest component and the width of the scaling window around the critical probability depend on the parameters in the corresponding definition of random intersection graphs. Our results show that there is still an “inside” phase transition in critical random intersection graphs.
Keywords: critical random intersection graph, largest component, scaling window 
@article{DMGT_2018_38_4_a4,
     author = {Wang, Bin and Wang, Longmin and Xiang, Kainan},
     title = {The {Largest} {Component} in {Critical} {Random} {Intersection} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {921--946},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a4/}
}
TY  - JOUR
AU  - Wang, Bin
AU  - Wang, Longmin
AU  - Xiang, Kainan
TI  - The Largest Component in Critical Random Intersection Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 921
EP  - 946
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a4/
LA  - en
ID  - DMGT_2018_38_4_a4
ER  - 
%0 Journal Article
%A Wang, Bin
%A Wang, Longmin
%A Xiang, Kainan
%T The Largest Component in Critical Random Intersection Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 921-946
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a4/
%G en
%F DMGT_2018_38_4_a4
Wang, Bin; Wang, Longmin; Xiang, Kainan. The Largest Component in Critical Random Intersection Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 921-946. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a4/

[1] M. Behrisch, Component evolution in random intersection graphs, Electron. J. Combin. 14 (2007) #R17.

[2] R. Durrett, Probability: Theory and Examples, Fourth Edition (Cambridge University Press, New York, 2010). doi:10.1017/CBO9780511779398

[3] Ch. Efthymiou and P.G. Spirakis, Sharp thresholds for Hamiltonicity in random intersection graphs, Theoret. Comput. Sci. 411 (2010) 3714–3730. doi:10.1016/j.tcs.2010.06.022

[4] J.A. Fill, E.R. Scheinerman and K.B. Singer-Cohen, Random intersection graphs when m = ω( n ): An equivalence theorem relating the evolution of G ( n,m, p ) and G ( n, p ) models, Random Structures Algorithms 16 (2000) 156–176. doi:10.1002/(SICI)1098-2418(200003)16:2h156::AID-RSA3i3.0.CO;2-H

[5] S. Janson, T. Łuczak and A. Ruciński, Random Graphs (John Wiley & Sons, New York, 2000). doi:10.1002/9781118032718

[6] M. Karoński, E.R. Scheinerman and K.B. Singer-Cohen, On random intersection graphs: The subgraph problem, Combin. Probab. Comput. 8 (1999) 131–159. doi:10.1017/S0963548398003459

[7] A.N. Lagerås and M. Lindholm, A note on the component structure in random intersection graphs with tunable clustering, Electron. J. Combin. 15 (2008) #N10.

[8] A. Nachmias and Y. Peres, Component sizes of the random graph outside the scaling window, ALEA Lat. Am. J. Probab. Math. Stat. 3 (2007) 133–142.

[9] A. Nachmias and Y. Peres, Critical random graphs: Diameter and mixing time, Ann. Probab. 36 (2008) 1267–1286. doi:10.1214/07-AOP358

[10] A. Nachmias and Y. Peres, The critical random graph, with martingales, Israel J. Math. 176 (2010) 29–41. doi:10.1007/s11856-010-0019-8

[11] A. Nachmias and Y. Peres, Critical percolation on random regular graphs, Random Structures Algorithms 36 (2010) 111–148. doi:10.1002/rsa.20277

[12] K. Rybarczyk, Equivalence of a random intersection graph and G (n, p), Random Structures Algorithms 38 (2011) 205–234. doi:10.1002/rsa.20356

[13] K. Rybarczyk, Sharp threshold functions for random intersection graphs via a coupling method, Electron. J. Combin. 18 (2011) #P36.

[14] D. Stark, The vertex degree distribution of random intersection graphs, Random Structures Algorithms 24 (2004) 249–258. doi:10.1002/rsa.20005

[15] K.B.Singer, Random Intersection Graphs (Ph.D. Thesis, John Hopkins Univresity, 1995).