{"entities":{"Q2243791":{"pageid":2254534,"ns":120,"title":"Item:Q2243791","lastrevid":54141773,"modified":"2026-01-26T08:12:10Z","type":"item","id":"Q2243791","labels":{"en":{"language":"en","value":"On the chromatic numbers of random hypergraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7424645"}},"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":"Q2243791$242D73A1-36E9-4A60-A936-FB2BCAE24F1C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0f4f8238543de88685b9fb1c4580519af3508b33","datavalue":{"value":{"text":"On the chromatic numbers of random hypergraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2243791$22CF287F-0DEF-4A4A-8200-654E7D7228B6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4613909e2d28464c0f0f898e001c40c97ec195b3","datavalue":{"value":"1478.05134","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243791$3267D766-D71E-4ADE-9A64-855CD3831F8F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6deffa0ca96ae0050e2ab835fd29936f67f3101f","datavalue":{"value":"10.1134/S1064562420050312","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243791$69B8C2F8-2A7E-4600-B64D-FDF2EE6F38C1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"890681f7d7e4c45b7ac75928ebb8c67471d5c92f","datavalue":{"value":{"entity-type":"item","numeric-id":2088727,"id":"Q2088727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$22866457-BF43-4A69-8122-72841F9D1EB9","rank":"normal"},{"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":"Q2243791$285B60B9-57F7-4290-A171-6EC5CFD5875D","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":"Q2243791$35F68C87-B5EE-43E7-B145-08308F0DF878","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ff0991cde18ec724825a8f6357cb1656c5a612de","datavalue":{"value":{"time":"+2021-11-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2243791$2758672A-FC89-4EA8-A3EE-0D5D5B38A79F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"99d0fac89817f6f991b620eb4a9e132043b1b123","datavalue":{"value":"Let \\(H(n,k,p)\\) denote the random \\(k\\)-uniform hypergraph on the vertex set \\([n]=\\{1,2,\\ldots, n\\}\\) where each \\(k\\)-element subset is retained as a hyperedge with probability \\(p\\) independent of all other hyperedges. We are interested in the chromatic number \\(\\chi\\) of the hypergraph, namely the smallest number \\(s\\) such that there is a colouring of the vertices with \\(s\\) colours in such a way that no hyperedge has all its vertices the same colour. Generalising earlier results of \\textit{T. \u0141uczak} [Combinatorica 11, No. 3, 295--297 (1991; Zbl 0771.05091)] and subsequently others about the concentration of the chromatic number of 2-uniform random hypergraphs (i.e. random graphs), results were shown in [\\textit{M. Dyer} et al., J. Comb. Theory, Ser. B 113, 68--122 (2015; Zbl 1315.05051)] about the concentration of the chromatic number of \\(H(n,k,p)\\) when the expected number of edges \\(\\binom{n}{k}p\\) is a linear function of \\(n\\). The aim of the paper under review is to extend these results to dense cases where \\(\\binom{n}{k}p/n \\rightarrow \\infty\\) as \\(n\\rightarrow \\infty\\). This is achieved as a consequence of two theorems. The first states that if \\(c=c(n)=p\\binom{n}{k}/n\\) and \\(\\varepsilon>0\\), then if \\(c(n)\\rightarrow \\infty\\) as \\(n\\rightarrow\\infty\\) but \\(c(n)=o(n)\\), then for any function \\(r(n)\\) tending to infinity with \\(n\\), provided \\[c>r^{k-1}\\log(r)-\\log(r)/2+\\varepsilon,\\] it is true that, as \\(n\\rightarrow \\infty\\), we have \\[\\mathbb{P}(\\chi(H(n,k,p))>r)\\rightarrow 1.\\] The second, more substantial theorem goes in the opposite direction. Suppose now an integer \\(k\\geq 4\\) and \\(\\gamma \\in (0,1/8)\\) are fixed and that \\(c(n)\\) is defined as in the previous theorem. Suppose now that \\(c(n)\\) both tends to infinity with \\(n\\) (as before) but also now satisfies the more demanding upper bound \\(c(n)\\leq n^{(k-1)\\gamma /(2k+4)}\\), then there is an absolute constant \\(A\\) such that whenever \\(r(n)\\rightarrow\\infty\\) with \\[c < r^{k-1}\\log(r)-\\frac{\\log(r)}{2}-\\frac{r-1}{r} -A\\left(\\frac{k^{2}\\log(r)}{r^{k/3-1}}\\right)\\] it is true that, as \\(n\\rightarrow\\infty\\) \\[\\mathbb{P}(\\chi(H(n,k,p))\\leq r+1)\\rightarrow 1.\\]  A concentration result on at most three values (and in many intervals two values) follows from these two results.  Proofs involve results on an optimisation problem for doubly stochastic matrices to get a lower bound on the probability that \\(H(n,k,p)\\) has a proper \\(r\\)-colouring, then using martingale results to properly colour most of the hypergraph and a lemma to show that the remainder has at worst bounded chromatic number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243791$D49124C6-19A5-40D9-B7EF-6C78D484AA48","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243791$6C27BB61-A12C-4651-AC65-85D4EC6E70F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243791$1215AFE7-0271-4F78-BBDC-37CDCDFB5E46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243791$AFAEC42E-7203-48B8-9851-E2D9D524402C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a0857bc5d0ca473765a16d278912b5bbed3c523","datavalue":{"value":"7424645","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243791$65558A15-865B-44E2-9C2C-6DC54CC0BB40","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ad22613fc54c36c8248580a6c672588e112aab2","datavalue":{"value":"random hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243791$ADF105DD-4224-4992-9BED-C2011F1D2E0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243791$B79CF028-7447-4C29-A7AC-1FCA510E0CD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2b25a5a66786be30e1f9e76aa7171a8621315af0","datavalue":{"value":"second moment method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2243791$172AE522-D449-45BA-B107-80C65C3A460C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$B928B994-6ACC-4822-BCF4-FEDE5807018C","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":"Q2243791$ED831EE6-00EE-475C-9F1F-94289C3D28E0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff724a3146245444368d23d9020649822aa061f3","datavalue":{"value":{"entity-type":"item","numeric-id":1180430,"id":"Q1180430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$EF3CC133-1D80-420C-A601-597096956632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a341187ece0b34f8f08992d0752bab13f6c0dab5","datavalue":{"value":{"entity-type":"item","numeric-id":1280244,"id":"Q1280244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$92189CE7-E988-4CB6-BC99-4A6605469836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c904ec5fe1d4be7f07fb97f3e923f75bb422f427","datavalue":{"value":{"entity-type":"item","numeric-id":5920569,"id":"Q5920569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$982F77DF-C33C-4598-A5D6-2BDDD559BBC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e30dc7555b55c505c3d808b84cf3c5a0fe646d8a","datavalue":{"value":{"entity-type":"item","numeric-id":4560521,"id":"Q4560521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$498C25F8-F86A-49D7-A1BF-BD5F5E80EF88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d594fa8b07256e84d93e987e920d523adfe1adb","datavalue":{"value":{"entity-type":"item","numeric-id":396853,"id":"Q396853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$95C20720-596F-484D-B4FB-14905A8417CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abd62d13f252c0bf3b977c6009fe3bd435a969bf","datavalue":{"value":{"entity-type":"item","numeric-id":947725,"id":"Q947725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$8D2147FD-177F-46FC-BA54-631B9EA2480D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"522dc6ab6efe1c7b4551eefc5b738d9684080b27","datavalue":{"value":{"entity-type":"item","numeric-id":4705318,"id":"Q4705318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$7AAD1F45-1A81-4692-9D17-EF0FD403AFFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a3cd8b86bf12e7992fcaa94591ed158a5517559","datavalue":{"value":{"entity-type":"item","numeric-id":2347844,"id":"Q2347844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$EC165B21-598B-43B1-BB6F-F29BED7BA222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd5aeacabe60bec57946b5f73d8fc187a299bb53","datavalue":{"value":{"entity-type":"item","numeric-id":2411788,"id":"Q2411788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$4A7AE18D-8F00-4AA2-BC2A-035073D60807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2d70d8939fca3624a82cb97bf7c38b368870f67","datavalue":{"value":{"entity-type":"item","numeric-id":5229334,"id":"Q5229334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$5AF197AA-9FC9-43EE-975F-9CC569B15321","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a73019967f39ea1e69eb3f8a42f7aec00213ff1","datavalue":{"value":{"entity-type":"item","numeric-id":668022,"id":"Q668022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$45DFA2F4-0CA6-4C3C-AB22-0F44376707E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"268601179e1d3db7a31cf94b4d4c61a48ecd0316","datavalue":{"value":{"entity-type":"item","numeric-id":2422211,"id":"Q2422211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$906C3736-B8BC-4F28-B855-E19A0C9CD228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e9b2754fd88508c9858e4755aa7932c6d7d22b5","datavalue":{"value":{"entity-type":"item","numeric-id":1996843,"id":"Q1996843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$6EBFB063-7062-489F-9D3D-B540A1560E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72f86c8be67768ea7a0abf1352892206a5bd1544","datavalue":{"value":{"entity-type":"item","numeric-id":5380531,"id":"Q5380531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2243791$298BD059-D747-4CE9-B03E-35F167B79FB9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"208d172cf1b18ac45a1397c93ad19ddb78e29dcb","datavalue":{"value":"https://doi.org/10.1134/s1064562420050312","type":"string"},"datatype":"url"},"type":"statement","id":"Q2243791$EB9678AF-5F4D-4924-B4E6-747D0846E24D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"565c948252279e74ca0af968a60cc3719afcf6e8","datavalue":{"value":"W3118634717","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2243791$87A25418-BB2C-46E5-AB21-7545EC583049","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a96fb338bb5006a0d81b8efc69482035296a863","datavalue":{"value":{"entity-type":"item","numeric-id":5097170,"id":"Q5097170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6de41cc969fc9861b9336b9515cef59e6fcca38a","datavalue":{"value":{"amount":"+0.9160113334655762","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":"Q2243791$8F68119D-073F-4697-945D-2BB851605FEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0741e3513f4fa3a1af838ce34e33f9497aed1491","datavalue":{"value":{"entity-type":"item","numeric-id":2347844,"id":"Q2347844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"326a6ea55ce3f0106c1479bde573cd653d1ca10b","datavalue":{"value":{"amount":"+0.9006921648979187","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":"Q2243791$96718FC9-1786-4994-BD29-2AB55ACBC5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db42764ecbe7b6c9550554d350e279c8935a72f5","datavalue":{"value":{"entity-type":"item","numeric-id":4705318,"id":"Q4705318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53f94be22f00499d07ac9d496f36179797829d48","datavalue":{"value":{"amount":"+0.8895571827888489","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":"Q2243791$9EC27CD1-A3BB-4508-AC74-9F39B8A1EC80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f5ded99613c48ffa717986c17f0805bb0faed9d","datavalue":{"value":{"entity-type":"item","numeric-id":6112960,"id":"Q6112960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"646e0cf5fc2302e5a9bd37e78cb9faf781d0906f","datavalue":{"value":{"amount":"+0.889154314994812","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":"Q2243791$1811DD22-20D1-41CB-AADF-19EC560E8B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83e6bb72027b2697173be6caf2d547be71e9e984","datavalue":{"value":{"entity-type":"item","numeric-id":947725,"id":"Q947725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"894b0e8b1087440f8eea0e05c59bb9ad91366e02","datavalue":{"value":{"amount":"+0.8886808753013611","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":"Q2243791$13444ECB-C59C-4A02-8FF3-EF02EE26514F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2243791","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2243791"}}}}}