{"entities":{"Q705745":{"pageid":707594,"ns":120,"title":"Item:Q705745","lastrevid":48412234,"modified":"2026-01-04T15:49:00Z","type":"item","id":"Q705745","labels":{"en":{"language":"en","value":"An explicit construction for a Ramsey problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2133936"}},"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":"Q705745$AE9A9099-8DDE-47A6-89D5-4C1FDAE304D4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a28723f8b3af4fcdedd85e486ba003346cb74264","datavalue":{"value":{"text":"An explicit construction for a Ramsey problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q705745$A1C6D3EB-1D51-44BD-A570-37439F2D1D1D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ac5b97f90ff3c8f6aa7b4553d5be148c56b18b8c","datavalue":{"value":"1058.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705745$D17DB775-5EDA-4348-A6B6-491DF37D949D","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":"Q705745$5BCE1BA4-02C9-4BD8-9321-03B2C9AF4F38","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":"Q705745$B5A29293-AE0E-4A53-B16D-C0CF8522A0A8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e25cede1ef8d2406793b84eb9dd56b013bc7d13f","datavalue":{"value":{"time":"+2005-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q705745$FE26210E-8B6E-4E94-9BC9-C4D90349CF7E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"68ba77b5304bf49ee186b4dfaab977bcc7a19f14","datavalue":{"value":"Given graphs \\(G\\) and \\(H\\), an \\((H, q)\\)-coloring of \\(G\\) is a coloring of the edges of \\(G\\) such that every subgraph of \\(G\\) isomorphic to \\(H\\) receives at least \\(q\\) colors. The minimun munber of colors needed is \\(r(G, H, q)\\), for details see \\textit{M. Axenovich, Z. F\u00fcredi} and \\textit{D. Mubayi} [J. Comb. Theory, Ser. B 79, No. 1, 66--86 (2000; Zbl 1023.05101)]. For \\(G=K_n\\) and \\(H=K_p\\), \\(f(n, p, q)\\) is used instead of \\(r(G, H, q)\\). \\textit{P. Erd\u0151s} and \\textit{A. Gy\u00e1rf\u00e1s} [Combinatorica 17, No. 4, 459--467 (1997; Zbl 0910.05034)] investigated the growth rate of the function \\(f\\) when \\(p\\) is fixed. In particular, they showed that \\(d \\log n/\\log \\log n \\leq f(n, 4, 2) \\leq d' \\log n\\), and \\(f(n, 4, 4) =O(n^{2/3})\\) by a probabilistic argument. The main result of this paper gives an explicit (algebraic, with some modifications) coloring that proves \\(f(n, 4, 4) < n^{1/2}e^{c \\sqrt{\\log n}}\\). From Tur\u00e1n's celebrated theorem follows easily that \\(\\Omega(\\sqrt{n})= f(n, 4, 4)\\), and the author conjectures that indeed, \\(f(n, 4, 4)= \\Theta (\\sqrt{n})\\).   The proof nicely blends some simple computation over finite fields with graph theoretic ideas.","type":"string"},"datatype":"string"},"type":"statement","id":"Q705745$89EEC7D8-B44B-4EF9-AF2D-CB0D3EBF7E1F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"73456c3353ea197c90c73d5f0daaf3b9d502d311","datavalue":{"value":{"entity-type":"item","numeric-id":235726,"id":"Q235726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q705745$1FE9EF44-FA04-4B4B-B24B-700D464A28AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705745$94D487F6-C156-4E43-A276-652FC9FC9031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705745$6BEC5C68-A48D-4103-B900-941E279AAB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705745$F6CAE4D8-6D8C-4F29-B488-326933FA13EE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"225f526db34c7f2cf96f6e3afd7800a76418a974","datavalue":{"value":"2133936","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705745$9DA4D377-1592-45BC-92C2-328ED94877FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e89a6e5dcd9d75930dab0804d65f5e9780bef8c8","datavalue":{"value":"Ramsey problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q705745$99A24CBB-0D9B-4F3F-915B-8A234CB60BA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf10fbc0821653f5bccf71e9d370791acbafb53c","datavalue":{"value":"explicit constructions","type":"string"},"datatype":"string"},"type":"statement","id":"Q705745$D5FCDD80-C4EC-48E7-A8D9-17FF6F933471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a35b4807544faa4b9101bc872823f5673f03c7e","datavalue":{"value":"algebraic method","type":"string"},"datatype":"string"},"type":"statement","id":"Q705745$10342257-D452-4807-8371-975C1F769859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q705745$B8CC4E74-4A61-4A5C-9BC9-2B8AC32545B3","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":"Q705745$B5A3CCE5-BFD9-4683-BA81-0BCF3252728C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bdcfa21a4bcf830f9b5fb7f2deae5c2164d95fb8","datavalue":{"value":"https://doi.org/10.1007/s00493-004-0019-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q705745$D075933F-1BB8-48DC-B4C5-685B8CF3F463","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5d9d5c327333cf40150327a6d6a9377258c9446f","datavalue":{"value":"W2072455759","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705745$3F5E8D18-7F3E-429E-B597-A6FE4062FE90","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2cba6fd12ad65b20555d41c41b307aebfdaea40a","datavalue":{"value":"10.1007/S00493-004-0019-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q705745$6D6685B3-F756-451C-8F4B-0BE8CD699641","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78f796994f48b9e4238806e9f53ce939d4b1e67e","datavalue":{"value":{"entity-type":"item","numeric-id":1280308,"id":"Q1280308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eae55fd8ed2e84c13580cb6dd12c37586dbaa544","datavalue":{"value":{"amount":"+0.8290903568267822","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":"Q705745$B7329285-B22D-4A7D-B9A0-0D8E0090F7C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74b8b0bad5d2e77b5028b9f275c1c7e09fe85947","datavalue":{"value":{"entity-type":"item","numeric-id":1850469,"id":"Q1850469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7b8c5f456dd4a70748596949edd689820009e44","datavalue":{"value":{"amount":"+0.8290899991989136","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":"Q705745$C4022D6C-922D-4710-BE5D-08A88E5549D3","rank":"normal"},{"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":"836f7f50d74a8199bb4d4a8dbc1e14338b08fbe8","datavalue":{"value":{"amount":"+0.8275374174118042","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":"Q705745$A830023A-0BB5-4AFC-BA54-DCCAEA57434A","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":"c1704e17733ea1d2512fe96aef06c60d8ffa2aa1","datavalue":{"value":{"amount":"+0.8274837732315063","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":"Q705745$8AE031E4-B2D5-49B6-8E6B-A6996C23CD27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc4da945ec3f5abf0d02776a63b9e4e662ce745d","datavalue":{"value":{"entity-type":"item","numeric-id":4075490,"id":"Q4075490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d732ec614eac3f56a314e05f5b60bcc67723ce82","datavalue":{"value":{"amount":"+0.8268507122993469","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":"Q705745$6BEAD1F7-E5EE-452B-9C0A-4E5FD645D314","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:705745","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:705745"}}}}}