{"id":357809,"date":"2017-01-25T13:59:25","date_gmt":"2017-01-25T21:59:25","guid":{"rendered":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/?post_type=msr-research-item&p=357809"},"modified":"2018-10-16T20:01:12","modified_gmt":"2018-10-17T03:01:12","slug":"anatomy-young-giant-component-random-graph","status":"publish","type":"msr-research-item","link":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/publication\/anatomy-young-giant-component-random-graph\/","title":{"rendered":"Anatomy Of A Young Giant Component In The Random Graph"},"content":{"rendered":"

We provide a complete description of the giant component of the Erd\\H{o}s-R\\’enyi random graph G<\/span>(<\/span>n<\/span>,<\/span>p<\/span>)<\/span><\/span><\/span><\/span> as soon as it emerges from the scaling window, i.e., for p<\/span>=<\/span>(<\/span>1<\/span>+<\/span>\u03f5<\/span>)<\/span>\/<\/span><\/span><\/span>n<\/span><\/span><\/span><\/span> where \u03f5<\/span>3<\/span><\/span>n<\/span>\u2192<\/span>\u221e<\/span><\/span><\/span><\/span> and \u03f5<\/span>=<\/span>o<\/span>(<\/span>1<\/span>)<\/span><\/span><\/span><\/span>.
\nOur description is particularly simple for \u03f5<\/span>=<\/span>o<\/span>(<\/span>n<\/span>\u2212<\/span>1<\/span>\/<\/span><\/span><\/span>4<\/span><\/span><\/span><\/span>)<\/span><\/span><\/span><\/span>, where the giant component C<\/span>1<\/span><\/span><\/span><\/span><\/span> is contiguous with the following model (i.e., every graph property that holds with high probability for this model also holds w.h.p. for C<\/span>1<\/span><\/span><\/span><\/span><\/span>). Let Z<\/span><\/span><\/span><\/span> be normal with mean 2<\/span>3<\/span><\/span>\u03f5<\/span>3<\/span><\/span>n<\/span><\/span><\/span><\/span> and variance \u03f5<\/span>3<\/span><\/span>n<\/span><\/span><\/span><\/span>, and let K<\/span><\/span><\/span><\/span> be a random 3-regular graph on 2<\/span>\u230a<\/span>Z<\/span>\u230b<\/span><\/span><\/span><\/span> vertices. Replace each edge of K<\/span><\/span><\/span><\/span> by a path, where the path lengths are i.i.d. geometric with mean 1<\/span>\/<\/span><\/span><\/span>\u03f5<\/span><\/span><\/span><\/span>. Finally, attach an independent Poisson(1<\/span>\u2212<\/span>\u03f5<\/span><\/span><\/span><\/span>)-Galton-Watson tree to each vertex.
\nA similar picture is obtained for larger \u03f5<\/span>=<\/span>o<\/span>(<\/span>1<\/span>)<\/span><\/span><\/span><\/span>, in which case the random 3-regular graph is replaced by a random graph with N<\/span>k<\/span><\/span><\/span><\/span><\/span> vertices of degree k<\/span><\/span><\/span><\/span> for k<\/span>\u2265<\/span>3<\/span><\/span><\/span><\/span>, where N<\/span>k<\/span><\/span><\/span><\/span><\/span> has mean and variance of order \u03f5<\/span>k<\/span><\/span>n<\/span><\/span><\/span><\/span>.
\nThis description enables us to determine fundamental characteristics of the supercritical random graph. Namely, we can infer the asymptotics of the diameter of the giant component for any rate of decay of \u03f5<\/span><\/span><\/span><\/span>, as well as the mixing time of the random walk on C<\/span>1<\/span><\/span><\/span><\/span><\/span>.<\/p>\n","protected":false},"excerpt":{"rendered":"

We provide a complete description of the giant component of the Erd\\H{o}s-R\\’enyi random graph G(n,p) as soon as it emerges from the scaling window, i.e., for p=(1+\u03f5)\/n where \u03f53n\u2192\u221e and \u03f5=o(1). Our description is particularly simple for \u03f5=o(n\u22121\/4), where the giant component C1 is contiguous with the following model (i.e., every graph property that holds […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"Wiley Subscription Services, Inc.","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"Random Structures & Algorithms","msr_number":"","msr_organization":"","msr_pages_string":"139-178","msr_page_range_start":"139","msr_page_range_end":"178","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"","msr_doi":"10.1002\/rsa.20342","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2010-09-15","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13546],"msr-publication-type":[193715],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-357809","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-computational-sciences-mathematics","msr-locale-en_us"],"msr_publishername":"Wiley Subscription Services, Inc.","msr_edition":"","msr_affiliation":"","msr_published_date":"2010-09-15","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"139-178","msr_chapter":"","msr_isbn":"","msr_journal":"Random Structures & Algorithms","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"357812","msr_publicationurl":"","msr_doi":"10.1002\/rsa.20342","msr_publication_uploader":[{"type":"file","title":"0906.1839v2","viewUrl":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-content\/uploads\/2017\/01\/0906.1839v2.pdf","id":357812,"label_id":0},{"type":"doi","title":"10.1002\/rsa.20342","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Jian Ding","user_id":0,"rest_url":false},{"type":"text","value":"Jeong Han Kim","user_id":0,"rest_url":false},{"type":"text","value":"Eyal Lubetzky","user_id":0,"rest_url":false},{"type":"user_nicename","value":"peres","user_id":33234,"rest_url":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=peres"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"article","related_content":[],"_links":{"self":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/357809","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/357809\/revisions"}],"predecessor-version":[{"id":416810,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/357809\/revisions\/416810"}],"wp:attachment":[{"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/media?parent=357809"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=357809"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=357809"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=357809"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=357809"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=357809"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=357809"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=357809"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=357809"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=357809"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=357809"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=357809"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/newed.any0.dpdns.org\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=357809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}