{"entities":{"Q736013":{"pageid":737862,"ns":120,"title":"Item:Q736013","lastrevid":63981000,"modified":"2026-04-11T16:50:37Z","type":"item","id":"Q736013","labels":{"en":{"language":"en","value":"Improvement of the lower bound in the Erd\u00f6s-Hajnal combinatorial problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5621455"}},"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":"Q736013$879177DB-EC67-4607-9C11-094FCA4B3DDD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02e8e114c4310b32d2afa8930683c3005d02272a","datavalue":{"value":{"text":"Improvement of the lower bound in the Erd\u00f6s-Hajnal combinatorial problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q736013$34AAC8D8-568F-404D-888C-319E8803E2D0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7e72ed49a44c5cd55bd67207fe9b232a7091d64a","datavalue":{"value":"1281.05099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q736013$06574E17-B2B8-415F-A70C-41175B5321E1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bc953efd0f879708a7aa3ddba3fdcf43c3aa4f0a","datavalue":{"value":"10.1134/S1064562409030132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q736013$B4E105A4-DDCD-4FD3-9749-BD4EBFC59114","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2bbc31fcaa3dcf49d82403ba391044fdfb104e43","datavalue":{"value":{"entity-type":"item","numeric-id":161529,"id":"Q161529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$6F10C644-1DAA-477F-B563-CF71A9EC4044","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"630340bfa00872c2b7b4672df4d7eac20447ca42","datavalue":{"value":{"time":"+2009-10-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q736013$04E5E5E6-F087-434B-A2B3-736E547117E1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f1501569f5616edb8212a9e8aac74ea7fc7cd96b","datavalue":{"value":"In 1961 Erd\u0151s and Hajnal posed the problem of finding the minimum possible number \\(m(n,r)\\) of edges in an \\(n\\)-uniform hypergraph with a chromatic number large than \\(r\\). Later, Erd\u0151s proved the first nontrivial bounds for \\(m(n, 2)\\), which are easy to extend to arbitrary \\(r\\).  Several asymptotic bounds for \\(m(n,r)\\) have been obtained over the last year. For arbitrary \\(n\\geq 2\\) and \\(r\\geq 2\\), the author has shown that  \\[ m(n,r)\\geq (\\sqrt 3-1)\\left({n}{\\ln n}\\right)^{1/2} r^{n-1}. \\]  A. Pluh\u00e1r has improved that result by showing for many values of \\(r\\)  \\[ m(n,r)\\geq \\frac 1{\\sqrt{4\\pi e}}n^{\\frac 12-\\frac 1{2r}}r^{n-1}. \\]   In this paper the following more accurate argument improving this result is stated.  Theorem 1. For all positive integers \\(n\\geq 2\\) and \\(r\\geq 2\\),  \\[ m(n,r)\\geq \\left(\\pi^{\\frac 1r}e^{\\frac 1{12(n-1)}}\\right) \\frac 1{e\\sqrt{2\\pi}}(n-1)^{\\frac 12-\\frac 1{2r}}r^{n+\\frac2r}. \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q736013$5D79B7CF-02E1-4FEA-828C-A9D5F344E2CE","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":"Q736013$0840F603-CED5-417D-8954-68426C6857A7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q736013$F3AD0B74-73A8-453F-B5AE-0F398D11FD81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q736013$411CE3A3-5761-4272-8DF0-EF5BFCB9C093","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"94487102bbd25d6d19530d90bfda66d12f0c8d0f","datavalue":{"value":"5621455","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q736013$F1A9BF4E-3662-4606-A73C-1931A410A620","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":"Q736013$CF6869BD-E904-4735-9ED6-B4F9D064424A","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":"Q736013$C1DA68C8-E95B-42A6-B69E-9FA10A424529","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"46306cc727aecdc2a9ade517dd21e5cfcd5359ba","datavalue":{"value":{"entity-type":"item","numeric-id":5599149,"id":"Q5599149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$844F4340-F1C5-4BB1-B2CE-C7F421DC6C84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f3e8aed192df9c937689b0ef93a97de2bb22035","datavalue":{"value":{"entity-type":"item","numeric-id":5599180,"id":"Q5599180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$97BC7E3D-C7F6-40C8-8C50-9FEC95173E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b649528e4e67d88f6c2dbcc161016f576d50a29e","datavalue":{"value":{"entity-type":"item","numeric-id":5518400,"id":"Q5518400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$1C4E4967-CE4E-4523-B3DD-AA39D00F75BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b5ae336e247aeae12c2b527317abcf7bb7270aa","datavalue":{"value":{"entity-type":"item","numeric-id":1241757,"id":"Q1241757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$96BEDE70-260C-47F7-BBC8-23B302C292E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d921e7a17f79bb3f1ecb84187c6aa57f99762bbc","datavalue":{"value":{"entity-type":"item","numeric-id":1137600,"id":"Q1137600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$DD8F664C-E87D-4BD6-8706-5C159CC8AA83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fb2ef0ba324755a03a243a2fb7dc2a282848b3b","datavalue":{"value":{"entity-type":"item","numeric-id":4943351,"id":"Q4943351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$293D9BC9-B006-433E-B1CE-98090C98EF6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"469e1f7ad7488bc26b21feef5b68f9b629e4620c","datavalue":{"value":{"entity-type":"item","numeric-id":1086588,"id":"Q1086588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$77A42E03-A596-4C97-A900-8C0E8C6D9972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b91e003c5b539d5d90b07c5b048d80bad370aa9","datavalue":{"value":{"entity-type":"item","numeric-id":4446874,"id":"Q4446874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q736013$DBE6AF8A-E573-48FC-BEBD-1DD02347E7A6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"04e45f81aeffe264a8463fbc274006fb7a7e7b18","datavalue":{"value":"https://doi.org/10.1134/s1064562409030132","type":"string"},"datatype":"url"},"type":"statement","id":"Q736013$FA7B6B12-DABD-4B97-AA58-28EF9F2BB7CC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a872fe83892282b5b0c5c4934f60786931dad9c4","datavalue":{"value":"W2018064035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q736013$F27F314B-2312-4A94-8671-A7FB838E9763","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e17c3b283b36d3305ae608cc63c811fed1487e2","datavalue":{"value":{"entity-type":"item","numeric-id":630232,"id":"Q630232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"272d8ad0206e27043741ec7f8cb85af108b48de4","datavalue":{"value":{"amount":"+0.9166749119758606","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":"Q736013$ED86DFDE-97B5-4B3E-9431-2A12957EA289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a9807bfe92d75e96a5cb9d636ead7b2515948b2","datavalue":{"value":{"entity-type":"item","numeric-id":658071,"id":"Q658071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65f6285a531f9208ba9787dc54fab85a5e262787","datavalue":{"value":{"amount":"+0.8948373794555664","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":"Q736013$9A007BB3-0DD2-4B1B-8257-110DCBA0E74E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3268798375b21875f0df93a9cbc06a00d40b1be","datavalue":{"value":{"entity-type":"item","numeric-id":2440004,"id":"Q2440004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3add46911cf609896d6a72df9ec15d4842edca4e","datavalue":{"value":{"amount":"+0.8809053897857666","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":"Q736013$90143401-DA62-49F8-8974-AF3EB02CED25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c6683b6c7f43f5ba9ee503f4173234b7913a711","datavalue":{"value":{"entity-type":"item","numeric-id":2027318,"id":"Q2027318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68171baaf3dac85bc897dbdb4b3d45823b2ade24","datavalue":{"value":{"amount":"+0.876703143119812","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":"Q736013$6E21D663-6437-4403-A7E4-98E0AAA46D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a8de26916a4140b1d060fa6d6e4244d31429914","datavalue":{"value":{"entity-type":"item","numeric-id":5890912,"id":"Q5890912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7fa40b3be6656c254d731fb660a4171f0a2ef16a","datavalue":{"value":{"amount":"+0.8717172741889954","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":"Q736013$20F0E636-3835-40DA-B614-60F23804B79E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Improvement of the lower bound in the Erd\u00f6s-Hajnal combinatorial problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Improvement_of_the_lower_bound_in_the_Erd%C3%B6s-Hajnal_combinatorial_problem"}}}}}