{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:21:42Z","timestamp":1787322102360,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We consider the variation of Ramsey numbers introduced by Erd\u00f6s and Pach [J. Graph Theory, 7 (1983), pp. 137--147], where instead of seeking complete or independent sets we only seek a $t$-homogeneous set, a vertex subset that induces a subgraph of minimum degree at least $t$ or the complement of such a graph. For any $\\nu &gt; 0$ and positive integer $k$, we show that any graph $G$ or its complement contains as an induced subgraph some graph $H$ on $\\ell \\ge k$ vertices with minimum degree at least $\\frac12(\\ell-1) + \\nu$ provided that $G$ has at least $k^{\\Omega(\\nu^2)}$ vertices. We also show this to be the best possible in a sense. This may be viewed as correction to a result claimed in [P. Erd\u00f6s and J. Pach, J. Graph Theory, 7 (1983), pp. 137--147]. For the above result, we permit $H$ to have order at least $k$. In the harder problem, where we insist that $H$ have exactly $k$ vertices, we do not obtain sharp results, although we show a way to translate results of one form of the problem to the other.<\/jats:p>","DOI":"10.1137\/14097313x","type":"journal-article","created":{"date-parts":[[2015,9,10]],"date-time":"2015-09-10T13:56:55Z","timestamp":1441893415000},"page":"1670-1682","source":"Crossref","is-referenced-by-count":4,"title":["A Precise Threshold for Quasi-Ramsey Numbers"],"prefix":"10.1137","volume":"29","author":[{"given":"Ross J.","family":"Kang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Viresh","family":"Patel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guus","family":"Regts","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,9,10]]},"reference":[{"key":"atypb1","unstructured":"B. Bolloba\u0301s,\n                      Random Graphs\n                      , 2nd ed., Cambridge Stud. Adv. Math. 73, Cambridge University Press, Cambridge, 2001."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2009.170.941"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Dembo and O. Zeitouni,\n                      Large Deviations Techniques and Applications\n                      , 2nd ed., Appl. Math. (New York) 38, Springer-Verlag, New York, 1998.","DOI":"10.1007\/978-1-4612-5320-4"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1947-08785-1"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190070117"},{"key":"atypb7","unstructured":"P. Erdo\u0308s and J. Spencer,\n                      Probabilistic Methods in Combinatorics\n                      , Probab. Math. Statist., Academic Press, New York, 1974."},{"key":"atypb8","first-page":"463","volume":"2","author":"Erdo\u0308s P.","year":"1935","journal-title":"Compos. Math."},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"S. Janson, T. \u0141uczak, and A. Rucinski,\n                      Random Graphs\n                      , Wiley-Intersci. Ser. Discrete Math. Optim., Wiley-Interscience, New York, 2000.","DOI":"10.1002\/9781118032718"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990216"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"R. J. Kang, V. Patel, and G. Regts,\n                      On a Ramsey-Type Problem of Erdo\u0308s and Pach\n                      , arXiv:1411.4459, 2014.","DOI":"10.1016\/j.endm.2015.06.049"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(75)90071-0"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14097313X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:18:12Z","timestamp":1787318292000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14097313X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/14097313X"],"URL":"https:\/\/doi.org\/10.1137\/14097313x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}