{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T06:16:01Z","timestamp":1771481761982,"version":"3.50.1"},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T00:00:00Z","timestamp":1380585600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>Erd\u0151s asked in 1962 about the value of<jats:italic>f<\/jats:italic>(<jats:italic>n<\/jats:italic>,<jats:italic>k<\/jats:italic>,<jats:italic>l<\/jats:italic>), the minimum number of<jats:italic>k<\/jats:italic>-cliques in a graph with order<jats:italic>n<\/jats:italic>and independence number less than<jats:italic>l<\/jats:italic>. The case (<jats:italic>k<\/jats:italic>,<jats:italic>l<\/jats:italic>)=(3,3) was solved by Lorden. Here we solve the problem (for all large<jats:italic>n<\/jats:italic>) for (3,<jats:italic>l<\/jats:italic>) with 4 \u2264<jats:italic>l<\/jats:italic>\u2264 7 and (<jats:italic>k<\/jats:italic>,3) with 4 \u2264<jats:italic>k<\/jats:italic>\u2264 7. Independently, Das, Huang, Ma, Naves and Sudakov resolved the cases (<jats:italic>k<\/jats:italic>,<jats:italic>l<\/jats:italic>)=(3,4) and (4,3).<\/jats:p>","DOI":"10.1017\/s0963548313000357","type":"journal-article","created":{"date-parts":[[2013,10,8]],"date-time":"2013-10-08T08:23:16Z","timestamp":1381220596000},"page":"910-934","source":"Crossref","is-referenced-by-count":25,"title":["Minimum Number of<i>k<\/i>-Cliques in Graphs with Bounded Independence Number"],"prefix":"10.1017","volume":"22","author":[{"given":"OLEG","family":"PIKHURKO","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"EMIL R.","family":"VAUGHAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,10,1]]},"reference":[{"key":"S0963548313000357_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(68)80024-9"},{"key":"S0963548313000357_ref14","doi-asserted-by":"publisher","DOI":"10.2307\/2312538"},{"key":"S0963548313000357_ref16","unstructured":"Nikiforov V. (2005) The minimum number of 4-cliques in a graph with triangle-free complement. E-print arXiv.org:math\/050121."},{"key":"S0963548313000357_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"S0963548313000357_ref6","first-page":"459","article-title":"On the number of complete subgraphs contained in certain graphs.","volume":"7","author":"Erd\u0151s","year":"1962","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u0151zl."},{"key":"S0963548313000357_ref10","doi-asserted-by":"publisher","DOI":"10.2307\/2310464"},{"key":"S0963548313000357_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548301004722"},{"key":"S0963548313000357_ref20","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350785"},{"key":"S0963548313000357_ref3","volume-title":"Extremal Graph Theory","author":"Bollob\u00e1s","year":"1978"},{"key":"S0963548313000357_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.006"},{"key":"S0963548313000357_ref7","unstructured":"Falgas-Ravry V. , Marchant E. , Pikhurko O. and Vaughan E. R. (2013) The codegree threshold for 3-graphs with independent neighbourhoods. E-print arXiv.org:1307.0075."},{"key":"S0963548313000357_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/090747476"},{"key":"S0963548313000357_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.05.002"},{"key":"S0963548313000357_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000222"},{"key":"S0963548313000357_ref23","unstructured":"Vaughan E. R. (2013) Flagmatic: A tool for researchers in extremal graph theory. Version 2.0, http:\/\/flagmatic.org\/."},{"key":"S0963548313000357_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000508"},{"key":"S0963548313000357_ref12","unstructured":"Hirst J. (2011) The inducibility of graphs on four vertices. E-print arXiv.org:1109.1592."},{"key":"S0963548313000357_ref18","unstructured":"Pikhurko O. and Vaughan E. R. (2013) Minimum number of k-cliques in graphs with bounded independence number. E-print arXiv.1203.4393, version 4."},{"key":"S0963548313000357_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2013.02.003"},{"key":"S0963548313000357_ref8","doi-asserted-by":"crossref","first-page":"P40","DOI":"10.37236\/2733","article-title":"Tur\u00e1n H-densities for 3-graphs","volume":"19","author":"Falgas-Ravry","year":"2012","journal-title":"Electron. J. Combin."},{"key":"S0963548313000357_ref19","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"S0963548313000357_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2012.12.008"},{"key":"S0963548313000357_ref22","first-page":"667","volume-title":"Paul Erd\u0151s and his Mathematics","author":"Thomason","year":"2002"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000357","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,5]],"date-time":"2020-08-05T13:04:34Z","timestamp":1596632674000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000357\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,1]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["S0963548313000357"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000357","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,1]]}}}