{"entities":{"Q2684902":{"pageid":2695645,"ns":120,"title":"Item:Q2684902","lastrevid":56696934,"modified":"2026-03-18T23:06:28Z","type":"item","id":"Q2684902","labels":{"en":{"language":"en","value":"Multitrees in random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7655025"}},"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":"Q2684902$491CDEFA-53DA-4DC0-8D75-26B8F4745F93","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d8c19bf7aca9ba37af6424fe3f98e55eb982a2a0","datavalue":{"value":{"text":"Multitrees in random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2684902$998875EC-8D87-4FCC-96E5-895BF4597A20","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"886db713b5e975654a1c6bc10a9c39e5c9b0ecdf","datavalue":{"value":"10.37236/10804","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684902$965006D8-342D-44E3-8286-075184DB1573","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f74fe09b87e0ac8b962868920b53a656eff096e2","datavalue":{"value":{"entity-type":"item","numeric-id":295852,"id":"Q295852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684902$E7AAD7DE-5B95-4793-BAAC-4069F5B88BD1","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":"Q2684902$681D572E-34BE-41A3-835A-615331D4C6A6","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":"Q2684902$97AC0004-4762-4CB5-BF40-6F920A954B12","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2c66fb7aab39afe15eb7d8af0079ba7f34f4d9d","datavalue":{"value":{"time":"+2023-02-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2684902$478CCC2F-3AAA-4415-A55C-13EB74558755","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a7ae90be5cd15108f91f01c4cfa7485e8fffc85c","datavalue":{"value":"https://arxiv.org/abs/2110.08876","type":"string"},"datatype":"url"},"type":"statement","id":"Q2684902$7C3F902F-839F-4C76-9CFD-13182437343F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f62b45be6070a10c9be0e7dade0b319c969b0942","datavalue":{"value":"Let \\(N=\\binom{n}{2}\\) and \\(s\\geq 2\\) be a positive integer. Let \\(e_{i,j}\\) for \\(1\\leq i\\leq N\\) and \\(1\\leq j\\leq s\\) be \\(s\\) independent random permutations of the \\(N\\) edges of a complete graph on \\(n\\) vertices. We say that \\(I\\subseteq [N]=\\{1,2,\\ldots ,N\\}\\) is a multitree if for each \\(1\\leq j\\leq s\\) the edges \\(E_{I,j}=\\{e_{i,j}: i\\in I\\}\\) induce spanning trees of \\(K_{n}\\). Our interest is in the smallest \\(m=m(n)\\) for which there is a multitree with high probability (w.h.p., i.e. with probability tending to 1 with \\(n\\)). Let \\(m^\\ast\\) denote the hitting time for having a multitree.  The main result of the paper under review is that \\(m^\\ast=O(n\\log(n))\\) where the implied constant depends on \\(s\\).  The second main result is for the case \\(s=2\\) when a matroid result of \\textit{J. Edmonds} [in: Combinatorial structures and their applications. Proceedings of the Calgary international conference on combinatorial structures and their applications held at the University of Calgary, Calgary, Alberta, Canada, June, 1969. New York-London-Paris: Gordon and Breach, Science Publishers. 69--87 (1970; Zbl 0268.05019)] allows a more precise result that the first theorem mentioned above.  The authors also discuss some variants, for example showing that if \\(m\\geq Kn\\log(n)\\) for some absolute constant \\(K\\), then \\([m]\\) w.h.p. contains a MultiPerfectMatching, that is \\(I\\subseteq [m]\\) with \\(\\vert I\\vert=\\lfloor n/2 \\rfloor\\) and each set \\(E_{I,j}\\) inducing a matching of the maximum possible size \\(\\lfloor n/2 \\rfloor\\).  The authors also conjecture that there should be a constant \\(K\\) such that for \\(m\\geq Kn\\log(n)\\) there should be a multi-Hamilton cycle.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684902$7C211624-03A4-46F7-950C-C95FCEA9FE06","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684902$E7749403-0A13-4CDA-8111-3DA46C6CE140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684902$0F2EC0B3-2479-44F6-B85E-A1BDF724196C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f95337259c113f67164626f99958d45d83834947","datavalue":{"value":"7655025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684902$FA8BAED1-DC8F-486C-8707-6A878B8C093B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8419fa09c8080e343c913d27c5478d89adfee4ea","datavalue":{"value":"multitree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684902$FCBFD379-11E0-4701-BC70-B5EF730D350A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"389a5cd618f82735a490f722313a2ed2c428d806","datavalue":{"value":"random permutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2684902$F4CA7FEA-D13B-416F-9873-0D71E282E0B3","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":"Q2684902$3E55DEBD-E94F-4E3B-995D-2C0CD53E3C43","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":"Q2684902$1B3035BD-08DF-4EA0-A9F6-BAD532B42104","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fab9192e122be5a0818794a0da034443b45bef4d","datavalue":{"value":"W3207762126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684902$27A97252-7177-4F4F-A758-7BE919BBD683","rank":"normal"}],"P223":[{"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":"Q2684902$4DA3EDE3-CEB1-4AED-83A2-0A3691D29129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5952bee1e4055d9d7c84857b3c37163a4b453936","datavalue":{"value":{"entity-type":"item","numeric-id":4414632,"id":"Q4414632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684902$42C32CF6-B5D4-4D82-9C67-BDE0F181CD8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"423876ffd372f8cc922e2f017542b2a3f5991ac8","datavalue":{"value":{"entity-type":"item","numeric-id":1983096,"id":"Q1983096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684902$908F7766-7E8C-458B-B5A4-DE89B29654FB","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":"Q2684902$F5DE3D4D-3454-48CC-B7B5-FB800A493DA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c179cf0d9ad0ae5d2979f955ed58b12d9e45f476","datavalue":{"value":{"entity-type":"item","numeric-id":3522827,"id":"Q3522827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684902$05CB6EEE-61C8-475E-A6C0-71BACE2A053D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4179d847b8fbfde630c91039b913396fdacb7d76","datavalue":{"value":{"entity-type":"item","numeric-id":5020682,"id":"Q5020682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684902$A09E350B-70DB-4671-AE2F-67E078A4E2DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30f2197a6a09231de2069b98b8861f1751f91919","datavalue":{"value":{"entity-type":"item","numeric-id":3971235,"id":"Q3971235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684902$2CFA1A90-A19A-46D2-AF6A-C59D101BB3FE","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b6a04267ef1c5107d5dcde9c5b84a734e4114df5","datavalue":{"value":"bafkreigvfnj3pw3ofzgpq76b73tnnz3rsivrmpg7n6nskfzkmg2tnvbuym","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2684902$4E6D2288-06FD-4AF1-8301-9EE8CE76066F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc01e4a424ea6220eca4a486b465ded4a6a6c356","datavalue":{"value":{"entity-type":"item","numeric-id":2136168,"id":"Q2136168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d37a55230c0fc33dddc3e5a3851a5b3306bd7145","datavalue":{"value":{"amount":"+0.7886626124382019","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":"Q2684902$9F557253-180F-488B-8785-1BEBA54E2FA7","rank":"normal"},{"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":"8cc666855df8cb0692cbdf5635d94496a9f07a0e","datavalue":{"value":{"amount":"+0.7877131700515747","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":"Q2684902$1F843584-4330-42BE-BDD4-05942084A9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06074747e8d1e52b372ff7d01674149ef29aa080","datavalue":{"value":{"entity-type":"item","numeric-id":4262228,"id":"Q4262228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cc666855df8cb0692cbdf5635d94496a9f07a0e","datavalue":{"value":{"amount":"+0.7877131700515747","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":"Q2684902$C3182B35-3FF1-4A0F-BE60-4FE8CB9F2EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e70c7425dd28647a4990221155adbea99a066371","datavalue":{"value":{"entity-type":"item","numeric-id":5904060,"id":"Q5904060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"114346f73e218c44079f86dddf8d0877b15ce77c","datavalue":{"value":{"amount":"+0.7602664232254028","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":"Q2684902$329C6A75-26F7-4894-89F9-CE679EAA6199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cff59b83f91f4955523dd4c5e36bb94aab39d29d","datavalue":{"value":{"entity-type":"item","numeric-id":5113937,"id":"Q5113937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"743930f14b12e5c187143af6aa642bc61f5ae0ac","datavalue":{"value":{"amount":"+0.7568110823631287","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":"Q2684902$59875A2F-458A-4C62-90BF-33100BCE3204","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2684902$25BD2687-F186-4B28-97E1-3B2B6A9F1B28","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2684902","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2684902"}}}}}