{"entities":{"Q2178253":{"pageid":2188996,"ns":120,"title":"Item:Q2178253","lastrevid":57762930,"modified":"2026-04-02T10:29:07Z","type":"item","id":"Q2178253","labels":{"en":{"language":"en","value":"The Erd\u0151s-Hajnal hypergraph Ramsey problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7198107"}},"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":"Q2178253$7414F268-2039-4D66-9CC7-A1BC6F4267CC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef9f72067af8315b45453c1d7b02f5cdd670905e","datavalue":{"value":{"text":"The Erd\u0151s-Hajnal hypergraph Ramsey problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2178253$FB8719B9-C080-4945-8670-8DD4A85259B4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"74934ffb131ca1b12a1f15af7435521d94e6ee68","datavalue":{"value":"1439.05218","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2178253$569BD574-4315-4C19-A02D-83A61DE38208","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d94ac1dc94f523c037890f1e550e9dc49423018f","datavalue":{"value":"10.4171/JEMS/944","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2178253$90FA0187-4927-42FD-9A72-2171245DF951","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b2dc7fb86714f67c87c73e07c13ee1e0d7b9d71","datavalue":{"value":{"entity-type":"item","numeric-id":168649,"id":"Q168649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$CEB63237-EA8B-441E-8D04-1152908810A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9bb32cb105f0d567e8e0240a89680b942eebc8c0","datavalue":{"value":{"entity-type":"item","numeric-id":427058,"id":"Q427058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$6FD61FBE-DA92-4021-B3CD-876F1A9B2063","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"26780b1287f0091cd789fa2d15704011bf65df86","datavalue":{"value":{"entity-type":"item","numeric-id":171275,"id":"Q171275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$7956D79A-00DD-4D0D-B6A5-C57AF01983E7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"45b0b521676d950468ecb32ef53d7d65df0b91dd","datavalue":{"value":{"time":"+2020-05-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":"Q2178253$D2D2016B-84FE-42A1-BEB4-571C1EC4F019","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"55b816241de1db2b66b6527cce2058178204f9d5","datavalue":{"value":"https://arxiv.org/abs/1602.08716","type":"string"},"datatype":"url"},"type":"statement","id":"Q2178253$8DE81F4A-C9DC-43C8-976A-B34D012F3A54","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"712865df7040deb910339416598d15a8e20bbde7","datavalue":{"value":"Summary: Given integers \\(2\\leq t \\leq k+1 \\leq n\\), let \\(g_k(t,n)\\) be the minimum \\(N\\) such that every red/blue coloring of the \\(k\\)-subsets of \\(\\{1, \\dots, N\\}\\) yields either a \\((k+1)\\)-set containing \\(t\\) red \\(k\\)-subsets, or an \\(n\\)-set with all of its \\(k\\)-subsets blue. \\textit{P. Erd\u0151s} and \\textit{A. Hajnal} [``On  Ramsey  like  theorems,  problems  and  results'', in:  Combinatorics. Proceedings of the Conference on Combinatorial Mathematics held at the Mathematical Institute, Oxford, 3--7 July, 1972. Southend-on-Sea: The Institute of Mathematics and its Applications. 123--140  (1972), \\url{https://users.renyi.hu/~p_erdos/1972-10.pdf}] proved that for fixed \\(2\\leq t \\leq k\\), there are positive constants \\(c_1\\) and \\(c_2\\) such that \\[2^{c_1 n} < g_k(t, n) < \\operatorname{twr}_{t-1} (n^{c_2}),\\] where \\(\\operatorname{twr}_{t-1}\\) is a tower of 2's of height \\(t-2\\). They conjectured that the tower growth rate in the upper bound is correct. Despite decades of work on closely related and special cases of this problem by many researchers, there have been no improvements of the lower bound for \\(2 < t < k\\). Here we settle the Erd\u0151s-Hajnal conjecture in almost all cases in a strong form, by determining the correct tower growth rate, and in half of the cases we also determine the correct power of \\(n\\) within the tower. Specifically, we prove that if \\(2 < t < k - 1\\) and \\(k - t\\) is even, then \\[g_k(t, n) = \\operatorname{twr}_{t-1} ( n^{k-t+1 + o(1)} ).\\] Similar results are proved for \\(k - t\\) odd.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2178253$C3A6626E-B061-47A3-A4BE-4CC658FF5857","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2178253$AA35F56F-F4C5-42E9-8968-0FAD784DA2C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2178253$889BCED1-8326-4753-941D-25CB3F7D4F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2178253$85756451-F34D-43EB-831D-BD7AFBB7CD67","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"374f2e3abc328dc8d12553961c9ea19997be5d67","datavalue":{"value":"7198107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2178253$D4BC100A-32A7-4851-BCA7-41AEA495C2EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07aa18c99cb6d821f2600528e5efd1fc1e91ce67","datavalue":{"value":"hypergraph Ramsey numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2178253$0228AECB-0C03-4DCB-A15D-A8F6DF3C6FD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9e9d34cb607eaf90cef26fb5dde457e582f84801","datavalue":{"value":"stepping-up lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q2178253$BE531D6A-FD65-4DBD-A36F-A142A4186B8C","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":"Q2178253$511F6B3B-4BE0-4DCB-BC1E-5EF2198CE9B1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52c7540760fe9ef3923a27be3c87c2aba62dfedc","datavalue":{"value":{"entity-type":"item","numeric-id":1149967,"id":"Q1149967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$7467F160-1F29-4E11-A250-C2F3A88AF18C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e8170c53c62de61c24b5892581374aeba4e8b1b","datavalue":{"value":{"entity-type":"item","numeric-id":396781,"id":"Q396781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$477EE7BA-AE38-4A26-B8BB-B85898B555A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e23a0e274687e86a5e75a720ea8cad4a219781a4","datavalue":{"value":{"entity-type":"item","numeric-id":1023043,"id":"Q1023043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$2FA22E8D-19C7-41CF-A008-2E67B2FAB19C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b727335b4f2906d42e54f4781565f646223f43fb","datavalue":{"value":{"entity-type":"item","numeric-id":982189,"id":"Q982189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$FB3932CC-AA29-4B67-8940-6A912D8C0EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d4b8048f6210c471ad38d88b52197aa2bd692d2","datavalue":{"value":{"entity-type":"item","numeric-id":4337503,"id":"Q4337503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$E54F5C51-1E6E-41A4-83C1-927D5EAEA24A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb49cccf623c06156cd7c1a0fddeb40fe276f892","datavalue":{"value":{"entity-type":"item","numeric-id":3584347,"id":"Q3584347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$673F0734-BD21-4536-8738-25A964C18B0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9523d6131311d1dd22c8165fd4c6de746a357f20","datavalue":{"value":{"entity-type":"item","numeric-id":385142,"id":"Q385142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$F63316AD-8642-4DB9-8099-8B54EF0EEE12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf29660bb43bc9f516b27c8877ebb67cb388d08f","datavalue":{"value":{"entity-type":"item","numeric-id":1343782,"id":"Q1343782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$237F6584-3CB5-4738-B6F7-07E5E16D35A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072f25a28315de2b4ed49bbecac8c6477180401b","datavalue":{"value":{"entity-type":"item","numeric-id":2437401,"id":"Q2437401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$C6F15E40-B4C7-436B-B7AA-8FB3D2C8A684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696e943427d95202a9a3e2ee416ff57e3a79afa7","datavalue":{"value":{"entity-type":"item","numeric-id":3143440,"id":"Q3143440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$D51030B0-CA50-4A33-8FB6-9E2BB77BD4E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fca512bd62ef81317baaf07336a09e35ab66e1e","datavalue":{"value":{"entity-type":"item","numeric-id":5789964,"id":"Q5789964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$09EA67FB-E0BA-41A0-BCA5-CC591975D992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d7993358cb712a93851b0bd102eb877f5714a26","datavalue":{"value":{"entity-type":"item","numeric-id":5541367,"id":"Q5541367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$BC0AD239-7957-4FB3-95FC-45CA3D501040","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":"Q2178253$A275A178-734E-488B-8E6F-C8AACD09B01F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3647fe00e3b83141b14436c1949063f538c83988","datavalue":{"value":{"entity-type":"item","numeric-id":3997075,"id":"Q3997075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$B81CF601-D7DA-4AE8-A62D-1FD3CDC0B069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ae086da94f3e49304312f06ac259fd4cfb7c8c9","datavalue":{"value":{"entity-type":"item","numeric-id":965243,"id":"Q965243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$27665FC0-D45F-4690-8516-359A98FCCCE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"262ef5c6e54a03847e2c095e39995c68d83f54d7","datavalue":{"value":{"entity-type":"item","numeric-id":5265346,"id":"Q5265346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$9E6F273A-494F-451C-84F7-F991022DE87A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebcf91f3bbc00fcf3bc033898454244f4129dec1","datavalue":{"value":{"entity-type":"item","numeric-id":5496786,"id":"Q5496786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$4BD43D40-11D6-458E-8F13-C60811BD8B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"526a4a79aca84f740f9b4d8497d4a552e37041b8","datavalue":{"value":{"entity-type":"item","numeric-id":393743,"id":"Q393743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$A8590DE5-3139-4E62-B983-12723F1B17C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8d31b5cb5b5caabc20cf8e55cfa3af8837672f2","datavalue":{"value":{"entity-type":"item","numeric-id":2251909,"id":"Q2251909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$8C36F416-32E6-4CB4-8DC4-87022968D9C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32f4abf1b719f757f648877270e84ee6dc40290d","datavalue":{"value":{"entity-type":"item","numeric-id":890582,"id":"Q890582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$EEFE1493-31B3-48DF-A42D-9BDCA73870A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5b830d63444297cee9f20338c8e42329c254890","datavalue":{"value":{"entity-type":"item","numeric-id":4638122,"id":"Q4638122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$D4FC9CAD-DB61-4F20-A2E2-7865B1D1131E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48fa4437ef11568231dbbc73b91cd8b1fde0cbd1","datavalue":{"value":{"entity-type":"item","numeric-id":4637550,"id":"Q4637550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2178253$FC5A8487-16A9-45EF-91DE-3B59C0B323A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97fbdbdc7de9bfa1935bf106f54f15c0c9c1eada","datavalue":{"value":{"entity-type":"item","numeric-id":5086917,"id":"Q5086917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84d868e8ecf0ff5fe7652f0f002d0b6caa0128b9","datavalue":{"value":{"amount":"+0.8649619221687317","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":"Q2178253$18BCA64E-AFFB-4D4F-9416-12073122F74B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4253742f74ebfcc7f728d397c48170a63674a665","datavalue":{"value":{"entity-type":"item","numeric-id":2396897,"id":"Q2396897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c24457b5c1b7752fdb3ea137cfb560eb5dbaec4","datavalue":{"value":{"amount":"+0.8533351421356201","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":"Q2178253$11E5F14B-5486-4EEA-A7A4-6AF50C65EFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"decaabe4dae445a77febda8bc0119edde3f46a83","datavalue":{"value":{"entity-type":"item","numeric-id":4637550,"id":"Q4637550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c631cf552c1abfae9ff5e34736b9678685078852","datavalue":{"value":{"amount":"+0.8273852467536926","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":"Q2178253$C44A3E59-DF46-4880-AAE1-781712F4AD89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4cc3dd787a100c64a2c568b1575ef3e323f70135","datavalue":{"value":{"entity-type":"item","numeric-id":518192,"id":"Q518192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8bbb3d9b7b123343d49c936b91d654d2726d475","datavalue":{"value":{"amount":"+0.8202154636383057","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":"Q2178253$9E0BBD26-3F7A-429D-98F8-EAB5E4F49B96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f4f437353ad68fcb2c8c15bc03e469f77b43408","datavalue":{"value":{"entity-type":"item","numeric-id":3584347,"id":"Q3584347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a377cbb40142696dfd8e6b4cee1e2fc4533b60e2","datavalue":{"value":{"amount":"+0.8182674646377563","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":"Q2178253$C52C2936-AC7B-425D-A970-281AC1D96137","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2178253","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2178253"}}}}}