Maximum independent sets on random regular graphs

Author(s): Ding, Jian; Sly, Allan M.; Sun, Nike

Download

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr19m5q

Full metadata record

DC Field	Value	Language
dc.contributor.author	Ding, Jian	-
dc.contributor.author	Sly, Allan M.	-
dc.contributor.author	Sun, Nike	-
dc.date.accessioned	2019-04-05T20:00:30Z	-
dc.date.available	2019-04-05T20:00:30Z	-
dc.date.issued	2016	en_US
dc.identifier.citation	Ding, Jian, Sly, Allan M., Sun, Nike. (2016). Maximum independent sets on random regular graphs. ACTA MATHEMATICA, 217 (263 - 340). doi:10.1007/s11511-017-0145-9	en_US
dc.identifier.issn	0001-5962	-
dc.identifier.uri	http://arks.princeton.edu/ark:/88435/pr19m5q	-
dc.description.abstract	We determine the asymptotics of the independence number of the random d-regular graph for all d≥d0. It is highly concentrated, with constant-order fluctuations around nα∗−c∗logn for explicit constants α∗(d) and c∗(d). Our proof rigorously confirms the one-step replica symmetry breaking heuristics for this problem, and we believe the techniques will be more broadly applicable to the study of other combinatorial properties of random graphs.	en_US
dc.format.extent	263 - 340	en_US
dc.language	English	en_US
dc.language.iso	en_US	en_US
dc.relation.ispartof	ACTA MATHEMATICA	en_US
dc.rights	Author's manuscript	en_US
dc.title	Maximum independent sets on random regular graphs	en_US
dc.type	Journal Article	en_US
dc.identifier.doi	doi:10.1007/s11511-017-0145-9	-
dc.date.eissued	2016	en_US
dc.identifier.eissn	1871-2509	-
pu.type.symplectic	http://www.symplectic.co.uk/publications/atom-terms/1.0/journal-article	en_US

Files in This Item:

File	Description	Size	Format
1310.4787.pdf		1.3 MB	Adobe PDF	View/Download