{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T11:42:30Z","timestamp":1772451750368,"version":"3.50.1"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2009,7,1]],"date-time":"2009-07-01T00:00:00Z","timestamp":1246406400000},"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":[[2009,7]]},"abstract":"<jats:p>An <jats:italic>n<\/jats:italic>-vertex graph <jats:italic>G<\/jats:italic> is <jats:italic>c-Ramsey<\/jats:italic> if it contains neither a complete nor an empty induced subgraph of size greater than <jats:italic>c<\/jats:italic> log <jats:italic>n<\/jats:italic>. Erd\u0151s, Faudree and S\u00f3s conjectured that every <jats:italic>c<\/jats:italic>-Ramsey graph with <jats:italic>n<\/jats:italic> vertices contains \u03a9(<jats:italic>n<\/jats:italic><jats:sup>5\/2<\/jats:sup>) induced subgraphs, any two of which differ either in the number of vertices or in the number of edges, <jats:italic>i.e.<\/jats:italic>, the number of distinct pairs (|<jats:italic>V<\/jats:italic>(<jats:italic>H<\/jats:italic>)|, |<jats:italic>E<\/jats:italic>(<jats:italic>H<\/jats:italic>)|), as <jats:italic>H<\/jats:italic> ranges over all induced subgraphs of <jats:italic>G<\/jats:italic>, is \u03a9(<jats:italic>n<\/jats:italic><jats:sup>5\/2<\/jats:sup>). We prove an \u03a9(<jats:italic>n<\/jats:italic><jats:sup>2.3693<\/jats:sup>) lower bound.<\/jats:p>","DOI":"10.1017\/s0963548309009869","type":"journal-article","created":{"date-parts":[[2009,3,30]],"date-time":"2009-03-30T18:32:44Z","timestamp":1238437964000},"page":"459-476","source":"Crossref","is-referenced-by-count":7,"title":["Sizes of Induced Subgraphs of Ramsey Graphs"],"prefix":"10.1017","volume":"18","author":[{"given":"NOGA","family":"ALON","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00d3ZSEF","family":"BALOGH","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDR","family":"KOSTOCHKA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WOJCIECH","family":"SAMOTIJ","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,7,1]]},"reference":[{"key":"S0963548309009869_ref7","first-page":"231","article-title":"Some of my favorite problems in various branches of combinatorics","volume":"47","author":"Erd\u0151s","year":"1992","journal-title":"Matematiche (Catania)"},{"key":"S0963548309009869_ref10","unstructured":"[10] Erd\u0151s P. and Hajnal A. (1977) On spanned subgraphs of graphs. In Contributions to Graph Theory and its Applications (Internat. Colloq., Oberhof, 1977), pp. 80\u201396."},{"key":"S0963548309009869_ref1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199709)11:2<179::AID-RSA5>3.0.CO;2-P"},{"key":"S0963548309009869_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10117"},{"key":"S0963548309009869_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02018669"},{"key":"S0963548309009869_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190120113"},{"key":"S0963548309009869_ref12","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1999.2972"},{"key":"S0963548309009869_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.09.006"},{"key":"S0963548309009869_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_3"},{"key":"S0963548309009869_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00044-1"},{"key":"S0963548309009869_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20250"},{"key":"S0963548309009869_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"S0963548309009869_ref13","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2845"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309009869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,7]],"date-time":"2019-04-07T18:57:55Z","timestamp":1554663475000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309009869\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["S0963548309009869"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309009869","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7]]}}}