{"entities":{"Q2874667":{"pageid":2885387,"ns":120,"title":"Item:Q2874667","lastrevid":58043820,"modified":"2026-04-03T14:11:39Z","type":"item","id":"Q2874667","labels":{"en":{"language":"en","value":"Cores of random graphs are born Hamiltonian"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6327945"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$AB409B98-E142-444B-AAC4-184A07D477E4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"18ab120dc2264b9567728df4bd950655f3a1ada6","datavalue":{"value":{"text":"Cores of random graphs are born Hamiltonian","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2874667$52D92FF2-FE19-4957-A746-3C2EF94B879E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0666c071c25547426a2524204a5b2d42e192e676","datavalue":{"value":"1301.05205","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2874667$090CCC32-5562-49F3-B221-6B74DC33B91E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$7E9C97AB-D89C-4A6D-A181-96D99B92A955","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad23806f4e17358488195c971b467433ef000b50","datavalue":{"value":{"entity-type":"item","numeric-id":244997,"id":"Q244997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$5B6B0697-6B1D-4236-A073-A6870D7F4CF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"502bbb6d3842faa7531646862d34737b11134d06","datavalue":{"value":{"entity-type":"item","numeric-id":1584432,"id":"Q1584432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$AC87874C-7906-46F8-852C-8A14DBEB21B9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6e4c38f71acce3ef3ddbdbb0562f4d6caaf6f9d7","datavalue":{"value":{"time":"+2014-08-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2874667$73795BA5-449C-4A97-8D77-7852BC31FAB1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"169d8c57ab20cc6464309eeaef12f0e9ef9ddfbd","datavalue":{"value":"https://arxiv.org/abs/1303.3524","type":"string"},"datatype":"url"},"type":"statement","id":"Q2874667$8758FEC1-451B-4FEA-98B7-0A6EDFF97600","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2874667$98FDA8F9-86A2-4171-8778-7866010A45DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2874667$56BBEF8B-231A-49B4-AB48-61FFE542FEED","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"60cc40df955333b2d2e8b521693356b6b98d42de","datavalue":{"value":"6327945","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2874667$F23AD700-E38B-4632-A6BF-BC195C777284","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a007f205fba6b4e5e7502c3706dda8ed6a019ee9","datavalue":{"value":"random graph process","type":"string"},"datatype":"string"},"type":"statement","id":"Q2874667$2A093FD1-889B-41D3-B326-4F05F03BB424","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11335e722e6100937eebbae2788305e299658007","datavalue":{"value":"\\(k\\)-core","type":"string"},"datatype":"string"},"type":"statement","id":"Q2874667$DB637A85-1485-408F-B079-177BC28A465C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd53d393c376b85f274601d67e734a11b5e588d2","datavalue":{"value":"Hamiltonicity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2874667$DEFE424D-B807-4464-A44B-FB16D64AC052","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$D482D425-CB19-48D0-A4BB-5B88215BE37A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b7d4e1e57ec7a4cf80823991bf1476ff5b9e060b","datavalue":{"value":"W2057897835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2874667$40ACDEEB-65E0-4E4E-B921-8CC85BBC5086","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"649597edca6ec074c56f1ed3256da1b31873673d","datavalue":{"value":{"entity-type":"item","numeric-id":3288454,"id":"Q3288454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$D48B2825-636B-4A24-84A2-C6457532E0E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75f3e6a00720528a1dcbef8f2404f730f0310dcc","datavalue":{"value":{"entity-type":"item","numeric-id":4487074,"id":"Q4487074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$8EC0030C-7B94-4EE3-99EB-B10FAAE20B7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06d2b6c7fc1aba70943c3521f001c103ec62bad1","datavalue":{"value":{"entity-type":"item","numeric-id":869995,"id":"Q869995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$CFB35516-592C-40D5-A213-FC4071557AF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4be869fa8cf9f115f2345b8e4c83aa8fc1a856d","datavalue":{"value":{"entity-type":"item","numeric-id":3168446,"id":"Q3168446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$2A638659-C967-4BAC-BFA5-FF977421409C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8b7ee5f423238333301dba3b10a805e6405f34e","datavalue":{"value":{"entity-type":"item","numeric-id":3201078,"id":"Q3201078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$E2D6D0CD-9DDD-44DB-BA19-58E64A3D8AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5aebf69e66710244e7620c7cdd8eec692d23c174","datavalue":{"value":{"entity-type":"item","numeric-id":2930057,"id":"Q2930057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$2F07520F-B459-443E-A0DA-2C9D56D52C1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$595E5474-E93E-4DA9-BE9F-4FAE91D775E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e2b9568c4145086c32e2ce66e36cf795d993822","datavalue":{"value":{"entity-type":"item","numeric-id":3419611,"id":"Q3419611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$4B03F3A0-0CDF-4A18-A529-EFE5F2BFC765","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d157c280a264ec9dee94b4262ed61bb4fe489ed","datavalue":{"value":{"entity-type":"item","numeric-id":930680,"id":"Q930680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$E96446ED-A999-445F-B6A1-B806287E6B6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e11bf65cb6459492b00543657811c7c16e1dde47","datavalue":{"value":{"entity-type":"item","numeric-id":1055441,"id":"Q1055441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$76447642-CCE3-4224-8874-01F307DCA799","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"378f24257f5b1d9059ca37b6bf16ce16a94e1126","datavalue":{"value":{"entity-type":"item","numeric-id":3057066,"id":"Q3057066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$4C00DA03-33B7-4756-BADF-193AE14633F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50d5a83992d2ac7d76eabc8c4da5b4cc550e8e60","datavalue":{"value":{"entity-type":"item","numeric-id":1179277,"id":"Q1179277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$CC373CC7-960C-4E94-A626-6A7120438727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1d7351625a639ac36c9c8bba21d64d720874906","datavalue":{"value":{"entity-type":"item","numeric-id":4870540,"id":"Q4870540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$955D233F-D7C8-4CA0-A342-DEFA96FF4C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4737b04ff28c38c999126c8fbbafa9df257c84","datavalue":{"value":{"entity-type":"item","numeric-id":5311914,"id":"Q5311914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$DF0A4408-F44F-4572-91C7-F60659121D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1d0bad7ad40feeb0d7b02e4fb5736b947c07ee9","datavalue":{"value":{"entity-type":"item","numeric-id":1924140,"id":"Q1924140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$02FE59CB-9B82-447C-B353-B9756586C6E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c65e5b083f4f44d31025fb954ea1b19f8a45c8ad","datavalue":{"value":{"entity-type":"item","numeric-id":1223313,"id":"Q1223313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$FED9B1E9-D1B7-45D4-9E46-4C9D4988C03B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f24c604ce39608f300c8be48509169b53a18fa79","datavalue":{"value":{"entity-type":"item","numeric-id":2428631,"id":"Q2428631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$B040DE6C-315C-4429-82C0-83812EE9273B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59ce3dbcfb84aaf1081b167ddfb4634029cfc249","datavalue":{"value":{"entity-type":"item","numeric-id":5448993,"id":"Q5448993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$CA540CED-A49C-4C0E-9B59-4CD2C788EDCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfba955c32dc153431f5c99ab1d6a49daa930c11","datavalue":{"value":{"entity-type":"item","numeric-id":5785127,"id":"Q5785127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$CFE0B1E6-015A-4E75-9971-4F3FBDD465EC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8dc35f2085372e9af3ed96a78a5ac69f4c47c98e","datavalue":{"value":"10.1112/PLMS/PDU003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2874667$7FC83609-FCD8-4A35-B5B6-9923372ED19D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"05c75dfbfeb57f29a657af8520ed8349037c0a8a","datavalue":{"value":{"entity-type":"item","numeric-id":6486853,"id":"Q6486853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$6EBB3037-3301-495B-A953-283FFB006955","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"560ebd7884effeb56a3d677763c0b22aa341d646","datavalue":{"value":"The fundamental problem of establishing the threshold for Hamiltonicity in the Erd\u0151s-R\u00e9nyi random graph has attracted a lot of attention over the years. It is believed that in a typical random graph process \\(\\{G_t\\}_{t\\geq 0}\\) on \\(n\\) vertices (\\(G_0\\) is edgeless and \\(G_t\\) is obtained by adding a uniformly distributed new edge to \\(G_{t-1}\\)), for any fixed \\(k\\geq 3\\) the \\(k\\)-core of \\(G_t\\) (its unique maximal subgraph with minimum degree at least \\(k\\)) is Hamiltonian upon creation with high probability (w.h.p.) and admits \\(\\lfloor (k-1)/2\\rfloor\\) edge-disjoint Hamilton cycles (plus a perfect matching when \\(k\\) is even). The first appearance of a \\(k\\)-core involves a discontinuous first-order phase transition and its size jumps from zero to linear in the number of vertices w.h.p. However, even the asymptotic threshold for the core to contain a (single) Hamilton cycle remained open. This threshold is believed to fall roughly between \\(k/n\\) and \\(2k^3/n\\).NEWLINENEWLINENEWLINE The authors establish that for any fixed \\(k\\geq 15\\), w.h.p. the \\(k\\)-core of \\(G_t\\) is Hamiltonian upon creation by applying a novel sprinkling recipe, hinging on conditioning on the future before creation of any \\(k\\)-core, and combining this method with the classical rotation-extension technique, thereby reducing Hamiltonicity to the task of verifying certain graph properties. Having settled the issue of Hamiltonicity in \\(k\\)-cores for \\(k\\geq 15\\), they then turn their attention to packing Hamilton cycles and prove that for large enough fixed \\(k\\), w.h.p. the \\(k\\)-core gives rise to \\(\\lfloor (k-3)/2\\rfloor\\) edge-disjoint Hamilton cycles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2874667$3219BC8D-C095-4862-86BD-FA72F21A9519","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d24973f79b07de5f29aac72f50f10f2643a18f1c","datavalue":{"value":{"entity-type":"item","numeric-id":315658,"id":"Q315658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2874667$02E25B8B-D46B-42C7-9FBD-6C4EAA259AE9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7885fd0fc01ead3885f1e2b6a09173624a0fca86","datavalue":{"value":{"entity-type":"item","numeric-id":2338643,"id":"Q2338643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f513893827000bcfc5ad47f120b6486b46c269a","datavalue":{"value":{"amount":"+0.8301401138305664","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2874667$7966330E-B8CA-4EE9-9033-E7BB0BCF10C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfdfc8da4a27e24a0e7ea3b90118639b47913870","datavalue":{"value":{"entity-type":"item","numeric-id":1924140,"id":"Q1924140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"88fd99c3c0a1f7bd2c5b959fbc8a1fab313b46eb","datavalue":{"value":{"amount":"+0.8063944578170776","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2874667$C893B3AC-4F83-4B13-88FB-229BC907B906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d421d9beb91e49011f94c60ccfa96361f729771","datavalue":{"value":{"entity-type":"item","numeric-id":5229343,"id":"Q5229343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bedc22c273acdd5dae3afd832565a05620ea0ba","datavalue":{"value":{"amount":"+0.8042582273483276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2874667$6E2DCA5A-7B50-4E75-A155-0719D0084B2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e20a4c735aebcabcbf8f303f7d5e43e566242bc","datavalue":{"value":{"entity-type":"item","numeric-id":5202206,"id":"Q5202206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4aac6c39695bcc8381cf4ae702bbcafe7dd7861","datavalue":{"value":{"amount":"+0.7961838245391846","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2874667$C67B0423-D848-4FF0-86E9-E7AA8EE397BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d20d07ed9c920303d3db36824747269600caa388","datavalue":{"value":{"entity-type":"item","numeric-id":948883,"id":"Q948883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fab4ca56a53a7309e9a6c751d044d155b37635bf","datavalue":{"value":{"amount":"+0.787406325340271","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2874667$20C0660B-BE37-4034-9A7D-91559E916083","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2874667","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2874667"}}}}}