{"entities":{"Q976704":{"pageid":978552,"ns":120,"title":"Item:Q976704","lastrevid":57309192,"modified":"2026-03-30T09:11:26Z","type":"item","id":"Q976704","labels":{"en":{"language":"en","value":"On winning fast in Avoider-Enforcer games"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5721450"}},"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":"Q976704$82E87353-E549-42D1-BDA0-726CDA30CE6D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6689e9078294d751a2bf8d5ac4e8c6389320c753","datavalue":{"value":{"text":"On winning fast in Avoider-Enforcer games","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q976704$8C016F2D-EAEE-4C6D-BEC5-71EDE8CCC4AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0412f677f81c8e933a6e968943e135efbdc49f86","datavalue":{"value":"1192.91037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q976704$726F9F2F-B292-476D-98E1-7A145B886BCB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"128ea2f3fc3f9dd84635387102467d325ee845b5","datavalue":{"value":{"entity-type":"item","numeric-id":215792,"id":"Q215792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q976704$DA32C2BE-B92E-4EA5-8737-2CA377A77D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad80b46d1148c8bd4ffa9e245db057048dfa5936","datavalue":{"value":{"entity-type":"item","numeric-id":377491,"id":"Q377491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q976704$41FC5D82-2ADF-45BD-A6C7-6CF68DB6998F","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":"Q976704$A6E9893B-34BB-45D4-B05B-BCD82CD63753","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"66b34ed5dc0f3fc5384918e70a0007292dca094b","datavalue":{"value":{"time":"+2010-06-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":"Q976704$32A493B4-D8BE-435E-9D66-EED2A206A39D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2f9ab62df152f5fc45a59b8b1dfa15e0243552f3","datavalue":{"value":"https://arxiv.org/abs/0910.4402","type":"string"},"datatype":"url"},"type":"statement","id":"Q976704$D0DD8A8E-D360-4A90-8DBE-56B46DA9CBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"dca523f08141c158d47559e63efb5c9f855a781d","datavalue":{"value":"https://eudml.org/doc/224193","type":"string"},"datatype":"url"},"type":"statement","id":"Q976704$34FA7D5F-B97F-4250-B884-0E5BF7F8793A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ceee993d0f6d5411994ffd45dd6b56cfd75f9eb7","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r56.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q976704$6F6A724C-3DFE-4E41-AEF8-34983C2409AD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"03b939d265d4dc08b7cadae31f6c3d2cfaebe204","datavalue":{"value":"Summary: We analyze the duration of the unbiased Avoider-Enforcer game for three basic positional games. All the games are played on the edges of the complete graph on \\(n\\) vertices, and Avoider's goal is to keep his graph outerplanar, diamond-free and \\(k\\)-degenerate, respectively. It is clear that all three games are Enforcer's wins, and our main interest lies in determining the largest number of moves Avoider can play before losing.  Extremal graph theory offers a general upper bound for the number of Avoider's moves. As it turns out, for all three games we manage to obtain a lower bound that is just an additive constant away from that upper bound. In particular, we exhibit a strategy for Avoider to keep his graph outerplanar for at least \\(2n-8\\) moves, being just 6 short of the maximum possible. A diamond-free graph can have at most \\(d(n)= \\lceil\\frac{3n-4}{2}\\rceil\\) edges, and we prove that Avoider can play for at least \\(d(n)-3\\) moves. Finally, if \\(k\\) is small compared to \\(n\\), we show that Avoider can keep his graph \\(k\\)-degenerate for as many as \\(e(n)\\) moves, where \\(e(n)\\) is the maximum number of edges a \\(k\\)-degenerate graph can have.","type":"string"},"datatype":"string"},"type":"statement","id":"Q976704$FA08FD93-6C2A-4A18-9395-E30E9C2B3897","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q976704$D6EA9141-5AB6-414C-BF84-79BF67249160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fbd0918ba2c4a1aeddd30d9d3d146d9773f1239","datavalue":{"value":"91A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q976704$41EEAACF-240B-4205-9A87-0F4B7F232D0B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"357d5f0e0ac98f040a04441d3f54d70eaffc671e","datavalue":{"value":"5721450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q976704$F58860C2-57C0-4CA7-A37D-A7C1CEA9D168","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"37d350bde689f064068899e0968df84d2eee7e87","datavalue":{"value":"avoider","type":"string"},"datatype":"string"},"type":"statement","id":"Q976704$124F3103-5621-4E97-91EA-8E9BF465DF0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"650ec312a19add6cf5d7044d682ee407939131c8","datavalue":{"value":"enforcer","type":"string"},"datatype":"string"},"type":"statement","id":"Q976704$7C68D303-E778-4D55-82C2-B06CD2BC6EB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013a665df3872df6518b386ba286fc369d4eed69","datavalue":{"value":"extremal graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q976704$7D930153-8F4E-49DA-B603-1FFE910E7070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"429780829b68b60d1b6e316cdeb433a38795ec80","datavalue":{"value":"diamond-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q976704$137D162D-0956-49CB-A60F-924E88455361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf93f082a91a712924057cec95f47b5382c4c672","datavalue":{"value":"\\(k\\)-degenerate graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q976704$780C061F-78CF-4738-9B34-79EA3844D93E","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":"Q976704$54B35066-1E0C-4583-92E7-A937EA53C408","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"53db2a051a5cb8160007ced217d47d84c280a099","datavalue":{"value":"bafkreihipwkc5mxqzh6ifgfyxexyoyvo7adie2ayrtvop4qx357vinsigy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q976704$85B53131-B6CE-4736-90A5-71970D6605AC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65da984c48582856f5b94b382b2dcc46036a6ef7","datavalue":{"value":{"entity-type":"item","numeric-id":844236,"id":"Q844236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a55ad1566d730f58dd6de040090a4ae1a71ba188","datavalue":{"value":{"amount":"+0.9770255","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":"Q976704$ECE21A4F-8D1D-4C95-BAEC-4FA0385ABAAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd060a45b2d50299e713236973fb9321b46691b9","datavalue":{"value":{"entity-type":"item","numeric-id":3563950,"id":"Q3563950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a48c74d303ec2c53f5223ebc4d71b2ca5ab45b6d","datavalue":{"value":{"amount":"+0.91657984","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":"Q976704$704898C8-C012-45F6-8626-0564AC989111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5416b59f65f32762648accb7586feae128bd2b60","datavalue":{"value":{"entity-type":"item","numeric-id":2312614,"id":"Q2312614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60e4271cc62ce28e533cfc01e436efee883fc04c","datavalue":{"value":{"amount":"+0.862991","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":"Q976704$9039F5CF-483B-4FF8-B1EA-5E174FD62317","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3b19ba65a2bbcd9e2b9a183135c81fd63cf36b5","datavalue":{"value":{"entity-type":"item","numeric-id":1690027,"id":"Q1690027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af99ba5ca1d202e645bb9de3c212973e65122ee5","datavalue":{"value":{"amount":"+0.8599605","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":"Q976704$F466CB52-F554-4E65-A38C-98E13A9F6497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85a2b5df74a6d6fe27655dfb26a89f1e9aa575b5","datavalue":{"value":{"entity-type":"item","numeric-id":322263,"id":"Q322263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a195d2961e8668883c110ac1005693a6cb63177","datavalue":{"value":{"amount":"+0.85649306","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":"Q976704$79F25BD8-3431-4C1B-B7E3-9CAC5235F164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"873937c8d8d4d98d940686d67a7885aefaf50087","datavalue":{"value":{"entity-type":"item","numeric-id":2111931,"id":"Q2111931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4e4679b64e55486f88f7c4602492787aabb8cbd","datavalue":{"value":{"amount":"+0.8526211","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":"Q976704$2B530D42-1180-4D33-9549-CB8D9B4070BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a24c871d1c376690002cff0c8d9d1b97bf855f80","datavalue":{"value":{"entity-type":"item","numeric-id":4560259,"id":"Q4560259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48e0c6a6904633fb86e11ea3040538aa0d2b47cd","datavalue":{"value":{"amount":"+0.851033","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":"Q976704$DF95B457-358F-4ED1-B9E3-6EC20626ED95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c636dda9d14a98c186c0cf7ea6712fec9767b890","datavalue":{"value":{"entity-type":"item","numeric-id":2519013,"id":"Q2519013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a51c001f0ea5f9bbc05681462a5627c1b6610ce","datavalue":{"value":{"amount":"+0.8471666","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":"Q976704$F3744E6E-43FD-47D0-9E30-B9C7AB2DE154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3471c1bbcf644ee0ac7bbf4da473f1e9b3a5e0d1","datavalue":{"value":{"entity-type":"item","numeric-id":2371294,"id":"Q2371294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d20fc75af28c7f3ffe9ff825cac6acef4e4198c7","datavalue":{"value":{"amount":"+0.84169436","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":"Q976704$58679907-5332-4BF8-9DCD-1A25891B275D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a0464b26ea91990740c50f4f5b19b21800b0bb3","datavalue":{"value":{"entity-type":"item","numeric-id":2200433,"id":"Q2200433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6694f949d322d3aba2f8f79989f5859e14b92137","datavalue":{"value":{"amount":"+0.8391113","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":"Q976704$60327516-1C60-4BB0-B423-C977E4EFE9EC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:976704","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:976704"}}}}}