{"entities":{"Q2322506":{"pageid":2333249,"ns":120,"title":"Item:Q2322506","lastrevid":57851988,"modified":"2026-04-02T19:34:57Z","type":"item","id":"Q2322506","labels":{"en":{"language":"en","value":"The sub-exponential transition for the chromatic generalized Ramsey numbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7101333"}},"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":"Q2322506$30C9104F-F8CE-468B-B93B-3A33A31690B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e95ec7b42052d44430ca49b6e6493db776dcf0cc","datavalue":{"value":{"text":"The sub-exponential transition for the chromatic generalized Ramsey numbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2322506$9B513B80-F167-4DC7-8BBD-68978BFFA7C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3db28ed62e03ac267a1713229b3571b138e88da1","datavalue":{"value":"1438.05174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322506$98FE65CB-9CCB-4E08-A886-6D229CF419FA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6c7051c205c12629057479729f5c7f60a52cca20","datavalue":{"value":{"entity-type":"item","numeric-id":345087,"id":"Q345087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2322506$1F6D5E58-F053-43DF-9828-8FCF83C28A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"afdea04fa0ef67f7301d00800e5806c0c9e03fb2","datavalue":{"value":{"entity-type":"item","numeric-id":266612,"id":"Q266612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2322506$F08117FD-311A-46C1-83FC-FFD44E2EC7E6","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":"Q2322506$BC0075B3-8671-4D49-9FF0-F3024B49CA7A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"761866c458b823deb2476ea286c91321ef138424","datavalue":{"value":{"time":"+2019-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2322506$6124FFBF-BFF9-48EC-8B6E-B8AAEBCE351F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0edb643dc432c0fcddfd72653667894749bd3824","datavalue":{"value":"https://arxiv.org/abs/1507.04792","type":"string"},"datatype":"url"},"type":"statement","id":"Q2322506$7ACFF9C8-F286-479A-9756-2E20AED4C3A9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba137874a0c53c3e7ce19ada36285e62381f6a77","datavalue":{"value":"Define, for positive integers \\(p\\), \\(q\\), \\(r\\) with \\(p\\geq 3\\) and \\(2\\leq q\\leq \\binom{p}{2}\\) \\(F_{\\chi} (r,p,q)\\) to be the smallest integer \\(n\\) for which every edge-colouring of \\(K_{n}\\) with \\(r\\) colours contains a \\(p\\)-chromatic subgraph receiving at most \\(q-1\\) colours on its edges. One can check that this is well-defined, e.g. because \\(F_{\\chi}(r,p,q)\\) is bounded above by the so-called generalised Ramsey number \\(F(r,p,q)\\). Similarly say that an edge-colouring of a complete graph is \\((p,q)\\)-chromatic if the union of every \\(q-1\\) colour classes has chromatic number at most \\(p-1\\): then it is clear that \\(F_{\\chi}(r,p,q)\\) is the smallest \\(n\\) for which there does not exist a chromatic \\((p,q)\\)-colouring of \\(K_{n}\\).\\par If there is a chromatic \\((p,q)\\)-colouring of \\(K_{n}\\) with \\(r\\) colours, by partitioning the \\(r\\) colours into \\(\\lceil r/(q-1) \\rceil\\) sets of size at most \\(q-1\\), noting that each induces a \\(p-1\\) chromatic graph, and then using the product formula for chromatic numbers, we obtain the exponential upper bound \\(F_{\\chi}(r,p,q)\\leq (p-1)^{\\lceil r/(q-1) \\rceil}\\). Sometimes this crude-looking bound is tight: for example, one can show that \\(F_{\\chi}(r,2^{q}+1,q+1)=2^{r}+1\\) whenever \\(q\\) divides \\(r\\). \\textit{D. Conlon} et al. [Int. Math. Res. Not. 2015, No. 17, 8052--8084 (2015; Zbl 1342.05123)], in earlier work on this topic, asked if by contrast \\(F_{\\chi}(r,2^{q},q+1)=2^{o(r)}\\) for \\(q\\geq 2\\) and the main result of the paper under review is to prove this fact, which can be regarded as saying that there is a threshold for \\(F_{\\chi}(r,p,q)\\) to be exponential in \\(r\\). Indeed, they prove a somewhat more precise statement about the \\(2^{o(r)}\\) term: one can show that \\(F_{\\chi}(r,p,q)\\leq e^{Cr^{1-1/q}(\\log(r)^{q})}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2322506$0EFA861D-6EC6-4857-A121-11719D2A360D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322506$E24334DD-D90A-41F8-85F4-7E4C158B137E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322506$EE1BEC1F-DF5D-40EA-8741-E194F974DFE1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cff777451b10c1d6c06ae1b4c7af324666eb2c6f","datavalue":{"value":"7101333","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322506$CEDEB52D-C5C4-4658-9270-5DD56710008E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04a8bf7a0679a859c7e39e74e0d93deff95bdd86","datavalue":{"value":"generalised Ramsey number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2322506$9F7E6570-FF3E-4AA5-9C07-276B6E9F1609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc561adf76edf575722c093d125648be3eca42c9","datavalue":{"value":"chromatic \\((p,q)\\)-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2322506$8A51A085-AB6F-4D19-951B-9C9D9C9519DF","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":"Q2322506$7FE54D35-5375-4873-B12F-770E6A92779D","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":"Q2322506$B2867309-C5A9-40AE-B40F-8D1634F153A2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cd5845c07634cb2d2a3580e9b98ac0e4662afa22","datavalue":{"value":"W2243687886","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322506$609338A9-5EB4-4B42-84EE-4D80630CD1DE","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a354363cb6d585a0f24ac2159152f30842f51027","datavalue":{"value":"Q115606570","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322506$B5559352-6472-4C30-A6C6-0AF0A1A9BE65","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f829c8451c559707f11b7711e1b277e2a18d82cf","datavalue":{"value":"10.1007/S00493-017-3474-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2322506$3BC14B98-CF21-42B5-A65F-6587B759A25A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2f4093581807535cc26003ac7e9332c6302f458","datavalue":{"value":{"entity-type":"item","numeric-id":2940075,"id":"Q2940075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32b83f8b4b54f548c51c172af20d144cea0e4520","datavalue":{"value":{"amount":"+0.7755424380302429","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":"Q2322506$F6BAE847-D958-406F-9D8A-44121E0421AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3149415f464e1439e5e203a8e06c8380a6832429","datavalue":{"value":{"entity-type":"item","numeric-id":1584391,"id":"Q1584391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d76470a699d68c2e54cc5302295501a47735c52d","datavalue":{"value":{"amount":"+0.7572689056396484","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":"Q2322506$D4FA9D13-E2CA-494D-AC1D-81C46204B0F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28923a931927604fa2a3d6c251e50cbcb7ca73f6","datavalue":{"value":{"entity-type":"item","numeric-id":1579567,"id":"Q1579567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccc362fb8ccac5b1e4ecf05192ff54b65c803701","datavalue":{"value":{"amount":"+0.7572687268257141","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":"Q2322506$C007EFD5-8F01-457E-8417-E83111193D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ee6b317b772fbd3ea862363427d58bb9ba805e4","datavalue":{"value":{"entity-type":"item","numeric-id":5466073,"id":"Q5466073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65cee9293c623ae0254f099490dcfcef62e36c1e","datavalue":{"value":{"amount":"+0.7532299757003784","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":"Q2322506$CB842A5D-266D-4A83-A408-92E2BADE24A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a0b251f8a00582a351bce854af23fa913a96b82","datavalue":{"value":{"entity-type":"item","numeric-id":1280270,"id":"Q1280270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7afa146c958d64bdc8fd3eb0e2be802855e4b9bc","datavalue":{"value":{"amount":"+0.7511537671089172","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":"Q2322506$48C55EAF-E879-47AC-A3EF-AE9837290A14","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2322506","badges":[]}}}}}