{"entities":{"Q2415089":{"pageid":2425832,"ns":120,"title":"Item:Q2415089","lastrevid":74218251,"modified":"2026-04-14T19:01:32Z","type":"item","id":"Q2415089","labels":{"en":{"language":"en","value":"Independence number of graphs with a prescribed number of cliques"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7056832"}},"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":"Q2415089$07CACE7D-3ACB-4E58-B1B0-945E66771DDC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3331b09559dfef987606cd86d1a099be805ec2ca","datavalue":{"value":{"text":"Independence number of graphs with a prescribed number of cliques","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2415089$888F48D5-3FB5-4F39-8837-C36728369533","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b695b460a872b734c60bfbcecdc8455a5640769","datavalue":{"value":"1412.05107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415089$DF85B0E4-B8BB-4DB3-B5D7-A0AB4F480B1E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"044c3bdf3596cdc4b56e2781949e43b4aeb4f370","datavalue":{"value":{"entity-type":"item","numeric-id":200901,"id":"Q200901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$A7636D2A-51C4-44E9-8494-5AAA06C8708B","rank":"normal"},{"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":"Q2415089$2AEA0403-17A2-408B-BECC-113636BD8962","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$4EE9D207-A101-41F2-B463-DEC1038E0F41","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"76aea2b75495bec6f97e62ffc31f2b341286902a","datavalue":{"value":{"time":"+2019-05-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":"Q2415089$D57CE76C-015F-47EC-8E4B-69AB26AC22DA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"77e0785385e1e77007de426087575710d631e66d","datavalue":{"value":"https://arxiv.org/abs/1801.01091","type":"string"},"datatype":"url"},"type":"statement","id":"Q2415089$105E0327-B7F8-44F5-96E2-B8CC5C38F8F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d5800fb80b4a78fa80a750f76cfac062b77487c0","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p25","type":"string"},"datatype":"url"},"type":"statement","id":"Q2415089$314471D4-313F-47ED-AD97-C32191DB7B01","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"307e9a5960ffd2f5ef9f6a9143f94e6afd72818e","datavalue":{"value":"Summary: We consider the following problem posed by \\textit{P. Erd\u0151s} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 459--464 (1962; Zbl 0116.01202)]. Suppose that \\(G\\) is an \\(n\\)-vertex graph where the number of \\(s\\)-cliques in \\(G\\) is \\(t\\). How small can the independence number of \\(G\\) be? Our main result suggests that for fixed $s$, the smallest possible independence number undergoes a transition at \\(t=n^{s/2+o(1)}\\).  In the case of triangles (\\(s=3\\)) our method yields the following result which is sharp apart from constant factors and generalizes basic results in Ramsey theory: there exists \\(c>0\\) such that every \\(n\\)-vertex graph with \\(t\\) triangles has independence number at least \\[ c \\cdot \\min\\left\\{\\sqrt{n \\log n},\\,\\frac{n}{t^{1/3}} \\left(\\log\\frac{n}{t^{1/3}}\\right)^{2/3}\\right\\}.\\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q2415089$4EF49318-2064-4E47-B876-1D683467C4BB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415089$05E50006-1C35-4E8B-B074-B71D1C899099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415089$E91D8E78-12D6-4828-B6A6-A4F6BE2F7837","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415089$E63001A9-AF5A-45B5-B0A3-BF824E7CCA16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415089$CBE90F09-7A99-4184-B950-561AD760F835","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a0961493d860099bd8a7d80ead6864338bd37547","datavalue":{"value":"7056832","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415089$B1CD0021-5DC4-4917-BC07-3FB72D2CF01C","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":"Q2415089$EC9BE2E1-568E-4E3A-B830-B3EFE7DE8F9D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52c7540760fe9ef3923a27be3c87c2aba62dfedc","datavalue":{"value":{"entity-type":"item","numeric-id":1149967,"id":"Q1149967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$4EC4E3F9-5554-4154-9C8D-C4FD90188A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e23a0e274687e86a5e75a720ea8cad4a219781a4","datavalue":{"value":{"entity-type":"item","numeric-id":1023043,"id":"Q1023043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$0C12492C-D9C6-4338-B00E-07A6D188C8BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73e5909188526138317dd48531e52bdc058b1f00","datavalue":{"value":{"entity-type":"item","numeric-id":5420011,"id":"Q5420011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$039E6009-ED64-4818-BA1C-2B2130BB91DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b07d6ae8072ec0b52d1a52248f558d67752e38c","datavalue":{"value":{"entity-type":"item","numeric-id":2743189,"id":"Q2743189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$2B1E8FDA-0632-46D1-99E7-F22E48BD6E0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84f8e1adea89f2849ad11871c497ace2e9031f45","datavalue":{"value":{"entity-type":"item","numeric-id":744160,"id":"Q744160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$4B245E67-4AB7-4544-AB6D-DD58F188F9A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5566417c2088884ccd866ade6700737a5ae2cec","datavalue":{"value":{"entity-type":"item","numeric-id":5724802,"id":"Q5724802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$863B030E-C651-4F57-9EE0-D6AE4F2A053F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8533499f7ff81508e8ebd49ceeba88a0de19c7f0","datavalue":{"value":{"entity-type":"item","numeric-id":5108704,"id":"Q5108704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$39CFDAB9-C8FB-4C7B-BAC5-138096DD18B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b356f40629a4b02fba2defe0109d7c59fcc5a93","datavalue":{"value":{"entity-type":"item","numeric-id":3122312,"id":"Q3122312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$0FFB47A4-E5A5-4961-A313-176C3D21A343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15132b3e75729a6d081fd45a4b035add2a9fce88","datavalue":{"value":{"entity-type":"item","numeric-id":4851927,"id":"Q4851927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$2E7D04D2-804A-45D6-B17C-9D3691F42903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eccbe6ec47dcb47c6a9ee9b874f2e69c450d563","datavalue":{"value":{"entity-type":"item","numeric-id":2757078,"id":"Q2757078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$9676BD61-F391-4765-A1E4-003C0D0EDB75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23acee77d1f4befa62be3cb55faa63af1aacf1ed","datavalue":{"value":{"entity-type":"item","numeric-id":5397739,"id":"Q5397739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2415089$FDAC9F8F-1899-4693-9D39-F96E1DE351B6","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"66cd313f941b9174d21e938bb230485651772e91","datavalue":{"value":"bafkreicddtfhy3uykyxyxfhnoq3vvrkcweb33rflw2tqwpwtqeh263abva","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2415089$C1616499-829E-4020-ADAA-B097FBA30DE0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eaad9af9d9e9d2fba1f00e149a84fb05295973c3","datavalue":{"value":{"entity-type":"item","numeric-id":2757078,"id":"Q2757078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffe878b403f12b66c7087d94af8e0d03575f07ab","datavalue":{"value":{"amount":"+0.8267216682434082","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":"Q2415089$B6450237-97B0-4697-9245-83196CBA0D24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7079b0c6e27a25be02478cd12a10320c9953ba8","datavalue":{"value":{"entity-type":"item","numeric-id":5397739,"id":"Q5397739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"238b0cc51411e324df235b395bd37c3da3196248","datavalue":{"value":{"amount":"+0.8079805970191956","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":"Q2415089$BFB32D98-9CF8-41D8-A268-26E63876661B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ded385f662012b020ee31c2541ed174b2ddf4273","datavalue":{"value":{"entity-type":"item","numeric-id":5434251,"id":"Q5434251"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ab8a31b4423edfc96509a936a59cc7ddf5456b6","datavalue":{"value":{"amount":"+0.801703929901123","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":"Q2415089$A7A7BE06-E689-413E-A3DC-26795007F50F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0cd1c452b361531623ce111851028214b8c29844","datavalue":{"value":{"entity-type":"item","numeric-id":3190316,"id":"Q3190316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3edef8e66dfeceb3c1ef437dc8244e6bbfc4fa0a","datavalue":{"value":{"amount":"+0.7979512214660645","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":"Q2415089$EC5E6D0D-B328-41B3-AABF-D316779E15A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4369d6cd30bb29de9a5768d783b8f5a0dd694f18","datavalue":{"value":{"entity-type":"item","numeric-id":5443808,"id":"Q5443808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccfa5d2f48a10a217aba0d6bdaca39a4adb763b8","datavalue":{"value":{"amount":"+0.7949352860450745","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":"Q2415089$739BC18E-2809-4D6E-B68D-E35D91E16896","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independence number of graphs with a prescribed number of cliques","badges":[]}}}}}