{"entities":{"Q2223474":{"pageid":2234217,"ns":120,"title":"Item:Q2223474","lastrevid":57780291,"modified":"2026-04-02T12:17:03Z","type":"item","id":"Q2223474","labels":{"en":{"language":"en","value":"Minimum-weight combinatorial structures under random cost-constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7303543"}},"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":"Q2223474$DA8B8F42-C11B-4BBE-899F-4FD67E00177F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc337d4e28e532695ef6b13ca65a5049493be0a1","datavalue":{"value":{"text":"Minimum-weight combinatorial structures under random cost-constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2223474$13B97E6E-9593-469E-B35E-3D7D6BE2A89E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"559bbc61f7dfa73ca6802eeaf08e59dcb7074114","datavalue":{"value":"1456.05145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2223474$A6904D4E-579D-4CC7-A1B8-13286B9CB0CB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a67814c94e3bacb4a90002d59e0b43b48a9401f","datavalue":{"value":"10.37236/9152","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2223474$5F097645-5C15-40C5-953F-E9E766C8124C","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":"Q2223474$9B626056-A86C-40FD-B829-7F5BD38E9DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"28ed5aa3d9119097d19913a5fb93bbc03bba7846","datavalue":{"value":{"entity-type":"item","numeric-id":414886,"id":"Q414886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$0F6BE4B3-C3F7-4083-AA35-67CFF90ADD70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b27515d469dfd012c92fe2f2c18443f1b26d0ee","datavalue":{"value":{"entity-type":"item","numeric-id":375760,"id":"Q375760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$FB127DC2-5176-4D4D-A2D5-1B9C8A943505","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":"Q2223474$C7104631-EB37-40B3-82F1-6B77E623C5F5","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":"Q2223474$FBCE8FF5-1BB3-48ED-BD51-790FDB6E25F3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4d9d719ebb8f670fd6c641609e1f785d25edf480","datavalue":{"value":{"time":"+2021-01-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2223474$CA650CF2-14EF-407C-AB57-53C29EA5534D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"82babf950ced473b0a67aa8c3481f1833491ef87","datavalue":{"value":"https://arxiv.org/abs/1910.08977","type":"string"},"datatype":"url"},"type":"statement","id":"Q2223474$5B6417F9-C8B1-4F30-B17E-877AB4864971","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a80e08703a40554e53bb72289a53748d3362940","datavalue":{"value":"Summary: Recall that \\textit{S. Janson} [Comb. Probab. Comput. 8, No. 4, 347--361 (1999; Zbl 0934.05115)] showed that if the edges of the complete graph \\(K_n\\) are assigned exponentially distributed independent random weights, then the expected length of a shortest path between a fixed pair of vertices is asymptotically equal to \\((\\log n)/n\\). We consider analogous problems where edges have not only a random length but also a random cost, and we are interested in the length of the minimum-length structure whose total cost is less than some cost budget. For several classes of structures, we determine the correct minimum length structure as a function of the cost-budget, up to constant factors. Moreover, we achieve this even in the more general setting where the distribution of weights and costs are arbitrary, so long as the density \\(f(x)\\) as \\(x\\to 0\\) behaves like \\(cx^\\gamma\\) for some \\(\\gamma\\geq 0\\); previously, this case was not understood even in the absence of cost constraints. We also handle the case where each edge has several independent costs associated to it, and we must simultaneously satisfy budgets on each cost. In this case, we show that the minimum-length structure obtainable is essentially controlled by the product of the cost thresholds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2223474$DC4F10D6-5F6A-4BE3-88E4-A12D13A07E54","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2223474$D915D3D6-304B-482A-9CEA-42A6B5929F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2223474$73EDBD14-BDBE-4EB7-9BB9-C495D0D97D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2223474$4D529433-FC5E-43D5-8598-A8556F587096","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cb290119d600f3b80b9a32fc463ba4098a44e73d","datavalue":{"value":"7303543","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2223474$D037C056-6D26-41C9-8A14-B2620B4992F1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5839356c219ad2177e1cb8d8abf6ceca9362543e","datavalue":{"value":"random weighed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2223474$26E12CC3-2DE9-4234-8D96-9CA66E3C1A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"539be726cb8dfa54cd0c12914c99488c7ea42ea5","datavalue":{"value":"percolation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2223474$7A384FB0-7CCA-4034-876B-12B20493F329","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":"Q2223474$DCEC7576-5D46-4A69-947F-D0D40B864320","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2643f6f71fdef56d10ee10183c0bc3f04de4bf86","datavalue":{"value":"W3129231088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2223474$1E608FEA-FD91-4A75-AADC-57B740F6247E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"279590ceda1f168ff8db96edec493a9e369d0687","datavalue":{"value":{"entity-type":"item","numeric-id":1600093,"id":"Q1600093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$943D9C6C-DED9-4AA0-98AC-2E058CD7473C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab2a5f300abe89797b950e0221f7ced15a174c24","datavalue":{"value":{"entity-type":"item","numeric-id":1958506,"id":"Q1958506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$4B3ECAF0-FF4A-4B4E-B8BE-B2233D6BC04E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84d7bbac2c39b8126500ba02ec7c4cc37b782c02","datavalue":{"value":{"entity-type":"item","numeric-id":1952427,"id":"Q1952427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$D029C948-4DC7-4843-BC31-812CA269BD48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d58b6246a6c38c22c0721d6ecf00c93dc735a80d","datavalue":{"value":{"entity-type":"item","numeric-id":3055783,"id":"Q3055783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$AF153622-B16E-4E47-9193-ACB5C9B00657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a6334e1aef2e216cce76059c80eba21cc0ce054","datavalue":{"value":{"entity-type":"item","numeric-id":4500692,"id":"Q4500692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$0604DE5F-91BB-468B-BCDA-813301AAF08C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$4BDC0120-F1A5-4A1C-B007-B7B783A0E754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a270b91c4299553b6f90d4713b498e1c7fd02458","datavalue":{"value":{"entity-type":"item","numeric-id":1066149,"id":"Q1066149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$BD1B2AA0-1299-456B-9D3B-AC9CC572CEFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1789f6f00038d8a571ac4f4b8460586591a90db","datavalue":{"value":{"entity-type":"item","numeric-id":1093654,"id":"Q1093654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$579EFB10-CDB4-4AD0-A8AE-5E741840BE59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aca85d688b61a9e35f868526bb8bfa5def16936f","datavalue":{"value":{"entity-type":"item","numeric-id":2323813,"id":"Q2323813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$400C78CF-C067-4FC3-9821-F47357A545BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8bbc64b5a99758112d66f6a36ae44645ea130c3","datavalue":{"value":{"entity-type":"item","numeric-id":3699721,"id":"Q3699721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$6B1C4F37-2A25-4CE8-9EE6-A25591BE8997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08dd2cde602af137c52ba4f69c22bcd86e50c081","datavalue":{"value":{"entity-type":"item","numeric-id":5332577,"id":"Q5332577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$45B116E5-FA10-436B-A77A-1A4FBC4724EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e533e28b1cbb6bbefe7a2c796f75a2e3665a8b0","datavalue":{"value":{"entity-type":"item","numeric-id":4719434,"id":"Q4719434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$1CB0E87B-E236-446C-9EB0-95E2CE1ACB48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"046e9440c3df548a174bc6cde28627a144dc8011","datavalue":{"value":{"entity-type":"item","numeric-id":3048272,"id":"Q3048272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2223474$11EC66A8-402B-422E-80E8-070C8E3F3255","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3195d7f4a621666d41908f839801d67e2d387fb6","datavalue":{"value":"bafkreida7jmywmnmjtgatizrl7ff4e23b3bs7yb65brywydegjtrpjqhla","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2223474$6CA78583-AA13-49B0-994A-6C4DD5DA6325","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53019ffd7ee4b3892b6ad89af16e918024eed017","datavalue":{"value":{"entity-type":"item","numeric-id":2043355,"id":"Q2043355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d77ed448f3aa94a9fb25c8c2015fec478da720c","datavalue":{"value":{"amount":"+0.844861626625061","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":"Q2223474$F85D1562-C2BE-4076-B2D9-C43950EA99D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f1eaf4ac2ae9fed399d762977e7a0745c786d5f","datavalue":{"value":{"entity-type":"item","numeric-id":1066149,"id":"Q1066149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"000b28d73c10e6be35ef56fd7cdd17694fcb6bd9","datavalue":{"value":{"amount":"+0.8315103650093079","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":"Q2223474$3AEE8C6F-108C-4E43-942B-B845B131B138","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e391bf503b0c2267426a814644dde69a52eafa13","datavalue":{"value":{"entity-type":"item","numeric-id":2223477,"id":"Q2223477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"89f23832517b657984bdc3786601799e78f9e19c","datavalue":{"value":{"amount":"+0.8217368125915527","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":"Q2223474$070D3C89-379B-49CB-90FA-541844740ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc4f83efcb6bb6e2c55d3f720bd441087c1c367f","datavalue":{"value":{"entity-type":"item","numeric-id":5085156,"id":"Q5085156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7451d8a77b6eaae0a77a06e5f3d7da05b5cd29e8","datavalue":{"value":{"amount":"+0.7998204827308655","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":"Q2223474$ED4A85B7-625B-4B73-B98F-167AB721AA3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"472f62325225bf38edc61bcf52f678352a80a514","datavalue":{"value":{"entity-type":"item","numeric-id":3386534,"id":"Q3386534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef910690bb7c5e9980fc29ce056c355f82875ff3","datavalue":{"value":{"amount":"+0.7994211912155151","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":"Q2223474$4C82567D-2C15-4E48-B25E-4BA0BDA086D8","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":"Q2223474$8C222478-A0BB-4AF7-87B0-F088E3D0EB9D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2223474","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2223474"}}}}}