{"entities":{"Q653983":{"pageid":655832,"ns":120,"title":"Item:Q653983","lastrevid":51389534,"modified":"2026-01-18T01:17:26Z","type":"item","id":"Q653983","labels":{"en":{"language":"en","value":"On \\(K_s\\)-free subgraphs in \\(K_{s+k}\\)-free graphs and vertex Folkman numbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5990941"}},"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":"Q653983$0E91A6B1-5F4B-4F5A-A71F-46E16CDFAD8B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"851ad08dc55ad9c536f5b3e45a2412d25f783b33","datavalue":{"value":{"text":"On \\(K_s\\)-free subgraphs in \\(K_{s+k}\\)-free graphs and vertex Folkman numbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q653983$BBA2B744-235C-408F-B93A-BE4283FA4F99","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"989c0517d4317fefdce993ba0b0fb533685ec065","datavalue":{"value":"1249.05197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653983$410E8158-F189-40D8-B33A-68C15C5C2C48","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b99f828f7c125d1e32c44078b73dd8c4e78184b","datavalue":{"value":{"entity-type":"item","numeric-id":267203,"id":"Q267203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$6C8AF4A2-DAD6-48DB-9FF2-A0B3730D9629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$EEC82ABB-A5E1-46D1-A267-13F872F783E6","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":"Q653983$468E31EB-D533-43C5-B3C6-484D4373F9C0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e9a9ebdc8bdc44c407c473bf89fbe244ce057f32","datavalue":{"value":{"time":"+2011-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q653983$8889CF6E-DDE6-4237-BC7C-D35EFF0268D7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"df005fe2f99564e0e6d474c69c819eec642082a7","datavalue":{"value":"For fixed integers \\(2 \\leq s < t\\), define  \\[  f_{s,t}(n) = \\min\\{\\max\\{| S| ~ : ~ S\\subseteq V(H) ~ \\text{and} ~ \\langle S\\rangle_H ~ \\text{contains no} ~ K_s\\}\\}  \\]  where the min is taken over all \\(K_t\\)-free graphs \\(H\\) of order \\(n\\). Bounds on this Ramsey function are investigated, and the following surprising result is proved. For every integer \\(s \\geq 2\\), there is a positive constant \\(c = c(s)\\) so that for every integer \\(n\\),  \\[  f_{s,s+1}(n) \\leq cn^{2/3}.  \\]  Previously, it was suggested that for any given \\(\\epsilon > 0\\), \\(f_{s,s+1}(n) \\geq n^{1 - \\epsilon}\\). The following more general result along with a corollary was proved. Given any \\(\\epsilon > 0\\) and integer \\(k \\geq 2\\), there is a constant \\(s_0 = s_0(\\epsilon, k)\\) such that for \\(s \\geq s_0\\),  \\[  c_1n^{1/(1 + (\\frac{s}{s-1})^{k-1})} \\leq f_{s, s+k}(n) \\leq c_2n^{\\frac{k+1}{2k+1} + \\epsilon},  \\]  where \\(c_1\\) and \\(c_2\\) are positive constants depending only on \\(s\\). An immediate corollary of this for \\(k\\) sufficiently large is the following:  \\[  c_1n^{\\frac12 - \\epsilon} \\leq f_{s, s+k}(n) \\leq c_2n^{\\frac12 + \\epsilon},  \\]  where \\(c_1\\) and \\(c_2\\) are constants depending on \\(k\\) and \\(s\\). These results are applied to the vertex Folkman number \\(F(r,s,t)\\) for \\(s < t\\), which is the smallest integer \\(n\\) such that there exists a \\(K_t\\)-free graph \\(G\\) of order \\(n\\) such that every \\(r\\)-coloring of the vertices of \\(G\\) yields a monochromatic \\(K_s\\). Each of the results on the function \\(f_{s, t}(n)\\) yields a corresponding result on the vertex Folkman number. For example, in the case of the corollary there is the following result: For any \\(\\epsilon > 0\\) and sufficiently large \\(s\\), \\(t\\), \\(k\\), \\(c_1\\) and \\(c_2\\),  \\[  c_1r^{2 - \\epsilon} \\leq F(r, s, s + k) \\leq c_1r^{2 + \\epsilon}.  \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q653983$5DDBF9B3-6D05-455D-8687-72FC1F6725A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653983$739B4337-527E-42E9-ABFF-B73B05A47526","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653983$1356DFF1-3171-4959-92FB-6D5C75412909","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c1a40f0ccccc88b02953c3acc26d8bd5b1e8a634","datavalue":{"value":"5990941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653983$5C3A77FF-1E48-4EBC-AE47-DB94A575AA7B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b281cb6c91ccf6233b3aa7a0e31f1c8e2bcc910","datavalue":{"value":"\\(K_s\\)-free subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q653983$E106E43E-51E1-48E1-8B05-67A05302DF60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39759b57322fc413fed9408d8397a22b347c9946","datavalue":{"value":"vertex Folkman numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q653983$89B1733B-F008-4757-A4F7-C1244191821B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed5607bcf9ea8dfa99691a6445086cfefb466c73","datavalue":{"value":"Ramsey numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q653983$A198DF63-3379-4EF3-A6E1-BEAAB42740B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8353bd93debca5b08640180cd9508d488fddd60","datavalue":{"value":"forbidden","type":"string"},"datatype":"string"},"type":"statement","id":"Q653983$C10CF487-D3C9-4FFD-9807-E4831889EA77","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":"Q653983$2FEBE7AC-1A29-45A0-91B6-8057FF08133E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"660e91ac161b517fc2ee09c00ab5db363aa51594","datavalue":{"value":"https://doi.org/10.1007/s00493-011-2626-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q653983$9968723A-E959-4604-AE2C-7C7B995C3B97","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"14231106163502b5899de57b9f26566c03c36b9a","datavalue":{"value":"W1984962604","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653983$DCA0CB55-4472-4E37-AC3F-AE478EC7F57F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"07d4b2c5cc997aa77410b9a8e412494917162a12","datavalue":{"value":{"entity-type":"item","numeric-id":1376057,"id":"Q1376057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$2753BB38-4E3D-48E3-BE94-03844B2A111B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"686765cc81ac94c4fe1e7edd588ed7673991a12b","datavalue":{"value":{"entity-type":"item","numeric-id":1174161,"id":"Q1174161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$0A96656E-D9AF-494A-B9E7-31FCE2774173","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"468e553c89e544cdc2e82b3d69176c982b8c6030","datavalue":{"value":{"entity-type":"item","numeric-id":1262327,"id":"Q1262327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$BD7DA584-1505-467F-BDBF-FA16B2A15EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68cca7acf9b49a351a68202ad9f67b0707138d0a","datavalue":{"value":{"entity-type":"item","numeric-id":965241,"id":"Q965241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$907E775B-8E09-4B41-96B8-13BF596BDACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61f620c50d11a1410dfdf3b13cc388e378dee800","datavalue":{"value":{"entity-type":"item","numeric-id":5458552,"id":"Q5458552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$57BFC535-6D29-45C2-A764-023DFF9D2186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3071d26047601ef4d6c18a18938b5be4e28295a5","datavalue":{"value":{"entity-type":"item","numeric-id":4019375,"id":"Q4019375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$C5120D57-E6C7-413D-8FC2-D75A6BE88078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20d333939803b46e00efa852d19924de6b797de0","datavalue":{"value":{"entity-type":"item","numeric-id":5589878,"id":"Q5589878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$302894F9-8098-43AC-9C15-7F60DBEA1E26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7aafb6f1967ec28f6cf07b039bb967384e63e04b","datavalue":{"value":{"entity-type":"item","numeric-id":5589119,"id":"Q5589119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$43FB0300-735A-4B7A-AC25-DD8427FB371F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d27dacc5c86087ff2495c99b8279b01d00250f","datavalue":{"value":{"entity-type":"item","numeric-id":2716030,"id":"Q2716030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$2FF746A0-954A-45C2-84E1-BBD2761C1083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b7fa7d4ef6fbd2c126520caca9e6739a5870ea4","datavalue":{"value":{"entity-type":"item","numeric-id":815208,"id":"Q815208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$05BA9FD2-1B0E-41D1-8F25-0FF5FE8CC6FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"870f3df5a240a464c4794a8429c175786ef682f4","datavalue":{"value":{"entity-type":"item","numeric-id":4847400,"id":"Q4847400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$DC6914D1-1356-4800-969C-B992AE71FF44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b57791728cfec3dbd2a1eeb332453fc42d10c8a","datavalue":{"value":{"entity-type":"item","numeric-id":4314152,"id":"Q4314152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$02E8FFAD-C0D4-4C2A-B5BD-912DE901B26D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de054ab62a4e7e615c2f535d34aa0c9257423f89","datavalue":{"value":{"entity-type":"item","numeric-id":5959105,"id":"Q5959105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$BB6CA203-333D-4574-B915-1D99C4A81292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"434297e1ae28f18e93d282fb158cf0ac6ce902fa","datavalue":{"value":{"entity-type":"item","numeric-id":1408894,"id":"Q1408894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$70BB50BE-ABB3-4B9B-A8DA-FA2627065DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"218de7e848ea7bb4b60a4eadc564810de2cedc88","datavalue":{"value":{"entity-type":"item","numeric-id":1227013,"id":"Q1227013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$0A70436B-B0A8-44D7-A712-F61376D9AD39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fdde022eb6a68b3b980aebc43995289373715f1","datavalue":{"value":{"entity-type":"item","numeric-id":4680408,"id":"Q4680408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$A7CA7224-C37D-4B34-9E52-F1BD84799D0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d126f028b5c32c5c7f3cfda26ed81347b0c4707","datavalue":{"value":{"entity-type":"item","numeric-id":2568501,"id":"Q2568501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$CE0C7CBF-FAF6-4E67-9B2B-116167F076CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f7793310e41aa6ce3a72c0f4201144ab529a18f","datavalue":{"value":{"entity-type":"item","numeric-id":4764145,"id":"Q4764145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q653983$11A08A19-BA53-4036-8AEF-627389CADD41","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"28c8313e9de21c35eb4b3257212d956a8939ca7c","datavalue":{"value":"10.1007/S00493-011-2626-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q653983$D5683A67-40CC-4F99-95ED-75D17FB224A2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02e35d8d94c34d7f70cd9c946ce3e42d44e4ea2c","datavalue":{"value":{"entity-type":"item","numeric-id":965241,"id":"Q965241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ca36699cde1e3ebc6991fb9db5a9c3155c28ef7","datavalue":{"value":{"amount":"+0.849884033203125","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":"Q653983$6995FED1-76A3-4006-B843-8D993DA5D7C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"836923992a85e09e6d4ab9f255561cd2529efa03","datavalue":{"value":{"entity-type":"item","numeric-id":5133216,"id":"Q5133216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f03259f0365803fc3000fe4b591b8f86aa1b467d","datavalue":{"value":{"amount":"+0.841084897518158","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":"Q653983$58B605A1-2B4B-41FC-819E-0B85F6FEA6DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f102d8f79df26c0a4e2442287e73362dfb2d726a","datavalue":{"value":{"entity-type":"item","numeric-id":2195230,"id":"Q2195230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40bfb14c90adca7fcc26fff9e876e3bf77336b32","datavalue":{"value":{"amount":"+0.8366940021514893","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":"Q653983$1B47280B-50AE-41CD-A084-9D042FE79642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74e82d9c6684bcf2ee4e4c5c408d510b4f57729d","datavalue":{"value":{"entity-type":"item","numeric-id":5458552,"id":"Q5458552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f062e26ff7e2e0e1d89d53ab75be1b77e1f9ca7","datavalue":{"value":{"amount":"+0.8232139348983765","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":"Q653983$2547AC68-6335-4F6E-82CB-EDF1BBDE8769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2919de4b5d8aa02ab2b6631296436f1eb6f7314b","datavalue":{"value":{"entity-type":"item","numeric-id":2936671,"id":"Q2936671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdf878e2af7ee6b52b8285640a5ca9fbe43dce1a","datavalue":{"value":{"amount":"+0.8219425678253174","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":"Q653983$06F96FC6-27A8-43D5-A79C-08410C277AB2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:653983","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:653983"}}}}}