{"entities":{"Q907253":{"pageid":909101,"ns":120,"title":"Item:Q907253","lastrevid":57217350,"modified":"2026-03-27T12:21:32Z","type":"item","id":"Q907253","labels":{"en":{"language":"en","value":"Low degree Nullstellensatz certificates for 3-colorability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6534989"}},"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":"Q907253$C8FD231B-25FD-44BD-80EF-29252B7EE356","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"daea0f7e28fc4fff11f6454f82e3227c4f978962","datavalue":{"value":{"text":"Low degree Nullstellensatz certificates for 3-colorability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q907253$A103FC40-D83D-41DB-BD15-6F91A4A2A4CF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af89d972251b57c4f0ba0303bb3b9ba5e67903a3","datavalue":{"value":"1329.05114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907253$882F9B70-F8FE-4543-B1B7-AFF46F105674","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c5832f8876614de1887b6fff71a1066143db327e","datavalue":{"value":{"entity-type":"item","numeric-id":786129,"id":"Q786129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$9CA90990-C14E-4A06-B8B6-536BF6208EC3","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":"Q907253$5C94C6B0-A6D2-4FDB-A416-A750D1FE2004","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e3f0504cdbec36416c8068369865aa5a0a508332","datavalue":{"value":{"time":"+2016-01-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q907253$F6D43D24-7EAA-4566-97D8-6981DD8F3949","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a2b9d2812ac918fe1ba4d3932f796ff18aa2d19c","datavalue":{"value":"https://arxiv.org/abs/1503.04680","type":"string"},"datatype":"url"},"type":"statement","id":"Q907253$FF55D9D9-AEBF-4004-B3EA-1201756A3961","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"edbdcad2b21967506c6d6d7b484c3ef5e18c3fbf","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p6","type":"string"},"datatype":"url"},"type":"statement","id":"Q907253$45FDAB3A-6CD0-49E3-9714-E6FF19AB8CE7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"998cce1d0086fe2b30110213e3ea827232ece053","datavalue":{"value":"Summary: In a seminal paper, \\textit{J. De Loera} et. al [in: Proceedings of the 2008 international symposium on symbolic and algebraic computation, ISSAC 2008, Linz/Hagenberg, Austria, July 20--23, 2008. New York, NY: Association for Computing Machinery (ACM). 197--206 (2008; Zbl 1297.05229)] introduce the algorithm NulLA (Nullstellensatz Linear Algebra) and use it to measure the difficulty of determining if a graph is not 3-colorable. The crux of this relies on a correspondence between 3-colorings of a graph and solutions to a certain system of polynomial equations over a field \\(\\Bbbk\\). In this article, we give a new direct combinatorial characterization of graphs that can be determined to be non-3-colorable in the first iteration of this algorithm when \\(\\Bbbk=\\mathrm{GF}(2)\\). This greatly simplifies the work of De Loera et. al [loc. cit.], as we express the combinatorial characterization directly in terms of the graphs themselves without introducing superfluous directed graphs. Furthermore, for all graphs on at most 12 vertices, we determine at which iteration NulLA detects a graph is not 3-colorable when \\(\\Bbbk=\\mathrm{GF}(2)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q907253$EF9B54F7-57E0-4533-8D3C-63DCAB498A3A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907253$930D38CE-2EFE-4F54-BE70-0C71CDA8929B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907253$DB825073-99A1-4A66-B3C1-A675D27DBDDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907253$8A1EB0CE-F056-49D9-9290-641F8C44C2AC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"10fbffafbeaf7a85fa2d58bd29773ddbd1da908b","datavalue":{"value":"6534989","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907253$25804DA2-9542-4C99-ACF4-84F3A3250C9E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9950f0ecad7327f41cdd0f04d6a09a9c1f9b92b0","datavalue":{"value":"polynomial equations over a field \\(\\mathbb{k}\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q907253$61785D8F-6684-4BC8-B932-CC07DE036BA6","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":"Q907253$786F9D14-1237-4577-A151-3088E90EE65F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"180dcdcd70e7dd722922a02e19e8df3d14ff3abb","datavalue":{"value":{"entity-type":"item","numeric-id":3413659,"id":"Q3413659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$012BD95C-BCD3-4734-B55F-E7B19E58F4D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"160d46d3b85faa2369b490324d6bd2ccf1ce0c28","datavalue":{"value":{"entity-type":"item","numeric-id":1960266,"id":"Q1960266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$EE0A77B7-69ED-4C94-84C8-1C89CB46A6B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f2924350d5ad77088d9baa85e630b9c6d32a0bc","datavalue":{"value":{"entity-type":"item","numeric-id":5301623,"id":"Q5301623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$27F15FB2-18C4-4C6A-A442-86196E782FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0fc6a82f70e2435255f603104335428b4c6bb0e","datavalue":{"value":{"entity-type":"item","numeric-id":3552513,"id":"Q3552513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$91D9B370-9E58-4373-BB21-082F8FC74B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e3933e7517ee5a24d9ac15664a52523f3908dbf","datavalue":{"value":{"entity-type":"item","numeric-id":3058523,"id":"Q3058523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$B2C27ED6-7A7A-4BDC-896C-2D1D2732E5AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98ca987cd31fcda273faf7f829a209009518eeda","datavalue":{"value":{"entity-type":"item","numeric-id":2706355,"id":"Q2706355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$F0D1C7EF-7CD9-4F7E-A526-F18E0EF81B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8ec8f6f81428bd8769215213b5291205ed0250d","datavalue":{"value":{"entity-type":"item","numeric-id":1313833,"id":"Q1313833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$E5E3812F-7E1D-44B5-BF4F-047710FD5F11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c94d017d89fe8a00bee910dd24c96d75202f025b","datavalue":{"value":{"entity-type":"item","numeric-id":4012419,"id":"Q4012419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$3E825884-7E3D-4DE8-9D90-91D7FAB99C29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b16b085550aa0b1ff43e0d0657a0dce948d880","datavalue":{"value":{"entity-type":"item","numeric-id":2467358,"id":"Q2467358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$7C4EED61-F5C5-4EEB-AC9D-EA30E8F14FCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b44fcaa1f05407395b26870122229a43ea361110","datavalue":{"value":{"entity-type":"item","numeric-id":3197621,"id":"Q3197621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$10A0FAA6-64BC-49D6-9EBB-2CEB2D357A87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"298ef5d69d0899859f4551080d5281f2074896cd","datavalue":{"value":{"entity-type":"item","numeric-id":5311854,"id":"Q5311854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q907253$DC86D716-29BE-4AD5-8631-39F073C7AB31","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"7bc5156eb8b39b68904cd6aefd76373f99bb094f","datavalue":{"value":"bafkreic2yijojurruwajzz2kao7y6gwgxmza44ipl62xklway4jnzkrsma","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q907253$707FA4A0-61F1-4170-9DD1-2E102FAAB839","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92b2ea1248f4237dfd3ef015257fa8970c415085","datavalue":{"value":{"entity-type":"item","numeric-id":650840,"id":"Q650840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc1d81c55a271228b0b4255216cc2d21cbf08b9e","datavalue":{"value":{"amount":"+0.8074583411216736","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":"Q907253$F1AAEF8B-C09A-48B8-A3E8-007486C0EFE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ca2f9b5bd991eca2ad9d39899604c5b311fc32d","datavalue":{"value":{"entity-type":"item","numeric-id":5301623,"id":"Q5301623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6eca94f80452849a79da12353660d5e86d9a5a08","datavalue":{"value":{"amount":"+0.803290069103241","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":"Q907253$6EC13300-6F46-492C-8CBB-CD2CFD300D4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"441416c8d61a70b566794b47705802e4326c642f","datavalue":{"value":{"entity-type":"item","numeric-id":3552513,"id":"Q3552513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2092e919d9083dc57a845be6d53f41e27579da5d","datavalue":{"value":{"amount":"+0.783375084400177","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":"Q907253$24656CA1-9F5D-4414-94D4-32E2FDAE964C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18f7bda9f6a6c2c397a74f950cb016da56c76b32","datavalue":{"value":{"entity-type":"item","numeric-id":5111132,"id":"Q5111132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc9cabea3bb7f70bab0dc23a3b0147058058efd4","datavalue":{"value":{"amount":"+0.7829574942588806","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":"Q907253$F0EEFA20-DED8-4647-95D4-9DB37C48FECC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b4f750b0d94445415c88d181cf9ae1b370b081b","datavalue":{"value":{"entity-type":"item","numeric-id":1711835,"id":"Q1711835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c6620e03b0d851687ed789dce06a20cbde883d1","datavalue":{"value":{"amount":"+0.7784466743469238","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":"Q907253$BC4C4931-13CA-4E2D-87A3-3E53A566DA11","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:907253","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:907253"}}}}}