{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T08:31:15Z","timestamp":1772181075843,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,4,15]],"date-time":"2024-04-15T00:00:00Z","timestamp":1713139200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,4,15]],"date-time":"2024-04-15T00:00:00Z","timestamp":1713139200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,8]]},"abstract":"Abstract<\/jats:title>In this paper we study the fundamental problem of finding small dense subgraphs in a given graph. For a real number$$s>2$$<\/jats:tex-math>s<\/mml:mi>><\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we prove that every graph onn<\/jats:italic>vertices with average degree$$d\\ge s$$<\/jats:tex-math>d<\/mml:mi>\u2265<\/mml:mo>s<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>contains a subgraph of average degree at leasts<\/jats:italic>on at most$$nd^{-\\frac{s}{s-2}}(\\log d)^{O_s(1)}$$<\/jats:tex-math>n<\/mml:mi>d<\/mml:mi>-<\/mml:mo>s<\/mml:mi>s<\/mml:mi>-<\/mml:mo>2<\/mml:mn><\/mml:mrow><\/mml:mfrac><\/mml:mrow><\/mml:msup>(<\/mml:mo>log<\/mml:mo>d<\/mml:mi>)<\/mml:mo><\/mml:mrow>O<\/mml:mi>s<\/mml:mi><\/mml:msub>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:msup><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>vertices. This is optimal up to the polylogarithmic factor, and resolves a conjecture of Feige and Wagner. In addition, we show that every graph withn<\/jats:italic>vertices and average degree at least$$n^{1-\\frac{2}{s}+\\varepsilon }$$<\/jats:tex-math>n<\/mml:mi>1<\/mml:mn>-<\/mml:mo>2<\/mml:mn>s<\/mml:mi><\/mml:mfrac>+<\/mml:mo>\u03b5<\/mml:mi><\/mml:mrow><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>contains a subgraph of average degree at leasts<\/jats:italic>on$$O_{\\varepsilon ,s}(1)$$<\/jats:tex-math>O<\/mml:mi>\u03b5<\/mml:mi>,<\/mml:mo>s<\/mml:mi><\/mml:mrow><\/mml:msub>(<\/mml:mo>1<\/mml:mn>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>vertices, which is also optimal up to the constant hidden in theO<\/jats:italic>(.) notation, and resolves a conjecture of Verstra\u00ebte.<\/jats:p>","DOI":"10.1007\/s00493-024-00091-6","type":"journal-article","created":{"date-parts":[[2024,4,15]],"date-time":"2024-04-15T07:01:50Z","timestamp":1713164510000},"page":"785-800","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Small Subgraphs with Large Average Degree"],"prefix":"10.1007","volume":"44","author":[{"given":"Oliver","family":"Janzer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Sudakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Istv\u00e1n","family":"Tomon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,15]]},"reference":[{"issue":"1","key":"91_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s003730200002","volume":"18","author":"N Alon","year":"2002","unstructured":"Alon, N., Hoory, S., Linial, N.: The Moore bound for irregular graphs. Graphs Comb. 18(1), 53\u201357 (2002)","journal-title":"Graphs Comb."},{"issue":"1","key":"91_CR2","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1137\/090780304","volume":"41","author":"S Arora","year":"2012","unstructured":"Arora, S., Lov\u00e1sz, L., Newman, I., Rabani, Y., Rabinovich, Y., Vempala, S.: Local versus global properties of metric spaces. SIAM J. Comput. 41(1), 250\u2013271 (2012)","journal-title":"SIAM J. Comput."},{"key":"91_CR3","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities \u2013 an $$O(n^{1\/4})$$ approximation for densest $$k$$-subgraph, Proceedings of STOC (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"91_CR4","unstructured":"Bhaskara, A., Charikar, M., Guruswami, V., Vijayaraghavan, A., Zhou, Y.: Polynomial integrality gaps for strong SDP relaxations of Densest $$k$$-subgraph, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA12)"},{"key":"91_CR5","volume-title":"Extremal graph theory, Dover Books on Mathematics Series","author":"B Bollob\u00e1s","year":"2004","unstructured":"Bollob\u00e1s, B.: Extremal graph theory, Dover Books on Mathematics Series. Dover Publications, Mineola (2004)"},{"key":"91_CR6","unstructured":"Braverman, M., Ko, Y.K., Rubinstein, A., Weinstein, O.: ETH hardness for Densest-$$k$$-subgraph with perfect completeness. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA17)"},{"key":"91_CR7","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1007\/s00493-023-00023-w","volume":"43","author":"M Buci\u0107","year":"2023","unstructured":"Buci\u0107, M., Sudakov, B.: Large independent sets from local considerations. Combinatorica 43, 505\u2013546 (2023)","journal-title":"Combinatorica"},{"issue":"7","key":"91_CR8","doi-asserted-by":"publisher","first-page":"1747","DOI":"10.4171\/jems\/798","volume":"20","author":"B Bukh","year":"2018","unstructured":"Bukh, B., Conlon, D.: Rational exponents in extremal graph theory. J. Eur. Math. Soc. 20(7), 1747\u20131757 (2018)","journal-title":"J. Eur. Math. Soc."},{"key":"91_CR9","unstructured":"P. Erd\u0151s, Problems and results in graph theory, The theory and applications of graphs (Kalamazoo, MI, 1980), pp. 331\u2013341 (1981)"},{"issue":"1","key":"91_CR10","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0012-365X(90)90162-B","volume":"85","author":"P Erd\u0151s","year":"1990","unstructured":"Erd\u0151s, P., Faudree, J.R., Rousseau, C.C., Schelp, R.H.: Subgraphs of minimal degree $$k$$. Discret. Math. 85(1), 53\u201358 (1990)","journal-title":"Discret. Math."},{"key":"91_CR11","unstructured":"P. Erd\u0151s, J. R. Faudree, C. C. Rousseau, R. H. Schelp, Edge conditions for the existence of minimal degree subgraphs. In Graph theory, combinatorics and applications, Vol. 1. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs, pp. 419\u2013434 (1991)"},{"key":"91_CR12","unstructured":"P. Erd\u0151s, H. Sachs, Regul\u00e4re graphen gegebener taillenweite mit minimaler knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math. Natur. Reihe 12 (1963), 251\u2013257"},{"key":"91_CR13","doi-asserted-by":"crossref","unstructured":"U. Feige, Relations between average case complexity and approximation complexity, In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC\u201902), pp. 534\u2013543. ACM Press, (2002)","DOI":"10.1145\/509984.509985"},{"key":"91_CR14","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/978-3-540-85221-6_9","volume":"19","author":"U Feige","year":"2008","unstructured":"Feige, U.: Small linear dependencies for binary vectors of low weight, building bridges between mathematics and computer science. Bolyai Soc. Math. Stud. 19, 283\u2013307 (2008)","journal-title":"Bolyai Soc. Math. Stud."},{"key":"91_CR15","unstructured":"U. Feige, and T. Wagner, Generalized Girth Problems in Graphs and Hypergraphs, submitted https:\/\/www.wisdom.weizmann.ac.il\/~feige\/mypapers\/TalWagner2016.pdf (2016)"},{"key":"91_CR16","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02579202","volume":"7","author":"J Friedman","year":"1987","unstructured":"Friedman, J., Pippenger, N.: Expanding graphs contain all small trees. Combinatorica 7, 71\u201376 (1987)","journal-title":"Combinatorica"},{"key":"91_CR17","unstructured":"M.\u00a0Gromov, Local and global in geometry. Preprint at www.ihes.fr\/~gromov\/wp-content\/uploads\/2018\/08\/1107.pdf (2018)"},{"key":"91_CR18","doi-asserted-by":"crossref","unstructured":"V. Guruswami, P. K. Kothari, and P. Manohar, Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random, In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 678\u2013689 (2022)","DOI":"10.1145\/3519935.3519955"},{"key":"91_CR19","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1007\/s11856-022-2380-9","volume":"253","author":"O Janzer","year":"2023","unstructured":"Janzer, O.: Rainbow Tur\u00e1n number of even cycles, repeated patterns and blow-ups of cycles. Isr. J. Math. 253, 813\u2013840 (2023)","journal-title":"Isr. J. Math."},{"key":"91_CR20","doi-asserted-by":"publisher","first-page":"8478","DOI":"10.1093\/imrn\/rnac076","volume":"10","author":"O Janzer","year":"2023","unstructured":"Janzer, O.: Disproof of a conjecture of Erd\u0151s and Simonovits on the Tur\u00e1n number of graphs with minimum degree 3. Int. Math. Res. Not. 10, 8478\u20138494 (2023)","journal-title":"Int. Math. Res. Not."},{"key":"91_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/fmp.2023.19","volume":"11","author":"O Janzer","year":"2023","unstructured":"Janzer, O., Sudakov, B.: Resolution of the Erd\u0151s-Sauer problem on regular subgraphs. Forum Math.: Pi 11, e19 (2023)","journal-title":"Forum Math.: Pi"},{"key":"91_CR22","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1137\/15M1007598","volume":"31","author":"T Jiang","year":"2017","unstructured":"Jiang, T., Newman, A.: Small dense subgraphs of a graph. SIAM J. Discret. Math. 31, 124\u2013142 (2017)","journal-title":"SIAM J. Discret. Math."},{"key":"91_CR23","doi-asserted-by":"crossref","unstructured":"S. Khot, Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique, In Proceedings of the 44th Annual IEEE Symposium on the Foundations of Computer Science (FOCS\u201904), pp. 136\u2013145 (2004)","DOI":"10.1109\/FOCS.2004.59"},{"issue":"4","key":"91_CR24","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1017\/S0963548300000857","volume":"2","author":"N Linial","year":"1993","unstructured":"Linial, N.: Local-global phenomena in graphs. Combin. Probab. Comput. 2(4), 491\u2013503 (1993)","journal-title":"Combin. Probab. Comput."},{"issue":"3","key":"91_CR25","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/BF02126799","volume":"8","author":"A Lubotzky","year":"1988","unstructured":"Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261\u2013277 (1988)","journal-title":"Combinatorica"},{"issue":"1","key":"91_CR26","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02579283","volume":"2","author":"G Margulis","year":"1982","unstructured":"Margulis, G.: Explicit constructions of graphs without short cycles and low density codes. Combinatorica 2(1), 71\u201378 (1982)","journal-title":"Combinatorica"},{"issue":"1","key":"91_CR27","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1006\/jctb.1994.1054","volume":"62","author":"M Morgenstern","year":"1994","unstructured":"Morgenstern, M.: Existence and explicit constructions of $$q$$+1 regular Ramanujan graphs for every prime power $$q$$. J. Combin. Theory Ser. B 62(1), 44\u201362 (1994)","journal-title":"J. Combin. Theory Ser. B"},{"key":"91_CR28","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/s00493-008-2195-2","volume":"28","author":"A Naor","year":"2008","unstructured":"Naor, A., Verstra\u00ebte, J.: Parity check matrices and product representations of squares. Combinatorica 28, 163\u2013185 (2008)","journal-title":"Combinatorica"},{"issue":"1","key":"91_CR29","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1007\/s00453-014-9956-7","volume":"74","author":"T Nonner","year":"2016","unstructured":"Nonner, T.: PTAS for Densest $$k$$-subgraph in interval graphs. Algorithmica 74(1), 528\u2013539 (2016)","journal-title":"Algorithmica"},{"key":"91_CR30","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/jctb.1995.1004","volume":"63","author":"L Pyber","year":"1995","unstructured":"Pyber, L., R\u00f6dl, V., Szemer\u00e9di, E.: Dense graphs without 3-regular subgraphs. J. Combin. Theory Ser. B 63, 41\u201354 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"key":"91_CR31","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.jctb.2018.05.002","volume":"134","author":"L Sauermann","year":"2019","unstructured":"Sauermann, L.: A proof of a conjecture of Erd\u0151s, Faudree, Rousseau and Schelp on subgraphs of minimum degree $$k$$. J. Combin. Theory Ser. B 134, 36\u201375 (2019)","journal-title":"J. Combin. Theory Ser. B"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00091-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00091-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00091-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,16]],"date-time":"2024-11-16T07:10:00Z","timestamp":1731741000000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00091-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,15]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["91"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00091-6","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,15]]},"assertion":[{"value":"1 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 December 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}