{"entities":{"Q1953415":{"pageid":1964157,"ns":120,"title":"Item:Q1953415","lastrevid":57627144,"modified":"2026-03-31T16:31:26Z","type":"item","id":"Q1953415","labels":{"en":{"language":"en","value":"New computational upper bounds for Ramsey numbers \\(R(3,k)\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6171869"}},"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":"Q1953415$3F5F482F-89EB-4949-A651-871F6E5EFA8A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"42cbf2d081232a1f39568c02ec04f7d436117dfc","datavalue":{"value":{"text":"New computational upper bounds for Ramsey numbers \\(R(3,k)\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1953415$23010300-CF93-4F3C-9ACD-B072481115BB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e0a272548b7aace7dd19eaee9dd8ce8d9ed8e12e","datavalue":{"value":"1266.05089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953415$D2ACF7EF-F12B-4787-92A0-C46988D2F241","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"972af8c62b49c1d10bf4175c5f7cd9d287de96e7","datavalue":{"value":{"entity-type":"item","numeric-id":396939,"id":"Q396939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953415$6B180C18-16D0-4FAC-997B-851A2BC6D30F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b407a0079d2053b1888e0d3f841e6710d7a1ac63","datavalue":{"value":{"entity-type":"item","numeric-id":1010890,"id":"Q1010890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953415$A2C3529C-9D5B-48C6-997C-F3EE2B2C07D3","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":"Q1953415$D1B0B8D6-546C-4F4D-BD05-4752E934CBB0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4a8303ee696998ba030c9b1c3b6bc07c6038c334","datavalue":{"value":{"time":"+2013-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1953415$7C4A4333-D6EC-4D1B-A149-6CAF94487070","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e92550a5476a828826c984a5f2daf9e4e069ae87","datavalue":{"value":"https://arxiv.org/abs/1210.5826","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953415$6933FA60-5555-444C-B206-3F6CC3B40260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"bd27b1b48e04cf04b0a20f0dc34eb350ff4e9293","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p30","type":"string"},"datatype":"url"},"type":"statement","id":"Q1953415$A73AFB89-DD77-48BB-A480-A82F871B6159","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7589c3d4f83751be2bce6578fdce7df6886a2ab5","datavalue":{"value":"Summary: Using computational techniques we derive six new upper bounds on the classical two-color Ramsey numbers: \\(R(3,10) \\leq 42\\), \\(R(3,11) \\leq 50\\), \\(R(3,13) \\leq 68\\), \\(R(3,14) \\leq 77\\), \\(R(3,15) \\leq 87\\), and \\(R(3,16) \\leq 98\\). All of them are improvements by one over the previously best known bounds.     Let \\(e(3,k,n)\\) denote the minimum number of edges in any triangle-free graph on \\(n\\) vertices without independent sets of order \\(k\\). The new upper bounds on \\(R(3,k)\\) are obtained by completing the computation of the exact values of \\(e(3,k,n)\\) for all \\(n\\) with \\(k \\leq 9\\) and for all \\(n \\leq 33\\) for \\(k = 10\\), and by establishing new lower bounds on \\(e(3,k,n)\\) for most of the open cases for \\(10 \\leq k \\leq 15\\). The enumeration of all graphs witnessing the values of \\(e(3,k,n)\\) is completed for all cases with \\(k \\leq 9\\).    We prove that the known critical graph for \\(R(3,9)\\) on 35 vertices is unique up to isomorphism. For the case of \\(R(3,10)\\), first we establish that \\(R(3,10)=43\\) if and only if \\(e(3,10,42)=189\\), or equivalently, that if \\(R(3,10)=43\\) then every critical graph is regular of degree 9. Then, using computations, we disprove the existence of the latter, and thus show that \\(R(3,10) \\leq 42\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953415$EF05946E-D947-4699-A202-13B657B3AD4B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953415$CE7CE12E-DF66-43B4-BD01-FC6111E5CA16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953415$2725DF14-9DC1-46C6-9BDB-FDD76EA9FBC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953415$85EBA274-98F4-4353-9F76-6E3B8DC6228D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f1a83f1ecaecdbc5308da47847ddb0c8b72138c6","datavalue":{"value":"6171869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953415$87D3F014-48FC-40D2-A5E0-AE6A00FE4644","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e72afdfbe4fade6720cebe4d868b61e062448960","datavalue":{"value":"classical two-color Ramsey number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953415$BE1C5F78-383C-4BCA-90CB-D6BFD4F18E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953415$5C5D1ABC-D750-45D1-A381-E03623F85897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90b2ed3c130c30bac7174fa9b54a06645cc1227f","datavalue":{"value":"computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1953415$D8CF2CC3-3AFD-4505-A390-741B938F578A","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"58012661cd5902d08c1d307a106ffc22f40d0c6b","datavalue":{"value":{"entity-type":"item","numeric-id":13366,"id":"Q13366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953415$EC8F24D7-D852-49CF-9FD7-8F5623CE3EA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"031b6d55b66743bef91b3bf43f95b2a97b46f8c1","datavalue":{"value":{"entity-type":"item","numeric-id":18775,"id":"Q18775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953415$20FD0C5F-7356-4FAC-9DD1-965D429FE035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"ca5533989432ab3feed631571cd202eec61fde0a","datavalue":{"value":{"entity-type":"item","numeric-id":38699,"id":"Q38699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1953415$27FEBCD4-6DC7-4D98-9C24-CF54F0884811","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":"Q1953415$3CB7A828-9B05-40E1-A299-13FD1CE931CB","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"547f35bdea1026ea87e668b58f6622e94d5f07ff","datavalue":{"value":"bafkreigsvp43pqwbqsdj23i4viea4r7cptlv3emnrpkuc2mlfqyrk4vszm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1953415$DB74C492-6B1A-40EF-8F72-B22A46C6954F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09657bef2a36a39c6be4d28a76bde4495d57b629","datavalue":{"value":{"entity-type":"item","numeric-id":396940,"id":"Q396940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6d07ccfdf8f66c7163c6701e9e55bb410a57b4a","datavalue":{"value":{"amount":"+0.9182329773902892","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":"Q1953415$3E748FA2-34D2-4C6C-989B-B8F72AEBD937","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69e6a40e849b53fa5516136b343591034e269e4f","datavalue":{"value":{"entity-type":"item","numeric-id":4733883,"id":"Q4733883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44b02e9d5a292b382bbe57c81d6e1ca8352f9a22","datavalue":{"value":{"amount":"+0.8906394839286804","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":"Q1953415$71B3BB29-8497-419C-984D-FED4918065FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebdfa85fdc03648ab3cf35287fea8c6269710244","datavalue":{"value":{"entity-type":"item","numeric-id":4256003,"id":"Q4256003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d9e943298da281f03576c08bf27c9771d0144b6","datavalue":{"value":{"amount":"+0.8488687872886658","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":"Q1953415$826F843A-CF4F-41AA-A236-B8FF9F655E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ef6de785bdb379f82af6056646850ad1205dd661","datavalue":{"value":{"entity-type":"item","numeric-id":5463479,"id":"Q5463479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c05c2432a9f83b13100750f6f6c7af9bc2e11ee8","datavalue":{"value":{"amount":"+0.8481686115264893","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":"Q1953415$EE763EF3-2D3B-4101-A49E-6751A51E82F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9868eb6463d005af1df7cfc0d10b4009e572692","datavalue":{"value":{"entity-type":"item","numeric-id":4393385,"id":"Q4393385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2251e7297e78db1bcb05f0fca8d755e8bf9836db","datavalue":{"value":{"amount":"+0.844832718372345","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":"Q1953415$935B78BC-DF03-4C85-A3F0-C62AB72F67A5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1953415","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1953415"}}}}}