{"entities":{"Q369596":{"pageid":371363,"ns":120,"title":"Item:Q369596","lastrevid":61309041,"modified":"2026-04-10T22:31:31Z","type":"item","id":"Q369596","labels":{"en":{"language":"en","value":"On the lower bound for the van der Waerden function"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6209097"}},"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":"Q369596$19B43D7E-422A-4595-8456-3BF973CD122A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e00a7e0e1bd6ec56c38153f79261f758fb49c625","datavalue":{"value":{"text":"On the lower bound for the van der Waerden function","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q369596$AE9BEBEA-7904-47D6-AFD8-CC71E3279980","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7eaccb61b6b5ec47126ea97472b1367321cde6ca","datavalue":{"value":"1317.11022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q369596$EFCEDD12-AA22-4F18-B913-231A15025429","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"15a36e69436f6c114697144510a14d2646ed97ca","datavalue":{"value":"10.1134/S0001434610050342","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q369596$641899F4-C9CA-4853-96B3-9B5356A60A96","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6288b0790219a402a99a3728c67fd2a775eb9a8b","datavalue":{"value":{"entity-type":"item","numeric-id":314148,"id":"Q314148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$2AC34BD9-69AC-483D-A113-77A279F32693","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"00de3e6b6cfff0576fe0e1d6bc63c05579d2cb43","datavalue":{"value":{"entity-type":"item","numeric-id":173953,"id":"Q173953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$96B6F06F-00F1-48FA-8A84-B23F97F98C5B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"882f57455209b6b7e7dd4f510eb3d4cb6732a678","datavalue":{"value":{"time":"+2013-09-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q369596$791F68EF-DB8C-4A12-A8D1-AF8AC38C6EAB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e0257973fbf903f8b7adc4a5ecbecb062a6ef8c5","datavalue":{"value":"The author's main result is a new asymptotic lower bound for the van der Waerden function \\(W(n,r)\\) [\\textit{L. van der Waerden}, Nieuw Arch. 15, 212--216 (1927; JFM 53.0073.12)]. For this he uses an improved version of the Erd\u0151s-Lov\u00e1sz theorem [Colloq. Math. Soc. J\u00e1nos Bolyai 10, 609--627 (1975; Zbl 0315.05117)] as follows.    Theorem. If the degree of each vertex of an \\(n\\)-uniform hypergraph \\(H\\) does not exceed  \\[ d = \\left(\\frac{\\sqrt 6-2}{4}\\right)\\frac {r^{n-1}}{\\sqrt {n\\ln n}} \\]  then \\(\\chi(H)\\leq r\\).   The proof of this theorem is based on the application of the local lemma as well as on the random coloring method for the vertices of the hypergraph in \\(r\\) colors; this proof was proposed by the author in [Math. Notes 85, No. 6, 902--905 (2009); translation from Mat. Zametki 85, No. 6, 951--954 (2009; Zbl 1191.05044)]. This theorem implies the following lower bound for the van der Waerden function \\(W(n, r)\\).    Theorem. For all \\(n\\geq 3\\), \\(r\\geq 2\\), the following inequality holds:  \\[ W(n, r)\\geq \\left(\\frac{\\sqrt 6-2}{4}\\right)\\frac {r^{n-1}}{\\sqrt {n\\ln n}}\\left(1-\\frac 1n\\right). \\]  This estimate improves the Erd\u0151s-Lov\u00e1sz estimate for \\(n\\geq 15\\). But, at the same time, this inequality is inferior asymptotically to \\textit{Z. Szab\u00f3}'s estimate [Random Struct. Algorithms 1, No. 3, 343--360 (1990; Zbl 0723.05115)] if \\(r=2\\). When \\(r\\) is exponentially large compared to \\(n\\) \\((n = o(\\ln r))\\), \\textit{L. Moser}'s estimate [Can. Math. Bull. 3, 23--25 (1960; Zbl 0100.27103)] remains the best.","type":"string"},"datatype":"string"},"type":"statement","id":"Q369596$A885658D-65DD-413F-82D5-085712A39E49","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3629f9b58c1c86062c61ff85f3263e580bc52bf7","datavalue":{"value":{"entity-type":"item","numeric-id":586708,"id":"Q586708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$C63FCB9A-072C-4B06-BA44-3EE65F55B9AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"59ff1173f55ceccb7042119df1cda673726c7815","datavalue":{"value":"11B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q369596$423FA622-56C0-408F-B88D-64A87EB8E92F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q369596$3C925036-A4F1-4366-B89A-8DECD638A353","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4bceb4852f142c7ae840ef027a3d11ea672a1bc4","datavalue":{"value":"11B75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q369596$183F034F-113A-4B81-A117-591CCD6ABB17","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"86abcc75680bae0a8c63ed29c1e7f8e263afa59c","datavalue":{"value":"6209097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q369596$C651B718-725F-4764-8AB2-927B0A280317","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa918ea1255c2cc0bd10589de07ef2a9cb8e1412","datavalue":{"value":"van der Waerden function","type":"string"},"datatype":"string"},"type":"statement","id":"Q369596$6C01C274-09FE-428A-81EE-575CDF4A2CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7e8a75011abf9e1b2949dafe6f3da14707ff5d8","datavalue":{"value":"arithmetic progression","type":"string"},"datatype":"string"},"type":"statement","id":"Q369596$69491926-C9D6-41D3-AAC2-A879FEB54432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"062e86198b28865499749e64228071dda218494f","datavalue":{"value":"coloring of a set","type":"string"},"datatype":"string"},"type":"statement","id":"Q369596$908121E8-9F96-4D37-980C-4E61C3615F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63a0b5bbdbffeb2f6d94dda6a7bccbc2173775aa","datavalue":{"value":"hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q369596$02B90499-DF63-4B59-8F4E-96E4F5D16116","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a123b3c17d3690dede94cabd3e6aa5f0de04a27","datavalue":{"value":"Erd\u0151s estimate","type":"string"},"datatype":"string"},"type":"statement","id":"Q369596$213AC338-808B-4A6C-9697-E9B4CA3A5C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddb7cb5638e00dd6c035901c1b2e4de1bf1cd9d3","datavalue":{"value":"Moser estimate","type":"string"},"datatype":"string"},"type":"statement","id":"Q369596$95F2D16D-9822-47BF-998E-9B63D2744EBD","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":"Q369596$3B0F32EC-5AE0-47A9-A2DE-A776A323294A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9e49449785c72925392b01526a9ab53fe19cc47","datavalue":{"value":{"entity-type":"item","numeric-id":5945509,"id":"Q5945509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$1B60F78B-DFF1-476E-89A9-A87120B36DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adf21ea69fe4ddc97ad38579c16428cebb928f87","datavalue":{"value":{"entity-type":"item","numeric-id":5814905,"id":"Q5814905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$47D92B12-BFD7-4DA8-9667-3EEEE63032EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7738ef16548db32013dbf9116da9deb20d4e8c2","datavalue":{"value":{"entity-type":"item","numeric-id":3282045,"id":"Q3282045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$E5BF3C0E-6775-45D3-90E3-6CB9F0D91E50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e679c1fc1ac9f410e28f56951c0380d80e6f7fd","datavalue":{"value":{"entity-type":"item","numeric-id":774715,"id":"Q774715"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$ED961D2E-BEB7-4FE3-BC71-7602ED692EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0d1cda34189e1ad50e802ad2a98183473a3f563","datavalue":{"value":{"entity-type":"item","numeric-id":5556460,"id":"Q5556460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$0ED699C6-CB31-4201-90FE-44F9CAFA250E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7deef63d53898ff7c759eca4a0eb235de82d6f4c","datavalue":{"value":{"entity-type":"item","numeric-id":3211360,"id":"Q3211360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q369596$9C37692B-CF70-47FF-83FA-D74B0228E370","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9a6fa3ae3bfe476c336885fe9131acbf02c764b3","datavalue":{"value":"https://doi.org/10.1134/s0001434610050342","type":"string"},"datatype":"url"},"type":"statement","id":"Q369596$4EFBC35A-575C-469E-B62F-E96D48224C48","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fc0498dc999f7ac9efe0e82837135e7fa18f4772","datavalue":{"value":"W2086173715","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q369596$17B88FAC-E69B-45D7-B54B-CB40A30926B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6999f766edf3c249c55d7eafc0baa983e01d582","datavalue":{"value":{"entity-type":"item","numeric-id":3447588,"id":"Q3447588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"196e6d7e1b6b33a6c59bf1b50e0a6bb0d85ef638","datavalue":{"value":{"amount":"+0.9537647","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$9B01C83E-9163-4692-B057-AB9D7551EF99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9faa3012015b84dd92ccdb88b84657e5b82437a7","datavalue":{"value":{"entity-type":"item","numeric-id":1296760,"id":"Q1296760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abacac7f25a92fc6b517afdd9792addf630ed7fe","datavalue":{"value":{"amount":"+0.9246572","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$14313AE5-E44B-42C9-8DA8-710DD8155E3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a7e78656c42633c21f3ad5e53540a04a0edb801","datavalue":{"value":{"entity-type":"item","numeric-id":1686261,"id":"Q1686261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b1a084279aac0e1eec797fe3532be7bf535517c7","datavalue":{"value":{"amount":"+0.9108292","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$ADCF0F27-8D6C-4FDD-B9A1-C355A37D6562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5f931e9a4c6297d6accdf333186c85b7eecd760","datavalue":{"value":{"entity-type":"item","numeric-id":5093808,"id":"Q5093808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b11b218cac95b01d7eefd404f58b6cc9ce20184","datavalue":{"value":{"amount":"+0.8950551","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$5E7CC0BB-4250-48E9-9466-F49B3024848C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a6f71b2ed28d0a8f0cdcf33ef2176b10ba7a9b5","datavalue":{"value":{"entity-type":"item","numeric-id":958741,"id":"Q958741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6000c1b6a09792012e7fa80e62900d556c74fb1d","datavalue":{"value":{"amount":"+0.89197433","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$F05AA5E8-8EBA-46E5-8ACF-4015EAD94330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc1332ac688b0bb59a69f6111b4c6a26a31d3b30","datavalue":{"value":{"entity-type":"item","numeric-id":870059,"id":"Q870059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1685d48adab68fbc15c25f5b02bb14b1581cdf24","datavalue":{"value":{"amount":"+0.889447","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$92497CDE-C38A-4AA8-A885-9E092C939480","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ced5811d7d1196788ac52552c2684d4857c1526e","datavalue":{"value":{"entity-type":"item","numeric-id":2267538,"id":"Q2267538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfef47ace4f1b047d9d49491b40e37d3a1ed7d29","datavalue":{"value":{"amount":"+0.8850069","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$F4C52AB6-EB15-4C23-864C-98403ABB722E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39cee0f432103df4903c688164a79331a3004fd8","datavalue":{"value":{"entity-type":"item","numeric-id":1117262,"id":"Q1117262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6594dc7f323ad9120cbb92f471c0000df0c03e93","datavalue":{"value":{"amount":"+0.88339996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$568CC28A-B11A-49EF-8FD1-37D0BBCAA23A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64c5d73e11f6cbc6f3dd2b9628acbb0d7e40a460","datavalue":{"value":{"entity-type":"item","numeric-id":540051,"id":"Q540051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"795eb440dbb52d1021d084a840f9c2bd83ffbc9a","datavalue":{"value":{"amount":"+0.87843823","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$FF88D72B-E7B6-4C1C-8316-F934C69C205B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c5b7c675e945ce98d4b567168d4590e4f422c6f","datavalue":{"value":{"entity-type":"item","numeric-id":1003615,"id":"Q1003615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18f3aa10d38d37ab269bcbc66e1ba0479006bfb2","datavalue":{"value":{"amount":"+0.8766045","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q369596$5A9D828A-2E30-418D-B2AE-153E7E16D5F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the lower bound for the van der Waerden function","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_lower_bound_for_the_van_der_Waerden_function"}}}}}