{"entities":{"Q6117415":{"pageid":13251722,"ns":120,"title":"Item:Q6117415","lastrevid":58692252,"modified":"2026-04-06T08:37:32Z","type":"item","id":"Q6117415","labels":{"en":{"language":"en","value":"Power of \\(k\\) choices in the semi-random graph process"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7806446"}},"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":"Q6117415$8CE69525-D004-4378-9F9A-7981AC177A21","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"54d2eea5d1aa3a38014f6170453d4e1c1098ef54","datavalue":{"value":{"text":"Power of \\(k\\) choices in the semi-random graph process","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6117415$8110BD7A-B0E0-4616-98CD-A16A7696ED1E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6ff7d31c230fca2ddeca98f46431b1b1392f16de","datavalue":{"value":"10.37236/11909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6117415$F2B58A0E-A1EC-4ED4-98E6-CC94BB106094","rank":"normal"}],"P16":[{"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":"Q6117415$AFB36F26-ED07-4081-B0B0-3F32AC5EDFEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c52810051fa0810a8ab1e57cfea7100ce86f29a","datavalue":{"value":{"entity-type":"item","numeric-id":6117414,"id":"Q6117414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$D5B5BB96-E335-4293-A535-8D2FE5AA4AD6","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":"Q6117415$03D787C5-B1ED-4269-81D8-843EC64C8AB8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"55eaaa493a481ac9a5b670bf3267ec8c8b613843","datavalue":{"value":{"time":"+2024-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":"Q6117415$7C547EEF-3206-4C40-8130-656C48080B8C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2a2f329a0e8ee2038b48c3c593b3ce5bd367ba65","datavalue":{"value":"https://arxiv.org/abs/2302.13330","type":"string"},"datatype":"url"},"type":"statement","id":"Q6117415$7C27311C-885A-4CC3-AAD3-7338628F06CB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c0977eeee876be64563b5836cf13b504773b956a","datavalue":{"value":"This paper studies a generalization of the semi-randomized graph process introduced in \\textit{O. Ben-Eliezer} et al. [Random Struct. Algorithms 56, No. 3, 648--675 (2020; Zbl 1442.05203)]. In this variation, the game starts with an empty graph on \\(n\\) vertices, and the player is presented \\(k\\) random vertices \\(u_1,\\dots,u_k\\) to choose from in each round. Once a vertex \\(u\\) is chosen, the player then selects a vertex \\(v\\) and adds \\(uv\\) to the graph. The objective of this game is to minimize the number of rounds it takes to force the graph to satisfy some monotone graph property with high probability. In the case of \\(k=1\\), we have the original game. The main results come in sections 3, 4, and 5 in which the properties of minimum degree of at least \\(\\ell\\), the existence of a perfect matching, and the existence of a Hamiltonian cycle respectively are discussed. For sections 4 and 5, an optimal algorithm was not clear, so upper and lower bounds are presented. However, in section 3 it is shown that the optimal algorithm when the property in consideration is minimum degree of at least \\(\\ell\\) is a greedy algorithm in which the offered vertex with the lowest degree is selected and joined to a minimum-degree vertex.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6117415$69D4028F-3B7B-4C49-8350-1CCEA4E27465","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"61aacb326b9016e73ab7a18800effe4a33425a59","datavalue":{"value":{"entity-type":"item","numeric-id":822751,"id":"Q822751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$823C6569-5039-4935-97EB-E228730652E3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6117415$818F86CE-5CDE-44EA-8F52-45AEC7DE65F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6117415$B0CFEEA5-742F-4B5D-A5E3-C2F4E11C03FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"eef1b49f4a66afb755b22d7419db9d61ba07415f","datavalue":{"value":"05C45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6117415$0DF80190-922A-4C29-88C3-DB82705A63C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6117415$6E9C2DA1-2E32-4992-BAFE-BD7FCD7D6E79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"93f10fe6f770d9a5bb6d9eaccaa75da241869576","datavalue":{"value":"7806446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6117415$F7050F37-64BC-43DC-8CE1-6D8A6C5F8A2B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q6117415$A66F812D-4796-41D6-944F-8B867A67B423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q6117415$17A0B230-5CD2-48CC-9800-31236AE88E03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7523f779bbfb4afc6792d52896fa0942e8ad02d","datavalue":{"value":"semi-random graph process","type":"string"},"datatype":"string"},"type":"statement","id":"Q6117415$09A04DB4-6A9F-4DB3-8CFC-AF84F3E7F447","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":"Q6117415$8B3C9B4C-9CD6-4B55-92D5-1B9977122828","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b05637aec4598ea21d60183188bf07e78ed9a989","datavalue":{"value":"W4391258576","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6117415$7DCB9DE7-C357-4211-8D2A-2F6432D1164B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e70cba328e20d29a75d4d61248ddf045d10851f","datavalue":{"value":{"entity-type":"item","numeric-id":2817654,"id":"Q2817654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$B14D3C92-AD30-4191-86F2-65CF62FC4E92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38952de44a94f745a0786ce5b7aaaeed136d1104","datavalue":{"value":{"entity-type":"item","numeric-id":2073291,"id":"Q2073291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$BDD2B02A-51F4-4EDA-8588-23DC233D5320","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21270dc0b5fa45056acd88b2299ee724aba0b966","datavalue":{"value":{"entity-type":"item","numeric-id":5146812,"id":"Q5146812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$0E344493-C4A4-4421-8B6A-0C1C8F8B191F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e5da755ddcb4d32fd26ce827b62ef4a147e84e5","datavalue":{"value":{"entity-type":"item","numeric-id":5113951,"id":"Q5113951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$80C46640-D1FF-4C82-BC4E-5D4272871009","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":"Q6117415$8B8861BB-B0DE-4E6C-AD19-0B0928CBA2EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5e3a589df52b5b59a3ffc403954bc73d11c67c9","datavalue":{"value":{"entity-type":"item","numeric-id":4705326,"id":"Q4705326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$0B0F8ECF-5F8E-4D26-975D-6F075DC7FB06","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":"Q6117415$26CD0C6E-0588-4671-AD01-9AED3DFA21D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9344fc1ca035cf683dde2e6f0e14d7e4a06606fa","datavalue":{"value":{"entity-type":"item","numeric-id":2237858,"id":"Q2237858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$50BA2EFE-6A0F-48A7-9BBB-FF9C56B0FBC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdf50d24a18d9f9dbfc60c53836fb6b5fc308867","datavalue":{"value":{"entity-type":"item","numeric-id":5864217,"id":"Q5864217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$6581E9DB-43B1-4A07-81B1-3354EA36A817","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":"Q6117415$3A2A2FA2-D1CD-4DF0-A260-1A3E6C2D952E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25ae01012e656d0bae282bb10dcbc843637ff552","datavalue":{"value":{"entity-type":"item","numeric-id":2949990,"id":"Q2949990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$3FA5D24F-141B-43F6-BEFA-5FA28EF5E806","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e889f1f400c15297e401c3bd41bcb94c13c3cf9","datavalue":{"value":{"entity-type":"item","numeric-id":2173435,"id":"Q2173435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$76BE8244-40F9-4C65-B8C5-211F6E2F5D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f952d3c1bcb0c1ee4c1d2186d9485850cf824637","datavalue":{"value":{"entity-type":"item","numeric-id":4788604,"id":"Q4788604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6117415$EBBC9D8B-7F47-4AB9-B58F-6FA3F192809C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c73c60c146b626c6b88a80f977f59e578e61b3e","datavalue":{"value":{"entity-type":"item","numeric-id":1252000,"id":"Q1252000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6117415$F20D6307-269B-4FAB-A250-C29589EA7710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e26a8623acd044c3beb0892ed8d0f39f0033a00","datavalue":{"value":{"entity-type":"item","numeric-id":4777167,"id":"Q4777167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6117415$F144567C-4F09-4CEB-A927-4DBF4CC199A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a10e02c3c9d183bcb19b02356581e251c58c00e","datavalue":{"value":{"entity-type":"item","numeric-id":4334585,"id":"Q4334585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6117415$BFBC2BAE-938C-41CF-8CB4-203851B7DC3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"678547c73b3756f131e0016b5a3d29b4c3c3564c","datavalue":{"value":{"entity-type":"item","numeric-id":2653890,"id":"Q2653890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f5bad60f5d71e07f84653e70422d32de406082f","datavalue":{"value":{"amount":"+1.0","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6117415$742AC176-F3F2-44AD-BAA6-14B1B09149F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f436c085843de9b8da98ce99c80f912b61328887","datavalue":{"value":{"entity-type":"item","numeric-id":5567707,"id":"Q5567707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6117415$66D536D7-139E-4D0B-BBDB-BF73F9F55F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"159a39c015e5ee2f8a554065024bd5b246679265","datavalue":{"value":{"entity-type":"item","numeric-id":3850075,"id":"Q3850075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6117415$B85CB744-D998-4DA4-A25E-FACEE5E849C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"764576409214279f9912a28e16df80a2db30ac72","datavalue":{"value":{"entity-type":"item","numeric-id":3245426,"id":"Q3245426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6117415$CB621FD3-794B-4874-B200-2536E968E971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cce9a2e4bafc108e8da7a092a718a9fdb8f1430d","datavalue":{"value":{"entity-type":"item","numeric-id":4743819,"id":"Q4743819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbab897a6d3e720dc80b67e0eef4e13e205a07dd","datavalue":{"value":{"amount":"+0.9999999","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q6117415$B18F5DE3-E107-4013-8B62-01440C61FE0F","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":"Q6117415$3E6F1EF0-AD3B-49A2-B3F2-039A28627510","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6117415","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6117415"}}}}}