---
OA_place: repository
OA_type: green
_id: '22158'
abstract:
- lang: eng
  text: "The triangle removal states that if G contains  edge-disjoint triangles,
    then G contains  triangles. Unfortunately, there are no sensible bounds on the
    order of growth of , and at any rate, it is known that  is not polynomial in .
    Csaba recently obtained an asymmetric variant of the triangle removal, stating
    that if G contains  edge-disjoint triangles, then G contains  copies of . To this
    end, he devised a new variant of Szemerédi’s regularity lemma. We obtain the following
    results:\r\n\r\n• We first give a regularity-free proof of Csaba’s theorem, which
    improves the number of copies of  to the optimal number .\r\n\r\n• We say that
    H is -abundant if every graph containing  edge-disjoint triangles has  copies
    of H. It is easy to see that a -abundant graph must be triangle-free and tripartite.
    Given our first result, it is natural to ask if all triangle-free tripartite graphs
    are -abundant. Our second result is that assuming a well-known conjecture of Ruzsa
    in additive number theory, the answer to this question is negative.\r\n\r\nOur
    proofs use a mix of combinatorial, number-theoretic, probabilistic and Ramsey-type
    arguments."
article_number: e38
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Lior
  full_name: Gishboliner, Lior
  last_name: Gishboliner
- first_name: Asaf
  full_name: Shapira, Asaf
  last_name: Shapira
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Gishboliner L, Shapira A, Wigderson Y. An efficient asymmetric removal lemma
    and its limitations. <i>Forum of Mathematics, Sigma</i>. 2025;13. doi:<a href="https://doi.org/10.1017/fms.2024.68">10.1017/fms.2024.68</a>
  apa: Gishboliner, L., Shapira, A., &#38; Wigderson, Y. (2025). An efficient asymmetric
    removal lemma and its limitations. <i>Forum of Mathematics, Sigma</i>. Cambridge
    University Press. <a href="https://doi.org/10.1017/fms.2024.68">https://doi.org/10.1017/fms.2024.68</a>
  chicago: Gishboliner, Lior, Asaf Shapira, and Yuval Wigderson. “An Efficient Asymmetric
    Removal Lemma and Its Limitations.” <i>Forum of Mathematics, Sigma</i>. Cambridge
    University Press, 2025. <a href="https://doi.org/10.1017/fms.2024.68">https://doi.org/10.1017/fms.2024.68</a>.
  ieee: L. Gishboliner, A. Shapira, and Y. Wigderson, “An efficient asymmetric removal
    lemma and its limitations,” <i>Forum of Mathematics, Sigma</i>, vol. 13. Cambridge
    University Press, 2025.
  ista: Gishboliner L, Shapira A, Wigderson Y. 2025. An efficient asymmetric removal
    lemma and its limitations. Forum of Mathematics, Sigma. 13, e38.
  mla: Gishboliner, Lior, et al. “An Efficient Asymmetric Removal Lemma and Its Limitations.”
    <i>Forum of Mathematics, Sigma</i>, vol. 13, e38, Cambridge University Press,
    2025, doi:<a href="https://doi.org/10.1017/fms.2024.68">10.1017/fms.2024.68</a>.
  short: L. Gishboliner, A. Shapira, Y. Wigderson, Forum of Mathematics, Sigma 13
    (2025).
date_created: 2026-06-29T10:51:07Z
date_published: 2025-02-10T00:00:00Z
date_updated: 2026-07-08T10:31:22Z
day: '10'
doi: 10.1017/fms.2024.68
extern: '1'
external_id:
  arxiv:
  - '2301.07693'
intvolume: '        13'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2301.07693
mathsc:
- 05C35
- 11B75
month: '02'
oa: 1
oa_version: Preprint
publication: Forum of Mathematics, Sigma
publication_identifier:
  issn:
  - 2050-5094
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: An efficient asymmetric removal lemma and its limitations
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2025'
...
---
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'
...