---
OA_place: repository
OA_type: green
_id: '22161'
abstract:
- lang: eng
  text: "Recently, Souza introduced blowup Ramsey numbers as a gener-\r\nalization
    of bipartite Ramsey numbers. For graphs G and H, say\r\nG r\r\n−→ H if every r-edge-coloring
    of G contains a monochromatic\r\ncopy of H. Let H[t] denote the t-blowup of H.
    Then the blowup\r\nRamsey number of G, H, r, and t is defined as the minimum n\r\nsuch
    that G[n] r\r\n−→ H[t]. Souza proved upper and lower bounds on\r\nn that are exponential
    in t, and conjectured that the exponential\r\nconstant does not depend on G. We
    prove that the dependence on\r\nG in the exponential constant is indeed unnecessary,
    but conjecture\r\nthat some dependence on G is unavoidable.\r\nAn important step
    in both Souza’s proof and ours is a theorem of\r\nNikiforov, which says that if
    a graph contains a constant fraction\r\nof the possible copies of H, then it contains
    a blowup of H of\r\nlogarithmic size. We also provide a new proof of this theorem
    with\r\na better quantitative dependence."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Sammy
  full_name: Luo, Sammy
  last_name: Luo
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, Luo S, Wigderson Y. Extremal and Ramsey results on graph blowups. <i>Journal
    of Combinatorics</i>. 2021;12(1):1-15. doi:<a href="https://doi.org/10.4310/joc.2021.v12.n1.a1">10.4310/joc.2021.v12.n1.a1</a>
  apa: Fox, J., Luo, S., &#38; Wigderson, Y. (2021). Extremal and Ramsey results on
    graph blowups. <i>Journal of Combinatorics</i>. International Press of Boston.
    <a href="https://doi.org/10.4310/joc.2021.v12.n1.a1">https://doi.org/10.4310/joc.2021.v12.n1.a1</a>
  chicago: Fox, Jacob, Sammy Luo, and Yuval Wigderson. “Extremal and Ramsey Results
    on Graph Blowups.” <i>Journal of Combinatorics</i>. International Press of Boston,
    2021. <a href="https://doi.org/10.4310/joc.2021.v12.n1.a1">https://doi.org/10.4310/joc.2021.v12.n1.a1</a>.
  ieee: J. Fox, S. Luo, and Y. Wigderson, “Extremal and Ramsey results on graph blowups,”
    <i>Journal of Combinatorics</i>, vol. 12, no. 1. International Press of Boston,
    pp. 1–15, 2021.
  ista: Fox J, Luo S, Wigderson Y. 2021. Extremal and Ramsey results on graph blowups.
    Journal of Combinatorics. 12(1), 1–15.
  mla: Fox, Jacob, et al. “Extremal and Ramsey Results on Graph Blowups.” <i>Journal
    of Combinatorics</i>, vol. 12, no. 1, International Press of Boston, 2021, pp.
    1–15, doi:<a href="https://doi.org/10.4310/joc.2021.v12.n1.a1">10.4310/joc.2021.v12.n1.a1</a>.
  short: J. Fox, S. Luo, Y. Wigderson, Journal of Combinatorics 12 (2021) 1–15.
date_created: 2026-06-29T10:52:13Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2026-07-08T10:41:31Z
day: '01'
doi: 10.4310/joc.2021.v12.n1.a1
extern: '1'
external_id:
  arxiv:
  - '1912.08328'
intvolume: '        12'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.1912.08328
mathsc:
- 05C35
- 05C55
month: '01'
oa: 1
oa_version: Preprint
page: 1-15
publication: Journal of Combinatorics
publication_identifier:
  eissn:
  - 2150-959X
  issn:
  - 2156-3527
publication_status: published
publisher: International Press of Boston
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extremal and Ramsey results on graph blowups
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2021'
...