Bipodal Structure in Oversaturated Random Graphs. (24th December 2016)

• Record Type: Journal Article
• Authors: Kenyon, Richard; Radin, Charles; Ren, Kui; Sadun, Lorenzo
• Is Part Of: International mathematics research notices. Volume 2018:Number 4(2018)
• Page Start: 1009
• Page End: 1044
• Publication Date: 2016-12-24
• Subjects: Mathematics -- Periodicals; 510
• DOI: 10.1093/imrn/rnw261
• Languages: English
• ISSNs: 1073-7928

Abstract

Abstract: We study the asymptotics of large simple graphs directly constrained by the limiting subgraph densities of edges and of an arbitrary fixed graph $H$ . We prove that, for all but finitely many values of the edge density, if the density of $H$ is constrained to be slightly higher than that for the corresponding Erdős–Rényi graph, the typical large graph is bipodal with parameters varying analytically with the densities. Asymptotically, the parameters depend only on the degree sequence of $H$ .