{"entities":{"Q2260635":{"pageid":2271378,"ns":120,"title":"Item:Q2260635","lastrevid":57810300,"modified":"2026-04-02T15:22:41Z","type":"item","id":"Q2260635","labels":{"en":{"language":"en","value":"Keeping avoider's graph almost acyclic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6413664"}},"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":"Q2260635$3BEC59E6-7435-49BE-9B7B-641A5E485FA5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9711a5bce712ab4ae83b9b697a50d66465674fa0","datavalue":{"value":{"text":"Keeping avoider's graph almost acyclic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2260635$CC7ECA9C-A1D3-4F9F-B0A1-8FEAFB919A4E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f92fbc40285133b8a493bd5ff8980ddeda77801e","datavalue":{"value":"1312.91024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260635$F7ED265C-CA59-4B7A-A3D9-63EFB5B31931","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$C0487993-4873-4AEF-9668-42503801A6FB","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":"Q2260635$ECC85376-A358-4913-AB9E-92814AC55636","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"aaa340ae51925f6905d18399dfd97774b2ad90cc","datavalue":{"value":{"time":"+2015-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2260635$45710447-3B2B-48B2-A86D-AC9DC0B3E47E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dea27293a7b719b7621c077fc09c2ce1c5471498","datavalue":{"value":"https://arxiv.org/abs/1403.1482","type":"string"},"datatype":"url"},"type":"statement","id":"Q2260635$F19F3E99-27DE-44E0-BEB4-B85CC4F008BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7914deb2b962a3b568811d41bb506380d565a846","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p60","type":"string"},"datatype":"url"},"type":"statement","id":"Q2260635$B931A5EA-390C-43D2-AE7C-7B560D3D2B5C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d7c69e6229129e4757480e55585f0ec2537a4063","datavalue":{"value":"In a general Avoider-Enforcer game we have a finite set \\(X\\) which is called the board of the game, and a subset \\(\\mathcal{F}\\) of the power set of \\(X\\) called the collection of `losing sets'. The two players alternately pick elements of \\(X\\) until all of the elements are chosen. The Avoider wins if at the end of this process he did not pick all of the elements of a losing set. Otherwise the Enforcer wins. In the strict \\((1:b)\\) biased game, the Avoider picks one element at each turn while the Enforcer picks \\(b\\) elements, except in his last move where the Enforcer might have to pick fewer than \\(b\\) elements.  It turns out that the strict biased game is not always monotone. Although very surprising, it might be the case that the Avoider wins the \\((1:b_1)\\) game while the Enforcer wins the \\((1:b_2)\\) game for some \\(b_1 > b_2\\), see [\\textit{D. Hefetz} et al., J. Comb. Theory, Ser. A, No. 5, 114, 840--853 (2007; Zbl 1121.91018)]. For this reason it is also natural to look at the monotone \\((1:b)\\) game where the Avoider picks at least one element while the Enforcer picks at least \\(b\\) elements (except possibly in his last move). As its name suggests this game is indeed monotone.  In this article, the authors show that in both the strict and the monotone \\((1:b)\\) biased games, if \\(n\\) is sufficiently large, \\(b \\geqslant 200n\\log{n}\\) and the board is the edge set of \\(K_n\\), then the Avoider can ensure that his graph can be made acyclic by removing at most one edge. They also show that in the strict game there is a bias \\(b\\) with \\(200n\\log{n} \\leqslant b \\leqslant 201 n\\log{n}\\) such that the Avoider can ensure that his graph is acyclic.  Since an acyclic graph plus at most one edge is planar, 3-colourable and does not contain a \\(K_4\\) minor, the authors deduce corresponding results for other avoidance games improving previously known bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260635$4C011658-7C1A-454D-92C5-9BF2BEF3A2E5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fe719ac6b13db778b87ec3647531213541412700","datavalue":{"value":{"entity-type":"item","numeric-id":396928,"id":"Q396928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$2926A510-4BF3-4AB1-91D3-3240A26E5587","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260635$4CB8FB46-50ED-4369-ADCC-88EC53E1F9D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260635$97818AE0-4CD0-4667-9E8E-379BD223650F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260635$140861A8-868D-45CE-9DBB-814C5929CF14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fbd0918ba2c4a1aeddd30d9d3d146d9773f1239","datavalue":{"value":"91A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260635$9E8B87AB-A602-4838-9A30-4C1DB1C6CE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260635$E49B2CB5-C8B7-45A8-AB23-ACC092316F64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"905492b01fe444acfe48e206e517c2680fbcec3a","datavalue":{"value":"6413664","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260635$AAE84348-9E6F-4692-A07B-3C7630B5ACDD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e226df7958c81afeb01d1d43e25a64e44049b3e0","datavalue":{"value":"positional games","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260635$A7B1FF15-891D-47F2-B2BC-B0847881C0E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39adcd7e1dc747cb1f5c6c97f4a6296cc936195e","datavalue":{"value":"Avoider-Enforcer games","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260635$24A3EBBE-68F2-4B77-84C1-A332AC156323","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a030a2877c0c7eef5b7181bf42ef1ebe034ca0a8","datavalue":{"value":"planarity game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260635$4F2E9B03-4443-4EE5-B8DF-FB38AE9CB344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87fce1d0397df3b297c41c9c5a900be4045b93a8","datavalue":{"value":"threshold bias","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260635$B9418EC6-5657-4727-A858-FFDE239ABF65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7af183da94e7866812043c256c00cc95943f159e","datavalue":{"value":"biased games","type":"string"},"datatype":"string"},"type":"statement","id":"Q2260635$EB1DA68C-324E-4401-930B-3C3CF24FF238","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":"Q2260635$95711DDA-4D1E-47C3-A44C-E879BCE8605A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"666d1d256fe16d5067471fe53e33cc8fa9a85f26","datavalue":{"value":{"entity-type":"item","numeric-id":3663044,"id":"Q3663044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$0A9D9721-B3CD-406E-BC3C-33D227CD1E6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c489e44f72e76e574d639c54e5b6283103ede52","datavalue":{"value":{"entity-type":"item","numeric-id":1598836,"id":"Q1598836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$C90C3741-0EC0-4C01-88FE-7F5BB27D9745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f021f5fad625a2d1b7ae69973379640bb5c12aef","datavalue":{"value":{"entity-type":"item","numeric-id":5386139,"id":"Q5386139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$A918B28F-33D7-467C-8997-AD3B5DD08811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf0644f3dc492e9466f37aa01da6ed58085bf64f","datavalue":{"value":{"entity-type":"item","numeric-id":5932750,"id":"Q5932750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$E52BD3BD-0534-4B00-A2D6-272142A8B271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d12695d4a3731e56edebe1f68edf8feccbdbd8","datavalue":{"value":{"entity-type":"item","numeric-id":4398864,"id":"Q4398864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$32748FA9-40C1-4F66-8101-D798954F5541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff4677d1e0ff5f3afddc0e2681e9b159386e0574","datavalue":{"value":{"entity-type":"item","numeric-id":4152069,"id":"Q4152069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$0B31348B-EF9F-4181-9942-28E1B89A3880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"485a2e2f2e09b6683be2f964ca6251ac93a9e382","datavalue":{"value":{"entity-type":"item","numeric-id":3614201,"id":"Q3614201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$7786CCF3-6001-4177-81E1-6B34B27ECF0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b3f17ba20bfe5b1eb1f36be683d07455e76d577","datavalue":{"value":{"entity-type":"item","numeric-id":966059,"id":"Q966059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$14837F26-06A6-4950-A841-3F385C28C2A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86b6127f4c2e720853f04b970302f324d7dc5962","datavalue":{"value":{"entity-type":"item","numeric-id":2371294,"id":"Q2371294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$838BB545-135F-4DB4-9A46-F708A978AEB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7278f22f8a3f1ae5af2d2949db87ea3001138715","datavalue":{"value":{"entity-type":"item","numeric-id":5511877,"id":"Q5511877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$CE34B137-3E41-4775-A25F-769B24A93D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0899eae2dbf6ae16d0935f08a54e26663d3cbeee","datavalue":{"value":{"entity-type":"item","numeric-id":1182968,"id":"Q1182968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$8ED448D3-784B-4A2F-9CA3-C58CD026B726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2702b7b8f02ffa8047ff82258a8a8562990d0488","datavalue":{"value":{"entity-type":"item","numeric-id":915667,"id":"Q915667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$CDEA69EF-0F7B-4766-8832-717E4B26E3F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d6c2f3b0935a33daa66a44d30800a69a220e67b","datavalue":{"value":{"entity-type":"item","numeric-id":1896354,"id":"Q1896354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2260635$380A7D4C-4F84-464A-A09A-792BCC791D75","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"996e01f67e467b00337776d427a0efd265d0513b","datavalue":{"value":"bafkreieg67njtet2e4ydimp22wvuc2uvuewakyoipcqbrey4255mfqop2u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2260635$A738DE05-6550-4C02-8F63-6CB9279C0C89","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36c8c18e78f5974f5b070b894c22b6a7d30f643e","datavalue":{"value":{"entity-type":"item","numeric-id":5249233,"id":"Q5249233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8407d080dd4e3f04b161b6dcaf1ee1c6ae5424c","datavalue":{"value":{"amount":"+0.8494157195091248","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":"Q2260635$435DD73D-772D-4891-88DD-D5B22248945B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc8d80260e9f027e72109d362d187fcab972f2ac","datavalue":{"value":{"entity-type":"item","numeric-id":966059,"id":"Q966059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1a7ffb12ac17b5ff790d699457f92b1153341bf","datavalue":{"value":{"amount":"+0.8409912586212158","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":"Q2260635$24B685D8-C099-41D6-B5E5-CD43A71B3255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c42c231116f3ae7cabd133a7872013a9b0db1022","datavalue":{"value":{"entity-type":"item","numeric-id":2851474,"id":"Q2851474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0d8134e19a8137c77b4b65158e464b7f3be6d25","datavalue":{"value":{"amount":"+0.8408206701278687","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":"Q2260635$0285CE4B-832E-4415-B703-083049641A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71b45aa1df6edc663115f22819af923d3cac4404","datavalue":{"value":{"entity-type":"item","numeric-id":405059,"id":"Q405059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"523ccd00e09f952934b9a54000baa3aa36da5130","datavalue":{"value":{"amount":"+0.8150891065597534","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":"Q2260635$1EF36C92-F08F-4FE7-BC23-5CA3FC5DC246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccc7ebf0a5ade378ec8511462df67c2bedd08061","datavalue":{"value":{"entity-type":"item","numeric-id":976704,"id":"Q976704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abff877f12cdf61a4e1a5009b5f7f0032afc9688","datavalue":{"value":{"amount":"+0.8109846711158752","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":"Q2260635$9576E4BD-006F-41B4-AF97-B06A68569F52","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2260635","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2260635"}}}}}