{"entities":{"Q726662":{"pageid":728511,"ns":120,"title":"Item:Q726662","lastrevid":63911412,"modified":"2026-04-11T16:23:07Z","type":"item","id":"Q726662","labels":{"en":{"language":"en","value":"Chip games and paintability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6603192"}},"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":"Q726662$8A01781C-85D4-48E5-8609-ABDEF7A68BCF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4febf99b41633e609f3826f66fc0833219c20fb3","datavalue":{"value":{"text":"Chip games and paintability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q726662$E8E82A0B-5FEF-4188-827B-A191F5EA3719","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0afca5ce3ba05a8b57e3a71f803bad784b77c73f","datavalue":{"value":"1339.05129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q726662$B4403E8B-2291-4930-8C61-E7A4E2D41748","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"df807168d2f2d51b81e22503931a4c54a7a38e7e","datavalue":{"value":{"entity-type":"item","numeric-id":726661,"id":"Q726661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$B2F1E4FC-3BEC-490A-B3E6-A52CE80E0BB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf0fae52332c3d590b6cc284261eb4a719b8af85","datavalue":{"value":{"entity-type":"item","numeric-id":551234,"id":"Q551234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$B01E364D-B2AC-432E-A528-74294D39773F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc629f0be60f72a336737629e351e85a1cdd011c","datavalue":{"value":{"entity-type":"item","numeric-id":322291,"id":"Q322291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$5B99E1CF-CE4F-4812-A8E4-FB8545A3D3B6","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":"Q726662$500D0E80-CC3A-47AC-8568-67CE7F02A67F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"15c8aa27298ddeb58875d8d2d9061140a0439971","datavalue":{"value":{"time":"+2016-07-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q726662$ACFDE69A-91B1-4862-95F4-1B8F4DC6C6AA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c4043121047d315f197574a2bc28cf8b50247a33","datavalue":{"value":"https://arxiv.org/abs/1506.01148","type":"string"},"datatype":"url"},"type":"statement","id":"Q726662$B02766FE-D856-4648-9EF5-F877E31B9590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"12eb2c6db1b2dae6b149be79cd51fbd7e0d98a8e","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i3p3","type":"string"},"datatype":"url"},"type":"statement","id":"Q726662$1D2B25E8-2CD5-4336-A2A9-DC30A4D97C49","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"91fb06c165beff35786763bf1fe067f8ee5e9396","datavalue":{"value":"Summary: We prove that the paint number of the complete bipartite graph \\(K_{N,N}\\) is \\(\\log N + O(1)\\). As a consequence, we get that the difference between the paint number and the choice number of \\(K_{N,N}\\) is \\(\\Theta(\\log \\log N)\\). This answers in the negative the question of \\textit{X. Zhu} [Electron. J. Comb. 16, No. 1, Research Paper R127, 16 p. (2009; Zbl 1186.05061)] whether this difference, for all graphs, can be bounded by a common constant. By a classical correspondence, our result translates to the framework of on-line coloring of uniform hypergraphs. This way we obtain that for every on-line two coloring algorithm there exists a \\(k\\)-uniform hypergraph with \\(\\Theta(2^k)\\) edges on which the strategy fails. The results are derived through an analysis of a natural family of chip games.","type":"string"},"datatype":"string"},"type":"statement","id":"Q726662$C05699B0-5C7B-4CFB-9C21-5A7E0C949A84","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q726662$E460AEE8-4561-4E9C-9049-8934D81C5E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2d5a866d412ef8af951814448fda0a03016cd3a5","datavalue":{"value":"68W27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q726662$9C626C83-709C-4FFB-89B1-FB1AE4A5CE80","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f3010f5d820576f436c6ec5cb054ef4368bbe1d7","datavalue":{"value":"6603192","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q726662$29C35AF9-AA1D-488D-A398-7FE862E28D1D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61e6e8d01418719e15aa61073bc585c328090187","datavalue":{"value":"paintability","type":"string"},"datatype":"string"},"type":"statement","id":"Q726662$D85AA522-06D5-4D95-9E0B-611FB8486D30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5f6aefdf1ffec3bc08d67d0b64a04330c0d9134","datavalue":{"value":"list coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q726662$469C3DF1-B74B-4E10-83F2-519979B56211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d115c16db558ace746e1657cf4058017713384fd","datavalue":{"value":"property B","type":"string"},"datatype":"string"},"type":"statement","id":"Q726662$94FFC1ED-C409-413B-AF44-EA58819BFA34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0fca5ac8cddc8f74e7908fc7842929c55342241","datavalue":{"value":"online algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q726662$6B97EACB-3FE2-4537-BC3E-5582B7C5AF86","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":"Q726662$51AA0447-E442-4270-800E-6A0B80EB835A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f80aadf78dae9fc5a0138327cacf9a09e7cfa15","datavalue":{"value":{"entity-type":"item","numeric-id":3142409,"id":"Q3142409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$1600CA1B-5804-46FE-960C-0F49079CE5A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a19e664d4d45826f0e792f05cb09125f3424d5d","datavalue":{"value":{"entity-type":"item","numeric-id":1210300,"id":"Q1210300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$CA07D0B6-6A1E-4CDA-8465-BAADE3767524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71cf2eb493c3866bfb6ee9a0c2fc0d9b9154ec87","datavalue":{"value":{"entity-type":"item","numeric-id":5724800,"id":"Q5724800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$2C322C51-C59C-4E9C-989E-A73B2CB79F73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f3e8aed192df9c937689b0ef93a97de2bb22035","datavalue":{"value":{"entity-type":"item","numeric-id":5599180,"id":"Q5599180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$6A4C6477-6636-4F36-816B-92FD9C3CD3E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46306cc727aecdc2a9ade517dd21e5cfcd5359ba","datavalue":{"value":{"entity-type":"item","numeric-id":5599149,"id":"Q5599149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$D9947F9E-6236-4680-BE9F-9D7B2D848790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3573b87026595a32002fa2dc54ac8b096bc29f3f","datavalue":{"value":{"entity-type":"item","numeric-id":3922703,"id":"Q3922703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$4BE6A47B-762A-4FBE-96B9-A6BF9531BB0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49b1ea8c71c16680a80daa5a278988ba0f26dce6","datavalue":{"value":{"entity-type":"item","numeric-id":1892837,"id":"Q1892837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$E43192AC-7EB2-4CE9-9D12-DEB0ACB3819D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ce0f1b1468a89d8abf4cb623f06bbf4a66af719","datavalue":{"value":{"entity-type":"item","numeric-id":2349182,"id":"Q2349182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$F4AAC07B-A2F9-440F-9AA3-B7D6790F1594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb2ef0ba324755a03a243a2fb7dc2a282848b3b","datavalue":{"value":{"entity-type":"item","numeric-id":4943351,"id":"Q4943351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$F9B54D2E-20A1-472D-A1C1-FBC270AE176A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bcf2b4c2b6c7326a3acf6bf57028e463e8c28e","datavalue":{"value":{"entity-type":"item","numeric-id":2380232,"id":"Q2380232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$F99ABF6B-E7C2-4808-AB05-F18F2CDF9E05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27383f46e729e13b7cb3bb1b17ea6cee53c2ee3d","datavalue":{"value":{"entity-type":"item","numeric-id":612968,"id":"Q612968"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$1057557D-16F7-4ECB-9014-3AD1675D4D21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92077b84d7a6aabab7f2ca3e178b3e89c72e8c83","datavalue":{"value":{"entity-type":"item","numeric-id":2380291,"id":"Q2380291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q726662$ACFA46FC-8038-4AC9-B6C5-AECA9903C2D8","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"5c095b6d320ec6090fcf03e07e061e5b5a2daa7a","datavalue":{"value":"bafkreic6shq4iqtistraiim6xl25iovxvsnwscajundffaw2vpkkstnpw4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q726662$9C2B7A51-551B-4937-A41F-C02BC4586187","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb64e4153363b9a76c30d1d7932364dcf6a3a0ad","datavalue":{"value":{"entity-type":"item","numeric-id":2448254,"id":"Q2448254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"530467bee3c60bec146d4c51fb2146f0410b4ae2","datavalue":{"value":{"amount":"+0.8004319071769714","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":"Q726662$16AF24E3-114C-4E94-BC5D-09FA84F9717C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efa7f9b5f8981860294dfec5931f90a55b56cc96","datavalue":{"value":{"entity-type":"item","numeric-id":1210300,"id":"Q1210300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18f6d23e18714c29e89e242bd8df21e1de62275c","datavalue":{"value":{"amount":"+0.7914486527442932","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":"Q726662$A567C9CD-B138-41C4-A33A-F65CFD6DB2F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cebb9de4ca49f313c416efb03de134547f86c1c6","datavalue":{"value":{"entity-type":"item","numeric-id":490305,"id":"Q490305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f4e4d732cab65dc97bec229e35fb9eff9478fa5","datavalue":{"value":{"amount":"+0.7878032922744751","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":"Q726662$1B9FDA0E-88F8-4FC4-A587-27CF79E9F635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa4c0ec4c721b2cd131ed141a9f6b01635c3794a","datavalue":{"value":{"entity-type":"item","numeric-id":2657183,"id":"Q2657183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d629f1f7042cbaf5bd5c4220169f1e4e1cbb159a","datavalue":{"value":{"amount":"+0.7875423431396484","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":"Q726662$AC469F62-4104-4DC7-8DBB-618491FA9BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6489b0f6c18381bd5cef0ea0ea3c57decb1e4303","datavalue":{"value":{"entity-type":"item","numeric-id":551235,"id":"Q551235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"361a24d2f05854b224030a39cf33469cc168dc8f","datavalue":{"value":{"amount":"+0.7624421715736389","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":"Q726662$7DBB13C1-7314-4DF8-A32D-D913CC104FA6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Chip games and paintability","badges":[]}}}}}