{"entities":{"Q2428631":{"pageid":2439374,"ns":120,"title":"Item:Q2428631","lastrevid":73402020,"modified":"2026-04-14T15:47:45Z","type":"item","id":"Q2428631","labels":{"en":{"language":"en","value":"On the threshold for \\(k\\)-regular subgraphs of random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6028291"}},"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":"Q2428631$9BE89442-A514-4765-96C2-4FE96185F000","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1121f138791032ff8df3f0590498999daf851162","datavalue":{"value":{"text":"On the threshold for \\(k\\)-regular subgraphs of random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2428631$686258D8-AEC3-4CA8-A68E-05CA3E055AF1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1b41c6d2183132d130910a2bf73a7cad141abe39","datavalue":{"value":"1263.05099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428631$3C12B5AB-39B4-4C98-9DDF-01BCBD85173E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6197eba997efc9b4d1afb25ce947d80519065cc","datavalue":{"value":{"entity-type":"item","numeric-id":265089,"id":"Q265089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$BE66CD10-4535-4EA6-9D44-63E5DAF1C6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c84290e2aa59f5e72197dc6c42e23718498784e5","datavalue":{"value":{"entity-type":"item","numeric-id":704840,"id":"Q704840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$C20CADD9-5DE8-4230-BDB5-DE8CE0EEE57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8444f9fccd215f879b6fe3e03b6423c5e05bd6c1","datavalue":{"value":{"entity-type":"item","numeric-id":311563,"id":"Q311563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$E993E94D-5757-49E1-A2DE-9FB8FDD72673","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$2B607C1B-5D3B-4EF1-A4ED-F37D1C0829E1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"52b04daa1d703ea977748e4d42defef3819c2dd9","datavalue":{"value":{"time":"+2012-04-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2428631$03AB06CD-1099-43E2-AD4E-ABBE15F0C29F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ebd6de6de67d67266597f5d58bd1d8156926634c","datavalue":{"value":"https://arxiv.org/abs/0706.1103","type":"string"},"datatype":"url"},"type":"statement","id":"Q2428631$1E94B406-AAC6-43BA-8D16-1B42CB87A2E7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"14eefe07f644e0f89f1bbe61fb4f02443cb76df3","datavalue":{"value":"The random graph model used in this paper is Erd\u0151s-R\u00e9nyi model \\(\\mathcal{G}(n,p)\\). The \\(k\\)-core of a graph \\(G\\) is the unique largest subgraph of \\(G\\) of minimum degree at least \\(k\\). A \\(k\\)-factor of a graph is a spanning \\(k\\)-regular subgraph, and a graph is \\(k\\)-factor-critical if, whenever one deletes a vertex from the graph, one obtains a graph which has a \\(k\\)-factor. An event which occurs with probability tending to 1 as \\(n \\to \\infty\\) is said to be a.a.s. The following main theorem is proved in this paper. There exists an absolute constant \\(k_0\\) such that for \\(k \\geq k_0\\) and constant \\(c > c_{k+2}\\) with \\(c < k + 2\\sqrt{k \\log k}\\), the \\((k+2)\\)-core of a random graph \\(\\mathcal{G}(n,c/n)\\) is a.a.s. nonempty and either contains a \\(k\\)-factor or is \\(k\\)-factor-critical. The constant \\(c_{k+2}\\) was first defined in \\textit{B.~Pittel}, \\textit{J.~Spencer} and \\textit{N.~Wormald} [J. Comb. Theory, Ser. B 67, No. 1, 111--151 (1996; Zbl 0860.05065)]. A corollary of the main theorem is the following statement. There esixts an absolute constant \\(k_0\\) such that for \\(k \\geq k_0\\), \\(\\varepsilon > 0\\) and any function \\(p(n) > c_{k+2}(1+\\varepsilon)/n\\), the random graph \\(\\mathcal{G}(n,p)\\) a.a.s. has a \\(k\\)-regular subgraph. Two conjectures are proposed in this paper. (i) There is a sharp threshold for the appearance of a \\(k\\)-regular graph in \\(\\mathcal{G}(n,p)\\). (ii) The \\((k+1)\\)-core of a random graph, when it is a.a.s. nonempty, contains a \\(k\\)-factor or is \\(k\\)-factor critical a.a.s.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428631$1FFD4B0D-95FC-4FB3-BAF6-8D57E2ED133A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428631$29B8FF4D-EB63-4348-9DA7-6D85EE217405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428631$8E78F428-CD73-4A21-BBF5-18368505F8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428631$BC1E9831-DB80-4112-835F-5675FBE7AC05","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cdb4115a9787f39b779bd3d9a9d4c1f81ad533aa","datavalue":{"value":"6028291","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428631$8E580C14-587C-4FCC-B749-5CDC480FACAD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae291a9f618c2c0938c719ae48bddfe3ecb7e7c","datavalue":{"value":"regular subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428631$FA8DF6F3-F62D-4CFE-B114-5A2EE0448F1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1e9df5f6f5000b0a9065b89a898b5d7f1ccfbfe","datavalue":{"value":"threshold","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428631$293D0DC8-5E57-41AE-A756-E633FD61403E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428631$DF82A6A8-CC82-4150-89EA-D2F325AAF7AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11335e722e6100937eebbae2788305e299658007","datavalue":{"value":"\\(k\\)-core","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428631$D5E3CB7F-C14F-4193-9874-985A2456010C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"157da90b3e36e1d11ade3292cb5de76a538a9b21","datavalue":{"value":"\\(k\\)-regular graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428631$540857CA-3EC9-44BA-B6E9-C85F35DE30CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c6b62c4e1e37b4402a1dbc53aff7c0416f8ad6f","datavalue":{"value":"\\(k\\)-factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428631$D1A24BDE-6E00-43F0-B264-E7CC501BEF05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee1c7455ee1557341be04cbd560b34ae13b5e406","datavalue":{"value":"\\(k\\)-factor-critical","type":"string"},"datatype":"string"},"type":"statement","id":"Q2428631$FA50CD83-B901-4BC9-8804-D60F4058F96B","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":"Q2428631$64C4B150-9421-486E-90F5-B1D973A33877","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bc837ce7241a7e81388e59c64a715c6d3d577770","datavalue":{"value":"W1966530078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428631$3E3AD1EB-DAF2-4B10-A106-42FD46A4DCB5","rank":"normal"}],"P223":[{"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":"Q2428631$1349FCF4-D914-4019-B4D4-C3360C52582F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4e981e5ad74ea0aeb3e133876532a6ae35a6d95","datavalue":{"value":{"entity-type":"item","numeric-id":5486304,"id":"Q5486304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$AD1867AA-FD7A-4D45-9624-FBCEFB842E6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20c8e2b620b70284add04eba77a33880e98a9ba4","datavalue":{"value":{"entity-type":"item","numeric-id":2930052,"id":"Q2930052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$FEE86E7C-0206-47F1-80F6-D243180EE1EA","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":"Q2428631$3803EAD2-B8DE-4C13-9C00-EBDC68D2A86D","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":"Q2428631$B3C7C87D-12EB-44E0-91E7-84A6309EAA8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccfce0413399ef6993e3b2ebbe302a214cfdaf20","datavalue":{"value":{"entity-type":"item","numeric-id":910415,"id":"Q910415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$05DFD58E-171B-4261-9C1F-175261C8FB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dcb8516baf05df7a49cb12b5fe52c39e4d886b8","datavalue":{"value":{"entity-type":"item","numeric-id":4796724,"id":"Q4796724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$BABA6CC1-6110-48C5-803D-0D00B42B2922","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":"Q2428631$A17F6955-27F5-4CD8-8D13-6A228257CFF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$59BE4A38-D720-4081-A325-0BC463B0E11F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c50fcb0bc33926d8ab954eac8aaa4e4abdf172e","datavalue":{"value":{"entity-type":"item","numeric-id":5491016,"id":"Q5491016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$0DCC3B10-8341-437B-AA56-0302DAF0D9B9","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":"Q2428631$2C17E8A7-4587-45AF-AE3C-AEAE14CD282D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0f4e7516daa6d4014d6dbd7077864aea96730aa","datavalue":{"value":{"entity-type":"item","numeric-id":5826303,"id":"Q5826303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2428631$18AD214A-5877-4CA1-9311-4AE3318D5010","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d673d0f2e3b585de6a4e30a84e9d1109cdfefa48","datavalue":{"value":"10.1007/S00493-011-2545-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2428631$0E133B52-655E-43B3-AA21-FDAEA06D3214","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"557cbf8508fe0e93cd2829b4c372f7007c229441","datavalue":{"value":{"entity-type":"item","numeric-id":5486304,"id":"Q5486304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89d779f4dd16b92cb2987ec9f875c8e2df7bdc0e","datavalue":{"value":{"amount":"+0.9118698239326476","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":"Q2428631$5C736F18-3726-405C-B0A5-74798AA01C41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"260aef4113668a9fbad31d453cc987a354177a93","datavalue":{"value":{"entity-type":"item","numeric-id":1985447,"id":"Q1985447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9fe9a699562fcad977b528b41e5a2788716d811","datavalue":{"value":{"amount":"+0.909219205379486","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":"Q2428631$5A5F3B76-05E6-43C8-9D77-51AAF56315A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21c7e1a97d4fd6b80659973f4627d8c47bbcd026","datavalue":{"value":{"entity-type":"item","numeric-id":3168446,"id":"Q3168446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ca1a1d76efa8c37a4822b0a6e126ba4e6afbf88","datavalue":{"value":{"amount":"+0.8997365832328796","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":"Q2428631$27788EF1-6800-4288-A985-5611EEDBA4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a66ad7eaeada8ff03f0123c0250d05e0b6366fa1","datavalue":{"value":{"entity-type":"item","numeric-id":2841681,"id":"Q2841681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1b7567827c934228d63ab947faffea0e94e3c0b","datavalue":{"value":{"amount":"+0.8717766404151917","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":"Q2428631$6AD86D0D-4B28-4E6F-A10A-36BB867D79ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a42177d8c9b476797ab1499f6a90aba8e9158e0f","datavalue":{"value":{"entity-type":"item","numeric-id":5418809,"id":"Q5418809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e86a9633181a10adac7aaaf0293f28f3f9be8aeb","datavalue":{"value":{"amount":"+0.843616247177124","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":"Q2428631$F621B16E-4115-4F39-826E-10DEEE8DCB94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the threshold for \\(k\\)-regular subgraphs of random graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_threshold_for_%5C(k%5C)-regular_subgraphs_of_random_graphs"}}}}}