{"entities":{"Q2833120":{"pageid":2843857,"ns":120,"title":"Item:Q2833120","lastrevid":83700695,"modified":"2026-05-07T10:01:45Z","type":"item","id":"Q2833120","labels":{"en":{"language":"en","value":"Rainbow arborescence in random digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6653613"}},"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":"Q2833120$CC729AB4-BB2D-468A-8F69-B8E22B35EFC5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e6e976aea4e1aaa660207979e9db7d37715fb4ae","datavalue":{"value":"1352.05160","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2833120$7E5257EB-E483-4C21-BA94-385E7905B7E9","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":"Q2833120$E63EC3B7-C794-4D41-AA98-833CD7CB7CAB","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":"Q2833120$42B12493-F252-409A-82E4-0F312C3E6AB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"af07c36948eced54f1dc55426fb5b21ba52f6793","datavalue":{"value":{"entity-type":"item","numeric-id":266694,"id":"Q266694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$F75EDACD-6391-4939-968F-080E2C1F157A","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":"Q2833120$80EC042D-916D-48F8-9F47-AD4E774683B7","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":"Q2833120$79F0D77E-1401-4AED-B3A6-C6B425841BB4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4de5c7a5d238217ab4a071d198b3a40ee05be465","datavalue":{"value":{"entity-type":"item","numeric-id":2725046,"id":"Q2725046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$2A87D3D9-1593-40F0-ABC4-B078E9649238","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bf4790cf746a4e37044520732373035560f5d245","datavalue":{"value":{"time":"+2016-11-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":"Q2833120$8568E025-6E12-4BFB-85EA-F8B730A728C9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"399779c9cbf29d0f4345502d92bae82122750334","datavalue":{"value":"https://arxiv.org/abs/1411.3364","type":"string"},"datatype":"url"},"type":"statement","id":"Q2833120$DEF585D8-AA7F-4CF5-8CA1-7D3F7EFE300F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2833120$34CFC8FB-C6A9-44BE-9A59-376E33D39E35","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f0b1de8d1db27adf87b82ef060d9cc49a274baa9","datavalue":{"value":"6653613","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2833120$E86680EA-AF7F-46E7-BE52-8F437447EF64","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c256c6db56948c6453d0f90a63e8084aa93c4066","datavalue":{"value":"random digraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2833120$A1362CFE-E3E0-4FBE-BFAB-3ED03A69BBAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"150b809fd0be0d31c43b2e18ef8f76a7cef79188","datavalue":{"value":"arborescence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2833120$5D8FAA57-5529-489C-8F36-2FC9E0EDC6B5","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":"Q2833120$E913609F-DA11-4B35-BDCB-DB21CFC57A59","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"db4b6c0a64cc0b69624cf298f77b071dc33c6e1f","datavalue":{"value":"W1871140597","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2833120$993AA9DA-4185-4EB7-8EA3-BBB54DFCFB75","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e10eb405d8e5cc097a8317842a8d7b101c1f022c","datavalue":{"value":"Q57401405","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2833120$DABB5EDF-F0F4-4E8F-AB55-FBAFA8DAC5C9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"db9282efb7b7b1a6a418a968111f1f5fe915228f","datavalue":{"value":{"entity-type":"item","numeric-id":2256126,"id":"Q2256126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$E2EF573A-1353-4235-9803-CBC323DDEBDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4921b098fc5d9f968826adfc009da05e27cb4687","datavalue":{"value":{"entity-type":"item","numeric-id":2811161,"id":"Q2811161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$009935F7-5876-42CD-9E54-D259CDCDBF93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48df165ba0da15b435264f2c0b648e0924d63a83","datavalue":{"value":{"entity-type":"item","numeric-id":3344024,"id":"Q3344024"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$86A73DDF-B141-4818-B25C-FD75048534C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1ca531eed01d1ab075f8b87c53db0f9bff17ecf2","datavalue":{"value":{"entity-type":"item","numeric-id":3876739,"id":"Q3876739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$5FBCDEBD-A9FD-4193-9910-A5F1EB23683A","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":"Q2833120$064C8A59-1DB8-4F0A-AC3B-E90B06EE4413","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":"Q2833120$8B3189A4-DB74-4E94-95CF-F1AE02333CA7","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":"Q2833120$AD400F36-1200-4650-8B2C-9633EC01A1A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88b88f4ed0ca35affe0ca6ef8e78ae9158cc6c32","datavalue":{"value":{"entity-type":"item","numeric-id":4152390,"id":"Q4152390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$A08EC054-F563-452D-87D9-82A638203879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88c00ee24a38915437e8fdf62979cb4730f8c212","datavalue":{"value":{"entity-type":"item","numeric-id":3419610,"id":"Q3419610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$4B2136BC-7E4B-4D5E-870A-19150EE8E9FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cdbef098b40f351a3a3ed8aa2e2fce2223a8999","datavalue":{"value":{"entity-type":"item","numeric-id":3039396,"id":"Q3039396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$A41E66C9-D472-4B1F-894A-891C3CCC1E6C","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"125484119cf579b22d952aadd14caac5ab6d8f33","datavalue":{"value":"journals/jgt/BalBCFP16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2833120$4856E0B3-5222-467E-8323-465053371BA4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"eb357aed56bc44ae9b2439202175d8702b8ca580","datavalue":{"value":"10.1002/JGT.21995","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2833120$1270B47F-E02C-4514-8020-BD6B38D194AC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ecc358c7ba661455348d24551749f37fb98bddbc","datavalue":{"value":{"text":"Rainbow arborescence in random digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2833120$F2C12F9B-DB67-4DFC-9299-3DE01392682B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c97157f31797811da461cc86efb147a30ef041c0","datavalue":{"value":"A rainbow arborescence in a directed graph on \\(n\\) vertices whose edges have been coloured is a rooted spanning tree in the graph where all \\(n-1\\) edges point away from the root and have different colours. Two obvious necessary conditions for this to happen are that at most one vertex has indegree zero and that at least \\(n-1\\) colours have been used.NEWLINENEWLINEThe paper under review studies the Erd\u0151s-R\u00e9nyi random graph process which starts with \\(n\\) isolated vertices and at each stage adds one directed edge chosen uniformly at random from the set of edges not thus far added: let \\(\\mathcal{D}(n,m)\\) denote the state of this process when \\(m\\) edges have been added. The question posed in this paper is what happens when the process is stopped when at most one vertex has outdegree zero and \\(n-1\\) colours are present. The answer is that with probability tending to 1 as \\(n\\rightarrow\\infty\\), there is a rainbow arborescence.NEWLINENEWLINEThe proof is delicate -- the event that causes the process to stop has probability tending to 0 with \\(n\\) -- and depends on, very crudely summarising, revealing the randomness in a very specific order (relative to a certain encoding of the coloured graph) and working round some vertices having dangerously low in-degrees in certain colours.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2833120$62F61417-7541-4868-BA99-A416F689E6D7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2833120$ADCFCAD6-14A3-4B65-A6BF-A8DE8FB1AF3D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1d0a81f584cb06aac6464d5accabaf3bc7ce671","datavalue":{"value":{"entity-type":"item","numeric-id":2256126,"id":"Q2256126"},"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":"Q2833120$6CB832C3-BADC-41D0-8B86-49B27A431105","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78c594b30f6802a219883b5f32b085d39700017e","datavalue":{"value":{"entity-type":"item","numeric-id":4627483,"id":"Q4627483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97e20dc24e92e611f104192a2232571c24333dbc","datavalue":{"value":{"amount":"+0.7959036827087402","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":"Q2833120$5EC208E3-8291-4955-A307-BEA0B17D663B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f3c327046b72ded5d1d0329241562004e04f488","datavalue":{"value":{"entity-type":"item","numeric-id":1689982,"id":"Q1689982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf4dee8b1fcfe6c00d83ef65dfdad6e706d0f7b1","datavalue":{"value":{"amount":"+0.7936195135116577","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":"Q2833120$9C5E821E-A7DE-469E-A9BB-E4F22DA15149","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":"f38e569ec660e2545e09d62a745ed233e18c5ad0","datavalue":{"value":{"amount":"+0.7833611965179443","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":"Q2833120$D379DB25-48BC-464C-8BDB-237745AE9130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6fc5fdae8faf1bb210805adf4f3723bf282b1b84","datavalue":{"value":{"entity-type":"item","numeric-id":2189824,"id":"Q2189824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ffe0f91c36d52fcad2ffc7eccb65ce89cbb3d58","datavalue":{"value":{"amount":"+0.7818978428840637","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":"Q2833120$8AA8F2AA-17D9-4043-B64D-9537520B46F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Rainbow arborescence in random digraphs","badges":[]}}}}}