{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T20:12:21Z","timestamp":1774037541715,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:00:00Z","timestamp":1743033600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T00:00:00Z","timestamp":1743033600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"EPFL Lausanne"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>For two graphs <jats:italic>F<\/jats:italic>,\u00a0<jats:italic>H<\/jats:italic> and a positive integer <jats:italic>n<\/jats:italic>, the function <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$f_{F,H}(n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>F<\/mml:mi>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:mi>H<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> denotes the largest <jats:italic>m<\/jats:italic> such that every <jats:italic>H<\/jats:italic>-free graph on <jats:italic>n<\/jats:italic> vertices contains an <jats:italic>F<\/jats:italic>-free induced subgraph on <jats:italic>m<\/jats:italic> vertices. This function has been extensively studied in the last 60 years when <jats:italic>F<\/jats:italic> and <jats:italic>H<\/jats:italic> are cliques and became known as the Erd\u0151s\u2013Rogers function. Recently, Balogh, Chen and Luo, and Mubayi and Verstra\u00ebte initiated the systematic study of this function in the case where <jats:italic>F<\/jats:italic> is a general graph. Answering, in a strong form, a question of Mubayi and Verstra\u00ebte, we prove that for every positive integer <jats:italic>r<\/jats:italic> and every <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$K_{r-1}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-free graph <jats:italic>F<\/jats:italic>, there exists some <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varepsilon _F&gt;0$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>\u03b5<\/mml:mi>\n                      <mml:mi>F<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> such that <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$f_{F,K_r}(n)=O(n^{1\/2-\\varepsilon _F})$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>F<\/mml:mi>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:msub>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:mi>r<\/mml:mi>\n                        <\/mml:msub>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mn>1<\/mml:mn>\n                          <mml:mo>\/<\/mml:mo>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:mo>-<\/mml:mo>\n                          <mml:msub>\n                            <mml:mi>\u03b5<\/mml:mi>\n                            <mml:mi>F<\/mml:mi>\n                          <\/mml:msub>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. This result is tight in two ways. Firstly, it is no longer true if <jats:italic>F<\/jats:italic> contains <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$K_{r-1}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> as a subgraph. Secondly, we show that for all <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$r\\ge 4$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>4<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> and <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\varepsilon &gt;0$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b5<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>0<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, there exists a <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$K_{r-1}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>K<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:msub>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-free graph <jats:italic>F<\/jats:italic> for which <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$f_{F,K_r}(n)=\\Omega (n^{1\/2-\\varepsilon })$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>F<\/mml:mi>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:msub>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:mi>r<\/mml:mi>\n                        <\/mml:msub>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mn>1<\/mml:mn>\n                          <mml:mo>\/<\/mml:mo>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:mo>-<\/mml:mo>\n                          <mml:mi>\u03b5<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. Along the way of proving this, we show in particular that for every graph <jats:italic>F<\/jats:italic> with minimum degree <jats:italic>t<\/jats:italic>, we have <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$f_{F,K_4}(n)=\\Omega (n^{1\/2-6\/\\sqrt{t}})$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>F<\/mml:mi>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:msub>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:mn>4<\/mml:mn>\n                        <\/mml:msub>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mn>1<\/mml:mn>\n                          <mml:mo>\/<\/mml:mo>\n                          <mml:mn>2<\/mml:mn>\n                          <mml:mo>-<\/mml:mo>\n                          <mml:mn>6<\/mml:mn>\n                          <mml:mo>\/<\/mml:mo>\n                          <mml:msqrt>\n                            <mml:mi>t<\/mml:mi>\n                          <\/mml:msqrt>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. This answers (in a strong form) another question of Mubayi and Verstra\u00ebte. Finally, we prove that there exist absolute constants <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$0&lt;c&lt;C$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mi>c<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mi>C<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> such that for each <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$r\\ge 4$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>4<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, if <jats:italic>F<\/jats:italic> is a bipartite graph with sufficiently large minimum degree, then <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\Omega (n^{\\frac{c}{\\log r}})\\le f_{F,K_r}(n)\\le O(n^{\\frac{C}{\\log r}})$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mfrac>\n                          <mml:mi>c<\/mml:mi>\n                          <mml:mrow>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>r<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:mfrac>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>F<\/mml:mi>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:msub>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:mi>r<\/mml:mi>\n                        <\/mml:msub>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mfrac>\n                          <mml:mi>C<\/mml:mi>\n                          <mml:mrow>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>r<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:mfrac>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. This shows that for graphs <jats:italic>F<\/jats:italic> with large minimum degree, the behaviour of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$f_{F,K_r}(n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mi>F<\/mml:mi>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:msub>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:mi>r<\/mml:mi>\n                        <\/mml:msub>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> is drastically different from that of the corresponding off-diagonal Ramsey number <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$f_{K_2,K_r}(n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>f<\/mml:mi>\n                      <mml:mrow>\n                        <mml:msub>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:mn>2<\/mml:mn>\n                        <\/mml:msub>\n                        <mml:mo>,<\/mml:mo>\n                        <mml:msub>\n                          <mml:mi>K<\/mml:mi>\n                          <mml:mi>r<\/mml:mi>\n                        <\/mml:msub>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00493-025-00147-1","type":"journal-article","created":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T06:05:51Z","timestamp":1743314751000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Induced Subgraphs of $$K_r$$-Free Graphs and the Erd\u0151s\u2013Rogers Problem"],"prefix":"10.1007","volume":"45","author":[{"given":"Lior","family":"Gishboliner","sequence":"first","affiliation":[]},{"given":"Oliver","family":"Janzer","sequence":"additional","affiliation":[]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,27]]},"reference":[{"key":"147_CR1","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/0097-3165(80)90030-8","volume":"29","author":"M Ajtai","year":"1980","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: A note on Ramsey numbers. J. Comb. Theor. Ser. A 29, 354\u2013360 (1980)","journal-title":"J. Comb. Theor. Ser. A"},{"key":"147_CR2","doi-asserted-by":"publisher","first-page":"3145","DOI":"10.1090\/proc\/15323","volume":"149","author":"N Alon","year":"2021","unstructured":"Alon, N., Buci\u0107, M., Sudakov, B.: Large cliques and independent sets all over the place. Proc. Am. Math. Soc. 149, 3145\u20133157 (2021)","journal-title":"Proc. Am. Math. Soc."},{"key":"147_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF03352998","volume":"13","author":"N Alon","year":"1997","unstructured":"Alon, N., Krivelevich, M.: Constructive bounds for a Ramsey-type problem. Graph. Comb. 13, 217\u2013225 (1997)","journal-title":"Graph. Comb."},{"key":"147_CR4","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1017\/S0963548303005741","volume":"12","author":"N Alon","year":"2003","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Tur\u00e1n numbers of bipartite graphs and related Ramsey-type questions. Comb. Probab. Comput. 12, 477\u2013494 (2003)","journal-title":"Comb. Probab. Comput."},{"key":"147_CR5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21273","volume":"66","author":"J Balogh","year":"2025","unstructured":"Balogh, J., Chen, C., Luo, H.: On the maximum $$F$$-free induced subgraphs in $$K_t$$-free graphs. Random Struct. Algorithms 66, e21273 (2025)","journal-title":"Random Struct. Algorithms"},{"key":"147_CR6","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s00222-010-0247-x","volume":"181","author":"T Bohman","year":"2010","unstructured":"Bohman, T., Keevash, P.: The early evolution of the $$H$$-free process. Invent. Math. 181, 291\u2013336 (2010)","journal-title":"Invent. Math."},{"key":"147_CR7","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(91)90042-Z","volume":"87","author":"B Bollob\u00e1s","year":"1991","unstructured":"Bollob\u00e1s, B., Hind, H.: Graphs without large triangle free subgraphs. Discret. Math. 87, 119\u2013131 (1991)","journal-title":"Discret. Math."},{"key":"147_CR8","doi-asserted-by":"publisher","DOI":"10.1112\/blms.13040","author":"D Conlon","year":"2024","unstructured":"Conlon, D., Mattheus, S., Mubayi, D., Verstra\u00ebte, J.: Ramsey numbers and the Zarankiewicz problem. Bull. Lond. Math. Soc. (2024). https:\/\/doi.org\/10.1112\/blms.13040","journal-title":"Bull. Lond. Math. Soc."},{"key":"147_CR9","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1006\/jcta.1997.2745","volume":"77","author":"D de Caen","year":"1997","unstructured":"de Caen, D., Sz\u00e9kely, L.: On dense bipartite graphs of girth eight and upper bounds for certain configurations in planar point-line systems. J. Comb. Theory Ser. A 77, 268\u2013278 (1997)","journal-title":"J. Comb. Theory Ser. A"},{"key":"147_CR10","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1002\/jgt.21760","volume":"76","author":"A Dudek","year":"2014","unstructured":"Dudek, A., Mubayi, D.: On generalized Ramsey numbers for 3-uniform hypergraphs. J. Graph Theory 76, 217\u2013223 (2014)","journal-title":"J. Graph Theory"},{"key":"147_CR11","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.jctb.2014.06.006","volume":"109","author":"A Dudek","year":"2014","unstructured":"Dudek, A., Retter, T., R\u00f6dl, V.: On generalized Ramsey numbers of Erd\u0151s and Rogers. J. Comb. Theory Ser. B 109, 213\u2013227 (2014)","journal-title":"J. Comb. Theory Ser. B"},{"key":"147_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/s00493-011-2626-3","volume":"31","author":"A Dudek","year":"2011","unstructured":"Dudek, A., R\u00f6dl, V.: On $$K_s$$-free subgraphs in $$K_{s+k}$$-free graphs and vertex Folkman numbers. Combinatorica 31, 39\u201353 (2011)","journal-title":"Combinatorica"},{"key":"147_CR13","doi-asserted-by":"crossref","unstructured":"Dudek, A., R\u00f6dl, V.: On the function of Erd\u0151s and Rogers. Ramsey theory: yesterday, today, and tomorrow, pp 63-76 (2011)","DOI":"10.1007\/978-0-8176-8092-3_4"},{"key":"147_CR14","doi-asserted-by":"publisher","first-page":"702","DOI":"10.4153\/CJM-1962-060-4","volume":"14","author":"P Erd\u0151s","year":"1962","unstructured":"Erd\u0151s, P., Rogers, C.: The construction of certain graphs. Can. J. Math. 14, 702\u2013707 (1962)","journal-title":"Can. J. Math."},{"key":"147_CR15","first-page":"463","volume":"2","author":"P Erd\u0151s","year":"1935","unstructured":"Erd\u0151s, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463\u2013470 (1935)","journal-title":"Compos. Math."},{"key":"147_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20344","volume":"38","author":"J Fox","year":"2011","unstructured":"Fox, J., Sudakov, B.: Dependent random choice. Random Struct. Algorithms 38, 1\u201332 (2011)","journal-title":"Random Struct. Algorithms"},{"key":"147_CR17","doi-asserted-by":"publisher","DOI":"10.19086\/aic.12048","author":"WT Gowers","year":"2020","unstructured":"Gowers, W.T., Janzer, O.: Improved bounds for the Erd\u0151s-Rogers function. Adv. Comb. (2020). https:\/\/doi.org\/10.19086\/aic.12048","journal-title":"Adv. Comb."},{"key":"147_CR18","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1016\/S0012-365X(96)00184-7","volume":"165","author":"E Gy\u0151ri","year":"1997","unstructured":"Gy\u0151ri, E.: $$C_6$$-free bipartite graphs and product representation of squares. Discret. Math. 165, 371\u2013375 (1997)","journal-title":"Discret. Math."},{"key":"147_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2024.114203","volume":"347","author":"X Hu","year":"2024","unstructured":"Hu, X., Lin, Q.: Ramsey numbers and a general Erd\u0151s-Rogers function. Discret. Math. 347, 114203 (2024)","journal-title":"Discret. Math."},{"key":"147_CR20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21280","volume":"66","author":"O Janzer","year":"2025","unstructured":"Janzer, O., Sudakov, B.: Improved bounds for the Erd\u0151s-Rogers $$(s, s+2)$$-problem. Random Struct. Algorithms 66, e21280 (2025)","journal-title":"Random Struct. Algorithms"},{"key":"147_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1002\/rsa.3240070302","volume":"7","author":"J Kim","year":"1995","unstructured":"Kim, J.: The Ramsey number $$R(3, t)$$ has order of magnitude $$t^2\/\\log t$$. Random Struct. Algorithms 7, 173\u2013207 (1995)","journal-title":"Random Struct. Algorithms"},{"key":"147_CR22","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1017\/S0963548300001243","volume":"3","author":"M Krivelevich","year":"1994","unstructured":"Krivelevich, M.: $$K_s$$-free graphs without large $$K_r$$-free subgraphs. Comb. Probab. Comput. 3, 349\u2013354 (1994)","journal-title":"Comb. Probab. Comput."},{"key":"147_CR23","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1002\/rsa.3240070204","volume":"7","author":"M Krivelevich","year":"1995","unstructured":"Krivelevich, M.: Bounding Ramsey numbers through large deviation inequalities. Random Struct. Algorithms 7, 145\u2013155 (1995)","journal-title":"Random Struct. Algorithms"},{"key":"147_CR24","doi-asserted-by":"publisher","first-page":"919","DOI":"10.4007\/annals.2024.199.2.8","volume":"199","author":"S Mattheus","year":"2024","unstructured":"Mattheus, S., Verstra\u00ebte, J.: The asymptotics of $$r(4, t)$$. Ann. Math. 199, 919\u2013941 (2024)","journal-title":"Ann. Math."},{"key":"147_CR25","unstructured":"Mubayi, D., Verstra\u00ebte, J.: Erd\u0151s-Rogers functions for arbitrary pairs of graphs. Preprint at ArXiv:2407.03121 (2024)"},{"issue":"2","key":"147_CR26","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1112\/blms.13214","volume":"57","author":"D Mubayi","year":"2024","unstructured":"Mubayi, D., Verstra\u00ebte, J.: On the order of the classical Erd\u0151s-Rogers functions. Bull. Lond. Math. Soc. 57(2), 582\u2013598 (2024)","journal-title":"Bull. Lond. Math. Soc."},{"key":"147_CR27","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/0021-8693(72)90070-1","volume":"20","author":"M O\u2019Nan","year":"1972","unstructured":"O\u2019Nan, M.: Automorphisms of unitary block designs. J. Algebra 20, 495\u2013511 (1972)","journal-title":"J. Algebra"},{"key":"147_CR28","first-page":"2","volume":"18","author":"I Ruzsa","year":"1978","unstructured":"Ruzsa, I., Szemer\u00e9di, E.: Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976). Coll. Math. Soc. J. Bolyai 18, 2 (1978)","journal-title":"Coll. Math. Soc. J. Bolyai"},{"key":"147_CR29","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s00493-005-0029-3","volume":"25","author":"B Sudakov","year":"2005","unstructured":"Sudakov, B.: A new lower bound for a Ramsey-type problem. Combinatorica 25, 487\u2013498 (2005)","journal-title":"Combinatorica"},{"key":"147_CR30","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/rsa.20035","volume":"26","author":"B Sudakov","year":"2005","unstructured":"Sudakov, B.: Large $$K_r$$-free subgraphs in $$K_s$$-free graphs and some other Ramsey-type problems. Random Struct. Algorithms 26, 253\u2013265 (2005)","journal-title":"Random Struct. Algorithms"},{"key":"147_CR31","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1007\/s00493-013-2845-x","volume":"33","author":"G Wolfovitz","year":"2013","unstructured":"Wolfovitz, G.: $$K_4$$-free graphs without large induced triangle-free subgraphs. Combinatorica 33, 623\u2013631 (2013)","journal-title":"Combinatorica"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00147-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00147-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00147-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,6]],"date-time":"2025-05-06T09:01:52Z","timestamp":1746522112000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00147-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,27]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["147"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00147-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,27]]},"assertion":[{"value":"16 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"23"}}