{"entities":{"Q521366":{"pageid":523133,"ns":120,"title":"Item:Q521366","lastrevid":62467371,"modified":"2026-04-11T06:17:57Z","type":"item","id":"Q521366","labels":{"en":{"language":"en","value":"Guessing numbers of odd cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6703737"}},"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":"Q521366$4C4E9F80-DD21-42BB-A1EF-B1947F5E882B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9470a04e5d80ac22c9edf3c13076fd44f2a32831","datavalue":{"value":{"text":"Guessing numbers of odd cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q521366$321CFAB6-5175-431C-89F6-155F44732F52","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3f1b574dab5135926e85cb8f716c3a0af4c8b856","datavalue":{"value":"1358.05092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521366$7AB291BB-6A5A-4444-8A42-9C2B223EF02B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"663c079ac4c39d30514edebf1ce75337bd10e88f","datavalue":{"value":{"entity-type":"item","numeric-id":521364,"id":"Q521364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$732107F8-1914-4EFC-B2EA-F4C5DAAB54FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d36984850a1b5b0787ddd1e3103be649672d7d33","datavalue":{"value":{"entity-type":"item","numeric-id":521365,"id":"Q521365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$7528A41A-34C7-4C94-846D-41DFBE88D5E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"52794ea33618a13587baa1033cd1b0861d6409cf","datavalue":{"value":{"entity-type":"item","numeric-id":247201,"id":"Q247201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$FBD97FF6-4893-41A3-ABF8-4DA73691DC72","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":"Q521366$F68F8253-1AF1-44DD-911B-A6C54785A3EC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c018a10501084d0b87c78551bc55b3f7e17eb53","datavalue":{"value":{"time":"+2017-04-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q521366$F714E6FE-6F2B-4946-90DC-4270EB513024","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52d1f1b5eadca212cab833fb25b945f0c9bb1f84","datavalue":{"value":"https://arxiv.org/abs/1602.03586","type":"string"},"datatype":"url"},"type":"statement","id":"Q521366$E8F4E8DB-B81F-496F-8EB7-22E408B94ADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"211d8922414cc547fe316cb6757ca1dea2cc32ca","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p45","type":"string"},"datatype":"url"},"type":"statement","id":"Q521366$4FA78A61-9972-4F3B-B2AB-A3D178D69067","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6506622891be37c3b1b63e78930e8bf72ca74b73","datavalue":{"value":"Summary: For a given number of colours, \\(s\\), the guessing number of a graph is the base \\(s\\) logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. An upper bound for the guessing number of the \\(n\\)-vertex cycle graph \\(C_n\\) is \\(n/2\\). It is known that the guessing number equals \\(n/2\\) whenever \\(n\\) is even or \\(s\\) is a perfect square. We show that, for any given integer \\(s \\geq 2\\), if \\(a\\) is the largest factor of \\(s\\) less than or equal to \\(\\sqrt{s}\\), for sufficiently large odd \\(n\\), the guessing number of \\(C_n\\) with \\(s\\) colours is \\((n-1)/2 + \\log_s(a)\\). This answers a question posed by \\textit{D. Christofides} and \\textit{K. Markstr\u00f6m} [Electron. J. Comb. 18, No. 1, Research Paper P192, 19 p. (2011; Zbl 1337.05077)]. We also present an explicit protocol which achieves this bound for every \\(n\\). Linking this to index coding with side information, we deduce that the information defect of \\(C_n\\) with \\(s\\) colours is \\((n+1)/2 - \\log_s(a)\\) for sufficiently large odd \\(n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q521366$F9A79170-2382-4425-A4ED-A4AAD9E6CA96","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521366$96B3F79C-AC92-4317-B80C-D599BD2073B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521366$6D617A06-AADA-43A6-ACE7-6A43F38D1DD3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f38802fcff4317196e5181ef8df463b6e337a4cc","datavalue":{"value":"6703737","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521366$706EE44B-A25A-498F-914E-D24F48BE744D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91cd2c0293b6c1ab7aeabab5aa25169e6f5e7b6b","datavalue":{"value":"guessing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q521366$9DA5D8D6-183E-44E0-9645-1B5236865608","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q521366$B8E614DE-72B2-4C90-BC61-29D49F4B3710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9fa0f365e6704c0d3eca0409b798149cf0cd2865","datavalue":{"value":"information defect","type":"string"},"datatype":"string"},"type":"statement","id":"Q521366$0047AC0F-86BE-4B39-87AC-46D8D824CE58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3687b97f685f2e933c151d213f91c2c68eb6b0c6","datavalue":{"value":"index coding","type":"string"},"datatype":"string"},"type":"statement","id":"Q521366$27DAFE89-1AB6-4EEB-BFA6-C6B9BA32FC8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84f2a31aea37ef24c63bf588138bcc1bcc9096c3","datavalue":{"value":"multiple unicast","type":"string"},"datatype":"string"},"type":"statement","id":"Q521366$A86CC675-04F9-4BC6-A013-52A010DB5D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c2e069b1a2184cd3b0f52ffa83b5fcb89125e86","datavalue":{"value":"entropy","type":"string"},"datatype":"string"},"type":"statement","id":"Q521366$5A53CA0A-8E63-423D-801C-BB75703483D0","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":"Q521366$C0E12D76-3C13-49EB-8882-8C3F07037047","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"72fe0ec44efa8fde458e9b5c8560356ff77ddb2b","datavalue":{"value":{"entity-type":"item","numeric-id":5358568,"id":"Q5358568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$0C24AFC5-A63A-428C-ADAE-E450A469EE7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05f02ca034d62b829540b6bc49fecbe490abfb62","datavalue":{"value":{"entity-type":"item","numeric-id":5281034,"id":"Q5281034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$0860CFAD-38F6-4228-B700-8FDF8721294D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73c8e13615b1f5d5eac693e690c34715ce928d1d","datavalue":{"value":{"entity-type":"item","numeric-id":5902082,"id":"Q5902082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$389102BC-2393-4DB1-9A48-FD32AAED7F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1272f5456e8e79a9293fa71f0dc9778b2d691ad","datavalue":{"value":{"entity-type":"item","numeric-id":278884,"id":"Q278884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$B21BDD51-54F0-4FE2-A5E1-3B8661C0C23B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b349b2f1ad0a4074f3a73d3d62901240c229e4bc","datavalue":{"value":{"entity-type":"item","numeric-id":2447965,"id":"Q2447965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$9CBF6F73-7189-4502-9C5D-BDA4485C2338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af9db6d262ff1398c9aaaf06b165d16d53838ffe","datavalue":{"value":{"entity-type":"item","numeric-id":640453,"id":"Q640453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$38DDEDA8-F8B3-494C-9D5E-CBACC968D53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763e3905bf47dfe4b400832ecce38198b0d97320","datavalue":{"value":{"entity-type":"item","numeric-id":5490912,"id":"Q5490912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$E71B524F-2F4B-4ED6-A146-2AE3AD54A083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a898a09efff71a0a6d4b9fc991409dc793d4c405","datavalue":{"value":{"entity-type":"item","numeric-id":3548078,"id":"Q3548078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$D71C03AA-7D48-4EE2-9FCC-F6150DA168A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fb5afb97ea0d8112ed4c35661851a62c69dd4a3","datavalue":{"value":{"entity-type":"item","numeric-id":5272296,"id":"Q5272296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$F51CB68A-4E4F-40A4-B06B-AD99BF960FF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1511d3b31952d21f6514cafeee2d1ad2fbd17dc","datavalue":{"value":{"entity-type":"item","numeric-id":976746,"id":"Q976746"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$3DACEDBD-F69B-4FE1-B1C6-FD03FC133E6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc6e42bbd28ad0df988766a128f5b2916ee17be6","datavalue":{"value":{"entity-type":"item","numeric-id":2372888,"id":"Q2372888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$1F0077A9-F77F-4280-8510-69C8B1C34FE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5c4a601da2dfbee44289940f692f1ad4e018855","datavalue":{"value":{"entity-type":"item","numeric-id":1026230,"id":"Q1026230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q521366$309B626C-6429-4C57-9F76-95C04BE787A3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ff44ee1d2e49c56ebef19f9613bd5404a4c8e243","datavalue":{"value":"bafkreidteufxfvmxwtaypsb4sohvyf63xoonyrgih7nlg5os5h6bxipdw4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q521366$D60F23A3-BFFE-428C-9E7D-9E5FE43E8E78","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9906d3f0f1098d65420b89b968b30d5dea79f92c","datavalue":{"value":{"entity-type":"item","numeric-id":2152800,"id":"Q2152800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4717ae86b99ee495469bdbe707f8a7921035dea0","datavalue":{"value":{"amount":"+0.8151787519454956","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":"Q521366$FC98825A-6886-423F-9CF9-0902D6736390","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f417cb0b0c290c0365423fe2fcdc118ee139d5ac","datavalue":{"value":{"entity-type":"item","numeric-id":640453,"id":"Q640453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0e77dfd9c486ea3d1c5f267c6062baf619b0357","datavalue":{"value":{"amount":"+0.8132604360580444","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":"Q521366$3E49A028-461A-40E4-A5FC-8EC03A160A00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5df6e9afd2a864b3f6509ef6a8cad4d4b351f5f1","datavalue":{"value":{"entity-type":"item","numeric-id":1026230,"id":"Q1026230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db0beb62b87edf64875013a8cfe4da9993c6c771","datavalue":{"value":{"amount":"+0.7832668423652649","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":"Q521366$DF95ECDF-70E9-4BB7-89E9-1ACAB15840E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"687851973e1c5fa80b52bd69120b43fe45294729","datavalue":{"value":{"entity-type":"item","numeric-id":278884,"id":"Q278884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1919240260360cc198559837ca14bfccf6608d8","datavalue":{"value":{"amount":"+0.7828309535980225","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":"Q521366$49373591-9CED-47EF-831B-B5A36D3AE8E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1af0bdcc6649a7b9269564635d7ace141d2d4ead","datavalue":{"value":{"entity-type":"item","numeric-id":2447965,"id":"Q2447965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d8b8966d7a53832023a9c1c02a11f8ae5602173","datavalue":{"value":{"amount":"+0.7765307426452637","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":"Q521366$EB91EAA2-EC63-47AB-A3D1-235B675C9B2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Guessing numbers of odd cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Guessing_numbers_of_odd_cycles"}}}}}