{"entities":{"Q2256126":{"pageid":2266869,"ns":120,"title":"Item:Q2256126","lastrevid":57814767,"modified":"2026-04-02T15:50:33Z","type":"item","id":"Q2256126","labels":{"en":{"language":"en","value":"Power of \\(k\\) choices and rainbow spanning trees in random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6405885"}},"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":"Q2256126$E312D988-DE51-4716-B86C-EEF47EF76C87","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d462d9085e5469692ae728caee669feb3787682b","datavalue":{"value":{"text":"Power of \\(k\\) choices and rainbow spanning trees in random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2256126$FDA80BFD-86C7-4AAE-A8A7-63142246DA03","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6253b994bc3c701066b337d1bcd0659b65b0a358","datavalue":{"value":"1307.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2256126$0573D985-074E-4F3B-A271-17E28BC25AD2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"15bff9c566e4551b0ae194362da4ad9b1958d695","datavalue":{"value":{"entity-type":"item","numeric-id":344443,"id":"Q344443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$C753593B-C192-4FFD-92BF-CFAC3D917880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2fd127ae6d5779c4f17f0db19dfc128c9ddb9529","datavalue":{"value":{"entity-type":"item","numeric-id":345116,"id":"Q345116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$4C56D1D1-23D4-44C2-8327-1003C345F757","rank":"normal"},{"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":"Q2256126$D9B14B1E-255A-4144-B177-8B701183CA81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$B3364146-13DE-4C27-A636-7A697AB0EF94","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$D9C0CEBA-1E40-41E6-8D02-F3A4200EDE15","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"35de2f7dede9cb43e2113b36996633151e59fa80","datavalue":{"value":{"time":"+2015-02-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2256126$307B6FD5-1921-4BC8-9DFB-DE84559C7353","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ffd20478df1df0a8570386c2f00f50dd85cd832b","datavalue":{"value":"https://arxiv.org/abs/1410.3405","type":"string"},"datatype":"url"},"type":"statement","id":"Q2256126$336BA2CB-713D-4AFC-8899-05F67DC741E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"331bd96e6983207cfc34a6d46912370aeaeacacb","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p29","type":"string"},"datatype":"url"},"type":"statement","id":"Q2256126$9B2EF650-32A6-446D-851F-419C5EE056B5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21c101173ca1b9ba2aeb9e44087fec14b7a635dd","datavalue":{"value":"Summary: We consider the Erd\u0151s-R\u00e9nyi random graph process, which is a stochastic process that starts with \\(n\\) vertices and no edges, and at each step adds one new edge chosen uniformly at random from the set of missing edges. Let \\(\\mathcal{G}(n,m)\\) be a graph with \\(m\\) edges obtained after \\(m\\) steps of this process. Each edge \\(e_i\\) (\\(i=1,2,\\dots, m\\)) of \\(\\mathcal{G}(n,m)\\) independently chooses precisely \\(k \\in\\mathbb{N}\\) colours, uniformly at random, from a given set of \\(n-1\\) colours (one may view \\(e_i\\) as a multi-edge). We stop the process prematurely at time \\(M\\) when the following two events hold: \\(\\mathcal{G}(n,M)\\) is connected and every colour occurs at least once (\\(M={n \\choose 2}\\) if some colour does not occur before all edges are present; however, this does not happen asymptotically almost surely). The question addressed in this paper is whether \\(\\mathcal{G}(n,M)\\) has a rainbow spanning tree (that is, multicoloured tree on \\(n\\) vertices). Clearly, both properties are necessary for the desired tree to exist. {  } \\textit{A. Frieze} and \\textit{B. D. Mckay} [Random Struct. Algorithms 5, No. 1, 45--56 (1994; Zbl 0796.05084)] investigated the case \\(k=1\\) and the answer to this question is ``yes'' (asymptotically almost surely). However, since the sharp threshold for connectivity is \\(\\frac {n}{2} \\log n\\) and the sharp threshold for seeing all the colours is \\(\\frac{n}{k} \\log n\\), the case \\(k=2\\) is of special importance as in this case the two processes keep up with one another. In this paper, we show that asymptotically almost surely the answer is ``yes'' also for \\(k \\geq 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2256126$FF0F9265-3EA7-4CB1-AC48-0F74DAE042B2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2256126$8B5BD9FA-8176-453B-A809-88202D5C3BD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2256126$41E4C925-8F5A-4E1B-8502-E255881E9CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2256126$03E35F9A-9C68-460B-8F12-426F7979EDFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2256126$C4499FEC-743F-4555-8F40-C24F6B5B4C7E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"528de5ed3129a17eb746968483fd651267a0472f","datavalue":{"value":"6405885","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2256126$BD568D83-7718-4963-BB8F-BA3F8B6B4D5E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00d2a028fef460e1de9188fe81a48c0b47a7f014","datavalue":{"value":"Erd\u0151s-R\u00e9nyi random graph process","type":"string"},"datatype":"string"},"type":"statement","id":"Q2256126$462309A6-051C-4E55-8868-6BC064152E9A","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":"Q2256126$46DFD956-B7F8-4C2C-BE08-ED80DEBA988E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bea8ef7821b5fc6d71652f11099bd43951d62ce9","datavalue":{"value":{"entity-type":"item","numeric-id":1890827,"id":"Q1890827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$B9881724-2310-403C-B891-A58C5510D5E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$18B3CDDF-F92A-4F19-A914-E932A79CC244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b07d6ae8072ec0b52d1a52248f558d67752e38c","datavalue":{"value":{"entity-type":"item","numeric-id":2743189,"id":"Q2743189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$A077FAA3-C766-4139-8AA0-51C984DA1FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"733d3e2504a069033ae23556590cbb0aad7f40b0","datavalue":{"value":{"entity-type":"item","numeric-id":3147274,"id":"Q3147274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$D528E5FC-390A-43AC-84E6-FA2702A22FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9507b7b5bcf387a198b92b7493bb3bf74faf59d9","datavalue":{"value":{"entity-type":"item","numeric-id":1899825,"id":"Q1899825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$68506C76-86AF-4EEB-81E2-2C3EBAE4CA6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$CD023B2B-A3B0-41ED-8B19-2D2C711EAD28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bfccaa03e442b16017ed30450c226137e312da1","datavalue":{"value":{"entity-type":"item","numeric-id":3672042,"id":"Q3672042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$A356059B-4163-4D56-9EA5-CA0DB008A4FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"815ab140628b680d51883c1c13ec9d244df1a525","datavalue":{"value":{"entity-type":"item","numeric-id":5415595,"id":"Q5415595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$2979311B-AB8D-4610-AD03-CD6B6A2B23A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba9aed24f44342d723932541b6d88423f731da04","datavalue":{"value":{"entity-type":"item","numeric-id":4288877,"id":"Q4288877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$61D779FE-F7DB-401B-B4F7-B3048D33ECF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3ed8f7222e9129de7ec9bbbdd4d41a3e177a017","datavalue":{"value":{"entity-type":"item","numeric-id":1088687,"id":"Q1088687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$5AAC551C-6AD8-4F77-9830-9839AD81BEB5","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":"Q2256126$45E280DE-7050-4697-925E-544019F00AB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1860b0031e2cbb9105661e4b1058c275782a39cf","datavalue":{"value":{"entity-type":"item","numeric-id":3135082,"id":"Q3135082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2256126$6E88D8AB-F0C2-4CF1-9534-0F928E7F864F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"9123cd921aa6973a701abe9531bb2780dcc14c56","datavalue":{"value":"bafkreie4boy5x7wkwidejwl6jvz7aojfwgg2it7ld74uoaf6i7spjggn34","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2256126$5D718E6D-1DED-4310-9A3C-2BA5A947A016","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8af16e8e239f0e16f82bd8f90cd2573120d3f001","datavalue":{"value":{"entity-type":"item","numeric-id":4288877,"id":"Q4288877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6f899842168b58ed4be5122d847bb0fd71c5c80","datavalue":{"value":{"amount":"+0.831074059009552","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":"Q2256126$90D041D6-3480-46DC-9874-AEE6D849E450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7eea4a92b283e4ddc56fd84ab5104efc03447ace","datavalue":{"value":{"entity-type":"item","numeric-id":6074865,"id":"Q6074865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d6f899842168b58ed4be5122d847bb0fd71c5c80","datavalue":{"value":{"amount":"+0.831074059009552","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":"Q2256126$4EF65AEE-25C7-4D32-9BCD-46C47C44760B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d78f87c15c23db6c0744a462993a0ffc9076386","datavalue":{"value":{"entity-type":"item","numeric-id":2833120,"id":"Q2833120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fa243fea7705657bc20029cfc8aa21903035461","datavalue":{"value":{"amount":"+0.8221144676208496","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":"Q2256126$3D0EABCF-701E-462A-B014-D4C4428C5F70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c799dccfa5e4232ed5d8ea728776dc5c3b81e6e5","datavalue":{"value":{"entity-type":"item","numeric-id":3167424,"id":"Q3167424"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e014a30c1506ffc1e4611a94a9b2d6194dd5a58a","datavalue":{"value":{"amount":"+0.800937831401825","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":"Q2256126$8ED2AE2E-3F9A-4360-B1F2-D63A46DD6A9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"490ca564c367cd0cd629c5e3fd2425a3d991decc","datavalue":{"value":{"entity-type":"item","numeric-id":5964983,"id":"Q5964983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"352aaec199b9a8b08b99157eec6e2627498bbfb1","datavalue":{"value":{"amount":"+0.7934603691101074","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":"Q2256126$AFD9EA36-1DA7-40FB-A8DB-02CC7183783E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2256126","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2256126"}}}}}