{"entities":{"Q1848150":{"pageid":1858892,"ns":120,"title":"Item:Q1848150","lastrevid":73040313,"modified":"2026-04-14T09:41:31Z","type":"item","id":"Q1848150","labels":{"en":{"language":"en","value":"Ramsey numbers for trees of small maximum degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1822338"}},"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":"Q1848150$D4C6C44D-E607-4CC3-B9E9-A6FA48214E6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"50d5e6e6d9bfc4b95322062bf88da62723ca31e5","datavalue":{"value":{"text":"Ramsey numbers for trees of small maximum degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1848150$F0C7FCCA-461D-4924-83E2-79438031AFB8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b48247e754cd415185347f943f9f8991fe25e5b0","datavalue":{"value":"0997.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1848150$A6885B6F-EF6D-47C8-AAA7-1E25F1A5CEDC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93a3904bbec182d67e761f38904a81bb2531b67d","datavalue":{"value":{"entity-type":"item","numeric-id":178704,"id":"Q178704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1848150$1C8B5362-959E-4E7E-A576-2ABD032040EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef9f22506a0bcbf1151d6523fea2bf6c3ee4e900","datavalue":{"value":{"entity-type":"item","numeric-id":353398,"id":"Q353398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1848150$215421CF-A66F-46DF-A6D7-100B26B0DC81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ba24e7a7c2ece164c1e96e84850f600a60c832d0","datavalue":{"value":{"entity-type":"item","numeric-id":426859,"id":"Q426859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1848150$1532914D-7BCE-4486-B843-A17B8817B25B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1848150$7C07F8C5-E009-45AD-85C5-DFA1A090468B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1619f533236da13b48e5500821f4ed21ad7e10ea","datavalue":{"value":{"time":"+2002-11-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1848150$818EDC08-A059-46CA-80D3-ED9ED1230FAC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"35648a515650f94506c1f18604666dc1755481ec","datavalue":{"value":"The authors find upper bounds on the Ramsey number of trees, that have close connections to Burr's conjecture. The Ramsey number \\(R(G,G)\\) of a graph \\(G\\) is the smallest integer \\(n\\), such that any graph on \\(n\\) vertices contains the graph \\(G\\) or its complement. For a tree \\(T\\), which is bipartite of course, let the sizes of its color classes be \\(t_1\\) and \\(t_2\\), such that \\(t_1 \\leq t_2\\). It is easy to see that \\(R(T,T) \\geq \\max \\{2t_1+t_2,2t_2\\}-1\\), and \\textit{S. A. Burr} [Lect. Notes Math. 406, 52--75 (1974; Zbl 0293.05122)] conjectured that the equality is false; see \\textit{J. W. Grossmann, F. Harary} and \\textit{M. Klawe} [Discrete Math. 28, 247--254 (1979; Zbl 0434.05052)]. Now the authors show an almost matching upper bound for some classes of trees. The main theorem is as follows. Let \\(\\eta > 0\\) be given. Then there exist \\(N=N(\\eta)\\) and \\(\\delta=\\delta(\\eta)\\) such that the following holds. For every \\(t_1 \\leq t_2 \\in Z\\) with \\(t_2 \\geq N\\), and every tree \\(T\\) with maximum degree \\(\\Delta(T) \\leq \\delta t_2\\) holds R\\((T,T) \\leq (1+\\eta) \\max \\{2t_1+t_2,2t_2\\}\\). The proof is based on Szemer\u00e9di's celebrated regularity lemma.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1848150$A3172207-D5F4-4255-BF44-3E73B8CEFC6A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1848150$152AE1E6-CED7-4AC5-A5B3-A36F4E22A923","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1848150$E2C45C8F-F125-4210-AD4E-12A07C0E5ED3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1848150$525FE639-58DA-40AC-A768-8660114C8063","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fe6a325cdf170962391afd1e2976d6dfc5e1dda8","datavalue":{"value":"1822338","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1848150$2119E732-6F0C-4267-8FB2-637E210F2954","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fda95859d903476568d5a87980a8b4bd69264e14","datavalue":{"value":"Ramsey numbers of trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1848150$01C22EAC-63A7-45B0-A628-82991C8DD5AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a6cf33575a7de49ac29ddc93f72a5401ad09876","datavalue":{"value":"Burr's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1848150$1A8B05A2-91E5-4538-80C4-B853B44030B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1a55ba5e5ae71e39cd2c561a862d90de0615e61","datavalue":{"value":"regularity lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1848150$F1614301-64CA-411A-9E77-F77A36F83F06","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":"Q1848150$59FD591F-C7DC-4F7C-99AF-15A0EEFCED75","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"669e454ea205722615a8f28e0d37230125a0846d","datavalue":{"value":"https://doi.org/10.1007/s004930200014","type":"string"},"datatype":"url"},"type":"statement","id":"Q1848150$FEA44608-69E8-4DFF-9272-3036166383D5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4990f90ae97dd4465b773e433176a49b5d853813","datavalue":{"value":"W2016667694","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1848150$F3E707E3-2182-4DAE-8974-0F4A9F1B8256","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"74581cdc7366100223227a6d233e079d6bd3f587","datavalue":{"value":"10.1007/S004930200014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1848150$7C02C956-9791-4364-AC8C-F9FBAD9AAED0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb7ae5038f1b37f91ec39545f166fa36b7918d6b","datavalue":{"value":{"entity-type":"item","numeric-id":5224758,"id":"Q5224758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f05e30bca38cdfecc343143918f1f8f61564a81","datavalue":{"value":{"amount":"+0.8645912408828735","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":"Q1848150$B6B38F9E-11FB-4529-9247-B6BFF3DD49DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"450b8565cfa921ee7a9e318c7d268cd18f187c96","datavalue":{"value":{"entity-type":"item","numeric-id":5916315,"id":"Q5916315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92e37fa7866cef5ed0906d47c0e965558d0aad64","datavalue":{"value":{"amount":"+0.8601214289665222","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":"Q1848150$8EE16C37-85D4-420A-9D59-6A5422F3BD99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad28606e051e9ddb80792cd53138de2ca7dc9c5a","datavalue":{"value":{"entity-type":"item","numeric-id":4034710,"id":"Q4034710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65ee20b09958f2dbb095675ea87a30937679001a","datavalue":{"value":{"amount":"+0.8574249744415283","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":"Q1848150$565174FE-C327-45AD-9ED5-5C5777460111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee4122a401505b5146342f872df47278c929dcbf","datavalue":{"value":{"entity-type":"item","numeric-id":3825106,"id":"Q3825106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"489646dc71102ae26966542030f5147896974f20","datavalue":{"value":{"amount":"+0.8572722673416138","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":"Q1848150$6C37DD0D-AE91-41FC-B563-823E3A009F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f21c801e88b9e29e1a26b54b68b2ae279fab84e8","datavalue":{"value":{"entity-type":"item","numeric-id":798674,"id":"Q798674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c34bc4279564e81064b966940dd8d312772fb93","datavalue":{"value":{"amount":"+0.8562526702880859","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":"Q1848150$8D7371FB-8792-4D45-827F-96F8B0E40F0E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Ramsey numbers for trees of small maximum degree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Ramsey_numbers_for_trees_of_small_maximum_degree"}}}}}