{"entities":{"Q1924140":{"pageid":1934882,"ns":120,"title":"Item:Q1924140","lastrevid":73923312,"modified":"2026-04-14T17:44:40Z","type":"item","id":"Q1924140","labels":{"en":{"language":"en","value":"Sudden emergence of a giant \\(k\\)-core in a random graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 934807"}},"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":"Q1924140$031B8789-856A-473A-810F-F926523326CE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e18bb9b7c52b2ded2eb6f2acdbc37ca02b6f6ab","datavalue":{"value":{"text":"Sudden emergence of a giant \\(k\\)-core in a random graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1924140$C2630E74-F0B2-46F6-925B-B68121C75323","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0b063f3e4b9097bc49f7db51acfcdcb7daca3152","datavalue":{"value":"0860.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924140$F0CDF056-7534-4935-A2BD-BD3244B3C8AB","rank":"normal"}],"P16":[{"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":"Q1924140$339EE88B-447F-4985-AD31-6B3C69F93E97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dc5c75446f79c1451425b519e32f93a97b58ceab","datavalue":{"value":{"entity-type":"item","numeric-id":1296593,"id":"Q1296593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924140$DF8B04FE-8F9E-44DA-A2B5-4BF00A778316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5614d963e1142d1d3e84430bb23fe04069b1019","datavalue":{"value":{"entity-type":"item","numeric-id":590239,"id":"Q590239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924140$07C922C3-51CB-4BDA-915D-B85654D23707","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924140$886BB355-F763-4D55-849B-DF794FA16745","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"87c3e3b2ec497a54777723f516b57d715fefe115","datavalue":{"value":{"time":"+1996-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1924140$4EF60835-E216-4162-9AF7-9927997DFEBA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"24ef0e4903f7bc8f7ecf7cbe4d443d01ed785625","datavalue":{"value":"The \\(k\\)-core of a graph is the largest subgraph of minimum degree \\(\\geq k\\). Fix \\(\\delta\\in(0,1)\\), and let \\(k\\geq 3\\); there is a \\(\\gamma_k\\) and a \\(p_k\\) such that the following is true. For a random graph of \\(n\\) edges and \\(m\\) vertices, when \\(m<\\gamma_kn-n^{1-\\delta}\\), the \\(k\\)-core a. s. has \\(o(n)\\) vertices, while if \\(m>\\gamma_k+n^{1-\\delta}\\), the \\(k\\)-core a. s. has at least \\(p_kn+o(n)\\) vertices. And it's unlikely that you'll catch the graph in transition: even if \\(|\\gamma_kn-m|\\leq n^{1-\\delta}\\), such a graph a. s. has a \\(k\\)-core of \\(o(n)\\) edges or \\(p_k(n)n+o(n)\\) edges.   The difficult proof is in two parts. In the first, the authors consider a process that successively deletes edges adjacent to vertices of degree \\(<k\\); they link this process with a parameter, and show that a random process based on the parameter alone simulates the graph process and is nearly Markov. In the second, they use this process to estimate the size of the \\(k\\)-cores.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924140$9D3A0066-EC6A-48E3-99D4-84CB757BB45B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924140$88951BBD-C0BF-4973-ADC7-F0B92421E721","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"67837a78943bd383f9574019b94c82f2cd89ad48","datavalue":{"value":"934807","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924140$1B71BEDD-6DE0-46F2-B074-949E08B46C3E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11335e722e6100937eebbae2788305e299658007","datavalue":{"value":"\\(k\\)-core","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924140$A3D20D9A-22CA-44F9-A557-0BB83C7A14F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e87bb1aed89f5da6ee5d1aa38eb687932a17c03","datavalue":{"value":"subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924140$4339B15E-F4E8-49FC-9D47-550E5DE85DC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924140$466E1511-98A9-457B-B6A3-56874F5B52D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924140$93D915B1-F24A-4DCF-97B8-703C6BA67105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa7d90ca27398ef878c4a8eef1e2bc72817674e8","datavalue":{"value":"random process","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924140$CE4B059E-92A3-4BBF-8299-180D2CB91715","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4c2e453a383fe1e064f27e4ca3ff49f8a1646b9","datavalue":{"value":{"entity-type":"item","numeric-id":587174,"id":"Q587174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924140$9A11EA2C-3855-47B2-ACB7-92BB9DAE6BB6","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":"Q1924140$6BE10E75-9484-4002-B843-0C3F0B77F952","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6c2566e93bce859bd487f5d47ed087ca9ba9d608","datavalue":{"value":"https://doi.org/10.1006/jctb.1996.0036","type":"string"},"datatype":"url"},"type":"statement","id":"Q1924140$6E9B3BC6-248A-4E4A-86BF-3C05657F4339","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3adaa4a41f9af1f0445ef57c53554fe4de06e818","datavalue":{"value":"W2065663455","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924140$9F62BC4B-5F65-41F9-9098-E63EC3C498A4","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f06b5f5a686e88a39fed85799fd28ee435bd5437","datavalue":{"value":"Q106185259","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924140$B169912A-968A-4748-8C2C-184CF65B18FB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"27cadbe9d57b50fc968571abf637e7ff697ffd66","datavalue":{"value":"10.1006/JCTB.1996.0036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924140$53EA4BA3-29B3-4857-9A35-FAE9417699FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3f07ec8cd62a99e99354f769a4e731ed25b3f77","datavalue":{"value":{"entity-type":"item","numeric-id":1179277,"id":"Q1179277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"301812c9f8b625b12b0a7a876d047da355e2168b","datavalue":{"value":{"amount":"+0.8661516904830933","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":"Q1924140$0BC438ED-ADFF-4024-940E-CE7A4C3EDE98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c49f51cd03e91c3dc3a7015a2b8ccb67644682ba","datavalue":{"value":{"entity-type":"item","numeric-id":930680,"id":"Q930680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9738534c42ed514c487765b92fb796f4f6fc9351","datavalue":{"value":{"amount":"+0.8649063110351562","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":"Q1924140$A7874111-1436-4AC9-B5ED-E489C02140E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c63eee59f9bd6d89f69a6095c0c671a8ac8a2db","datavalue":{"value":{"entity-type":"item","numeric-id":2312608,"id":"Q2312608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6923216ff52f82a08c4e1c3627a9d1959c7c01c","datavalue":{"value":{"amount":"+0.8633202910423279","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":"Q1924140$EC3D007B-1733-4DBB-8D66-0035BD7FE899","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"c39a117a349789e54237c0a3254f5a10c0a6517e","datavalue":{"value":{"entity-type":"item","numeric-id":6830565,"id":"Q6830565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924140$BB4AB4F5-A6DA-4FDA-945B-56005DC03B5D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sudden emergence of a giant \\(k\\)-core in a random graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sudden_emergence_of_a_giant_%5C(k%5C)-core_in_a_random_graph"}}}}}