{"entities":{"Q6930157":{"pageid":21084268,"ns":120,"title":"Item:Q6930157","lastrevid":84122990,"modified":"2026-05-10T15:04:22Z","type":"item","id":"Q6930157","labels":{"en":{"language":"en","value":"Decomposing random regular graphs into stars"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8093421"}},"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":"Q6930157$A3CA9037-4942-45DA-9D09-46634B862959","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6115920e55ec14ac26c630b83a0945f0c88d1529","datavalue":{"value":{"text":"Decomposing random regular graphs into stars","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6930157$FDF3362F-4F12-4198-AB80-15BEA00B0F88","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c4c2b8c246500aeefb65e125f536345f61ef4862","datavalue":{"value":"10.1016/J.EJC.2025.104216","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6930157$6286372A-5EF7-41CC-89ED-FE6F46EDDBD3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"225e476b91ecf5346e6f0e17e96dd007c71cfacf","datavalue":{"value":{"entity-type":"item","numeric-id":299040,"id":"Q299040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$C7233766-F445-4F23-B943-87E5751FF407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4e5fed75436711fae9c159f3931462760a8b85f","datavalue":{"value":{"entity-type":"item","numeric-id":311512,"id":"Q311512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$1B0F9A89-4798-4E72-BE2C-22AE8E192DF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9426ba06d2b9f00c542c81e125cce17b72d38d0","datavalue":{"value":{"entity-type":"item","numeric-id":287792,"id":"Q287792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$BB550C33-E2A2-464D-92B4-D3BA885D7A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9789bec085738fbdfa502ed903d619f413616619","datavalue":{"value":{"entity-type":"item","numeric-id":299041,"id":"Q299041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$9EA652AC-6E67-4161-89C1-23196F796BE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"231702fbc5a30e710ffb4eed2c1114ae9b9221ef","datavalue":{"value":{"entity-type":"item","numeric-id":273166,"id":"Q273166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$31DC2912-AE44-4818-BA1C-CE80090EEBF8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$5966EC1C-F8A1-4674-93A4-78029D238D60","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89702df27b41bf3bf3c052e0e7819f38e8fd190f","datavalue":{"value":{"time":"+2025-09-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6930157$5F993A4B-7764-4F2A-A827-2B1E5ED98838","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e6c3a4178b5d7ea72e11c998eafc9efd9fd4dd9e","datavalue":{"value":"Can you partition the edge set of a random \\(d\\)-regular graph with \\(n\\) vertices (\\(\\mathcal{G}_{n,d}\\)) into disjoint \\(k\\)-stars? This article conjectures there is a threshold value \\(k^\\ast (d)\\) such that this is possible with high probability (w.h.p.) as \\(n\\) grows large for \\(k\\leq k^\\ast (d)\\), and impossible w.h.p.\\ for \\(k> k^\\ast (d)\\). More precisely, there are some partial answers: the non-existence of a \\(k\\)-star decomposition in \\(\\mathcal{G}_{n,d}\\) w.h.p.\\ is proven for \\(k>k^+(d)\\) using a first moment method, where \\(k^+(d)\\) is defined as the threshold value for which the expected number of independent sets of size \\((2k-d)n / (2k)\\) in \\(\\mathcal{G}_{n,d}\\) goes to \\(0\\). This value is believed to be almost sharp since the conjecture is in fact \\(k^\\ast (d)\\in \\{k^+(d)-1,k^+(d)\\}\\).\\N\\NThe authors also prove existence w.h.p.\\ for some values of \\(k\\leq d/2\\) using, in particular, a connection between \\(k\\)-star decompositions and \\(\\beta\\)-orientations. Finally, existence w.h.p.\\ is proven for all \\(d/2<k\\leq k^-(d)\\), for some computable boundary value \\(k^-(d)\\) using the small subgraph conditioning method. Numerically, it is found that \\(k^-(d)\\) is sufficiently close (often equal) to \\(k^+(d)\\) that the conjecture could be verified for any \\(d\\leq 200\\) and \\(d/2\\leq k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6930157$3C788B83-F236-4CB9-8AD3-AED12CC80FBC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9475d262ec55242fd2469ab2c99e8e63adbb04ff","datavalue":{"value":{"entity-type":"item","numeric-id":1617122,"id":"Q1617122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$5C5F7910-77FD-4E35-B316-2DA8248D8C71","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6930157$B5C01140-D562-4AE7-BEFF-9F6500427ABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6930157$90E86CB0-5656-4889-B22F-49A790F9C97B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6930157$CA025E7E-33F4-45B4-A06C-A73EF64258DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e119ec900ee9bf9a7b856e16bfcb83ead6fe3577","datavalue":{"value":"8093421","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6930157$C3B04A8E-90D0-495B-A09E-08222BD79E7A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62e547b57ec4579de9e575a2ac77aeddbd664491","datavalue":{"value":"random regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6930157$EF139A4A-11EE-42A6-B2EA-6D7E93AB84E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"489a665d632b383ba80c5eff252c56e70ac177fb","datavalue":{"value":"star decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q6930157$11141F79-9283-440E-8515-62254790B52B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q6930157$C71607B1-3014-46B9-A8BD-8C1B9038A534","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":"Q6930157$D3919932-F74A-462C-8B54-E34F8D15B761","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0469e68bf5402f00965518bd450ee46c7f16a963","datavalue":{"value":{"entity-type":"item","numeric-id":2200917,"id":"Q2200917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$7E9528A4-334C-4853-B7BE-8E31C5BE6736","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faba6bbf127f770c659496defe55ac19f28d99b1","datavalue":{"value":{"entity-type":"item","numeric-id":1876685,"id":"Q1876685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$67A40B2B-6C4F-45AF-8E54-59360574597A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e6eb41e6ea95c3d0c759afdf930212864a893d","datavalue":{"value":{"entity-type":"item","numeric-id":1132885,"id":"Q1132885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$D873DA7F-4B66-41ED-9F0C-57449E82246F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"727cbe0ca00c9bd3b90b6cc980c71b3e1f6b5dcf","datavalue":{"value":{"entity-type":"item","numeric-id":1213891,"id":"Q1213891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$4701E1D6-282A-4CD3-9EBD-0B4B5A7A31E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efb33860812d9c15b3bb1746660260e97abb9d6b","datavalue":{"value":{"entity-type":"item","numeric-id":1645062,"id":"Q1645062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$C892ADBE-1965-4B2C-9FE9-F7C81D9388D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d56a1af52f8f9226f0d7f17f821a6a45d2331bb","datavalue":{"value":{"entity-type":"item","numeric-id":6829875,"id":"Q6829875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$8B1EF0DD-885C-42E0-B0C5-B0FE0F8DFE09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fc46f7d1ff67735ccbbabb7e798ca25ed5b8ad8","datavalue":{"value":{"entity-type":"item","numeric-id":2407501,"id":"Q2407501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$1F2FEF1D-8517-488B-B972-BAD002DC5AD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"059b844fd56c9a12f0c80cda9ffdfced07f9f6de","datavalue":{"value":{"entity-type":"item","numeric-id":1186131,"id":"Q1186131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$8BB7FA73-80EA-483A-8A56-8A124A5E3B6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a78277e6b14422e8d70cdf3fe5090acff8b19c6c","datavalue":{"value":{"entity-type":"item","numeric-id":2687694,"id":"Q2687694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$DE2E8C25-3709-4FAE-BB11-D7104F00B594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a388e547150b2efc6d4e6a53f73629715502961","datavalue":{"value":{"entity-type":"item","numeric-id":1756550,"id":"Q1756550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$4D6CE127-DA7B-4B50-987F-60A755B4F94F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14138bd19dbcaae6e98023dd587529bd29d27579","datavalue":{"value":{"entity-type":"item","numeric-id":1916491,"id":"Q1916491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$C2C5BBFE-F1F1-4D62-8664-B3D4A18E9364","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d158d5eff719264e089d573f19626af277acd271","datavalue":{"value":{"entity-type":"item","numeric-id":1034530,"id":"Q1034530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$CA46A5CA-F797-4238-9C1D-19F123ABCCA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51d9d8e004df3c99746501adf3be1620002bb433","datavalue":{"value":{"entity-type":"item","numeric-id":461727,"id":"Q461727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$E7E0A6B2-6652-4E05-8EFB-973BD8BC361F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8627b3f07ae500016bd6cbd2135c7bb226fd0653","datavalue":{"value":{"entity-type":"item","numeric-id":2998847,"id":"Q2998847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$1E31CF64-8F26-4041-991A-8ED90FDDAC73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"721b8b7bf556fe13b72ff83b9c4b2516e63b11a4","datavalue":{"value":{"entity-type":"item","numeric-id":4868737,"id":"Q4868737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$3155F624-FDF8-4B9A-9CBC-702C20A87C18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ea85834a995582d6f639d832e012772982e155e","datavalue":{"value":{"entity-type":"item","numeric-id":3990215,"id":"Q3990215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$F1BFD341-6DD9-46E2-A423-95B74A637216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb26da3d1d45575a2840912b1e47e6c0c39f7028","datavalue":{"value":{"entity-type":"item","numeric-id":412176,"id":"Q412176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$245DA1AB-9A85-4870-93B1-A54629871633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01dbcf60e7b62cc0aba0f82d898456954ee1b69e","datavalue":{"value":{"entity-type":"item","numeric-id":1143413,"id":"Q1143413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$FC98B120-3A2E-4DB9-9FD9-1F335DEBBF6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0171bc595200a187b32b365d87081bc016637750","datavalue":{"value":{"entity-type":"item","numeric-id":3287782,"id":"Q3287782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$9F972EB2-9E55-4D14-91F1-EEA3E96920AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"767177c9c2beae2d8abc0a60a160c198d5edad64","datavalue":{"value":{"entity-type":"item","numeric-id":3901534,"id":"Q3901534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$C395DC2B-7008-4C17-8385-428999BB64F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de613908d2cd012d4fcbd4fd9626fc061166750c","datavalue":{"value":{"entity-type":"item","numeric-id":1120601,"id":"Q1120601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$CDC8E10D-3A15-4AB9-BB0B-A9B8AD9E76AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7fb451cd334a87eafe9826c9961a47e98d4405","datavalue":{"value":{"entity-type":"item","numeric-id":1255501,"id":"Q1255501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$1B8F673D-37C9-47C9-AE57-3DB53F08A539","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e93d41a9be07a1a365d4aa53f08b358859e5633","datavalue":{"value":{"entity-type":"item","numeric-id":5110648,"id":"Q5110648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$FD72421F-C66D-44C4-A3A5-D4D04847D3B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f34fb167d6b58149e4c07bc6f477f173f3d07b81","datavalue":{"value":{"entity-type":"item","numeric-id":1150630,"id":"Q1150630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$70739D2B-E1C3-444C-BA9C-50D0B45E7121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd1a57b3a7e1f837da53304fca53786b3274b497","datavalue":{"value":{"entity-type":"item","numeric-id":4911113,"id":"Q4911113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$7F4FC9EF-5103-4F3F-90FF-054F7F9AAED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e874bf86ba4936c793a66726f6732ed7085c8caf","datavalue":{"value":{"entity-type":"item","numeric-id":4485695,"id":"Q4485695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$57607B4C-CE3E-4F3F-A672-DE9A615E8066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2330ca0732becd004147c331ff89990de545627","datavalue":{"value":{"entity-type":"item","numeric-id":4324964,"id":"Q4324964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6930157$9B839BDE-5155-4C43-8077-9642FC8BF4DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Decomposing random regular graphs into stars","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Decomposing_random_regular_graphs_into_stars"}}}}}