---
OA_place: publisher
OA_type: hybrid
_id: '22152'
abstract:
- lang: eng
  text: "We study off-diagonal Ramsey numbers \U0001D45F⁡(\U0001D43B,\U0001D43E(\U0001D458)\r\n\U0001D45B)
    of \U0001D458-uniform hypergraphs, where \U0001D43B is a fixed linear \U0001D458-uniform
    hypergraph and \U0001D43E(\U0001D458)\r\n\U0001D45B is complete on \U0001D45B
    vertices. Recently, Conlon, Fox, Gunby, He, Mubayi, Suk, and Verstraëte disproved
    the folklore conjecture that \U0001D45F⁡(\U0001D43B,\U0001D43E(3)\r\n\U0001D45B)
    always grows polynomially in \U0001D45B. In this paper, we show that much larger
    growth rates are possible in higher uniformity. In uniformity \U0001D458 ≥4, we
    prove that for any constant \U0001D436 >0, there exists a linear \U0001D458-uniform
    hypergraph \U0001D43B for which\r\n\r\n\U0001D45F⁡(\U0001D43B,\U0001D43E(\U0001D458)\r\n\U0001D45B)≥twr\U0001D458−2⁢(2(log⁡\U0001D45B)\U0001D436)."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Jiaxi
  full_name: Nie, Jiaxi
  last_name: Nie
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
- first_name: Hung-Hsun
  full_name: Yu, Hung-Hsun
  last_name: Yu
citation:
  ama: He X, Nie J, Wigderson Y, Yu H-H. Off-diagonal Ramsey numbers for linear hypergraphs.
    <i>Combinatorics, Probability and Computing</i>. 2026:1-14. doi:<a href="https://doi.org/10.1017/s0963548326100443">10.1017/s0963548326100443</a>
  apa: He, X., Nie, J., Wigderson, Y., &#38; Yu, H.-H. (2026). Off-diagonal Ramsey
    numbers for linear hypergraphs. <i>Combinatorics, Probability and Computing</i>.
    Cambridge University Press. <a href="https://doi.org/10.1017/s0963548326100443">https://doi.org/10.1017/s0963548326100443</a>
  chicago: He, Xiaoyu, Jiaxi Nie, Yuval Wigderson, and Hung-Hsun Yu. “Off-Diagonal
    Ramsey Numbers for Linear Hypergraphs.” <i>Combinatorics, Probability and Computing</i>.
    Cambridge University Press, 2026. <a href="https://doi.org/10.1017/s0963548326100443">https://doi.org/10.1017/s0963548326100443</a>.
  ieee: X. He, J. Nie, Y. Wigderson, and H.-H. Yu, “Off-diagonal Ramsey numbers for
    linear hypergraphs,” <i>Combinatorics, Probability and Computing</i>. Cambridge
    University Press, pp. 1–14, 2026.
  ista: He X, Nie J, Wigderson Y, Yu H-H. 2026. Off-diagonal Ramsey numbers for linear
    hypergraphs. Combinatorics, Probability and Computing., 1–14.
  mla: He, Xiaoyu, et al. “Off-Diagonal Ramsey Numbers for Linear Hypergraphs.” <i>Combinatorics,
    Probability and Computing</i>, Cambridge University Press, 2026, pp. 1–14, doi:<a
    href="https://doi.org/10.1017/s0963548326100443">10.1017/s0963548326100443</a>.
  short: X. He, J. Nie, Y. Wigderson, H.-H. Yu, Combinatorics, Probability and Computing
    (2026) 1–14.
date_created: 2026-06-29T10:47:02Z
date_published: 2026-04-14T00:00:00Z
date_updated: 2026-07-08T07:24:54Z
day: '14'
ddc:
- '500'
doi: 10.1017/s0963548326100443
extern: '1'
external_id:
  arxiv:
  - '2507.05641'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1017/S0963548326100443
mathsc:
- 05D10
- 05D40
- 05C65
month: '04'
oa: 1
oa_version: Published Version
page: 1-14
publication: Combinatorics, Probability and Computing
publication_identifier:
  eissn:
  - 1469-2163
  issn:
  - 0963-5483
publication_status: epub_ahead
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Off-diagonal Ramsey numbers for linear hypergraphs
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '22167'
abstract:
- lang: eng
  text: "Given a vertex-ordered graph G, the ordered Ramsey number\r\nr<(G) is the
    minimum integer N such that every 2-coloring of the edges of\r\nthe complete ordered
    graph KN contains a monochromatic ordered copy of G.\r\nMotivated by a similar
    question posed by Erd˝os and Graham [On partition\r\ntheorems for finite graphs,
    Infinite and finite sets (Colloq., Keszthely, 1973),\r\nNorth-Holland, Amsterdam-London,
    pp. 515–527] in the unordered setting,\r\nwe study the problem of bounding the
    ordered Ramsey number of any ordered graph G with m edges and no isolated vertices.
    We prove that r<(G) ≤\r\ne109√m(log log m)3/2\r\nfor any such G, which is tight
    up to the (log log m)3/2\r\nfactor in the exponent. As a corollary, we obtain
    the corresponding bound for\r\nthe oriented Ramsey number of a directed graph
    with m edges."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Domagoj
  full_name: Bradač, Domagoj
  last_name: Bradač
- first_name: Patryk
  full_name: Morawski, Patryk
  last_name: Morawski
- first_name: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: "Bradač D, Morawski P, Sudakov B, Wigderson Y. Ordered Ramsey numbers of graphs
    with \U0001D45A edges. <i>Proceedings of the American Mathematical Society</i>.
    2026;154(3):927-942. doi:<a href=\"https://doi.org/10.1090/proc/17442\">10.1090/proc/17442</a>"
  apa: "Bradač, D., Morawski, P., Sudakov, B., &#38; Wigderson, Y. (2026). Ordered
    Ramsey numbers of graphs with \U0001D45A edges. <i>Proceedings of the American
    Mathematical Society</i>. American Mathematical Society. <a href=\"https://doi.org/10.1090/proc/17442\">https://doi.org/10.1090/proc/17442</a>"
  chicago: "Bradač, Domagoj, Patryk Morawski, Benny Sudakov, and Yuval Wigderson.
    “Ordered Ramsey Numbers of Graphs with \U0001D45A Edges.” <i>Proceedings of the
    American Mathematical Society</i>. American Mathematical Society, 2026. <a href=\"https://doi.org/10.1090/proc/17442\">https://doi.org/10.1090/proc/17442</a>."
  ieee: "D. Bradač, P. Morawski, B. Sudakov, and Y. Wigderson, “Ordered Ramsey numbers
    of graphs with \U0001D45A edges,” <i>Proceedings of the American Mathematical
    Society</i>, vol. 154, no. 3. American Mathematical Society, pp. 927–942, 2026."
  ista: "Bradač D, Morawski P, Sudakov B, Wigderson Y. 2026. Ordered Ramsey numbers
    of graphs with \U0001D45A edges. Proceedings of the American Mathematical Society.
    154(3), 927–942."
  mla: "Bradač, Domagoj, et al. “Ordered Ramsey Numbers of Graphs with \U0001D45A
    Edges.” <i>Proceedings of the American Mathematical Society</i>, vol. 154, no.
    3, American Mathematical Society, 2026, pp. 927–42, doi:<a href=\"https://doi.org/10.1090/proc/17442\">10.1090/proc/17442</a>."
  short: D. Bradač, P. Morawski, B. Sudakov, Y. Wigderson, Proceedings of the American
    Mathematical Society 154 (2026) 927–942.
date_created: 2026-06-29T10:54:32Z
date_published: 2026-01-16T00:00:00Z
date_updated: 2026-07-14T08:34:43Z
day: '16'
doi: 10.1090/proc/17442
extern: '1'
external_id:
  arxiv:
  - '2412.17599'
intvolume: '       154'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2412.17599
month: '01'
oa: 1
oa_version: Preprint
page: 927-942
publication: Proceedings of the American Mathematical Society
publication_identifier:
  eissn:
  - 1088-6826
  issn:
  - 0002-9939
publication_status: published
publisher: American Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: "Ordered Ramsey numbers of graphs with \U0001D45A edges"
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 154
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '22183'
abstract:
- lang: eng
  text: "A partition of a (hyper)graph is ε-homogeneous if the edge densities between
    almost all clusters are\r\neither at most ε or at least 1 − ε. Suppose a 3-graph
    has the property that the link of every vertex has\r\nan ε-homogeneous partition
    of size poly(1/ε). Does this guarantee that the 3-graph also has a small\r\nhomogeneous
    partition? Terry and Wolf proved that such a 3-graph has an ε-homogeneous partition\r\nof
    size given by a wowzer-type function. Terry recently improved this to a double
    exponential bound,\r\nand conjectured that this bound is tight. Our first result
    in this paper disproves this conjecture by\r\ngiving an improved (single) exponential
    bound, which is best possible. We further obtain an analogous\r\nresult for k-graphs
    of all uniformities k  3. The above problem is part of a much broader programme,\r\nwhich
    seeks to understand the conditions under which a (hyper)graph has small ε-regular
    partitions.\r\nWhile this problem is fairly well understood for graphs, the situation
    is (as always) much more\r\ninvolved already for 3-graphs. For example, it is
    natural to ask if one can strengthen our first result\r\nby only requiring each
    link to have ε-regular partitions of size poly(1/ε). Our second result shows that\r\nsurprisingly
    the answer is “no”, namely, a 3-graph might only have regular partitions of tower-type
    size,\r\neven though the link of every vertex has an ε-regular partition of polynomial
    size."
article_number: rnag018
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. Is it easy to regularize a hypergraph
    with easy links? <i>International Mathematics Research Notices</i>. 2026;2026(4).
    doi:<a href="https://doi.org/10.1093/imrn/rnag018">10.1093/imrn/rnag018</a>
  apa: Gishboliner, L., Shapira, A., &#38; Wigderson, Y. (2026). Is it easy to regularize
    a hypergraph with easy links? <i>International Mathematics Research Notices</i>.
    Oxford University Press. <a href="https://doi.org/10.1093/imrn/rnag018">https://doi.org/10.1093/imrn/rnag018</a>
  chicago: Gishboliner, Lior, Asaf Shapira, and Yuval Wigderson. “Is It Easy to Regularize
    a Hypergraph with Easy Links?” <i>International Mathematics Research Notices</i>.
    Oxford University Press, 2026. <a href="https://doi.org/10.1093/imrn/rnag018">https://doi.org/10.1093/imrn/rnag018</a>.
  ieee: L. Gishboliner, A. Shapira, and Y. Wigderson, “Is it easy to regularize a
    hypergraph with easy links?,” <i>International Mathematics Research Notices</i>,
    vol. 2026, no. 4. Oxford University Press, 2026.
  ista: Gishboliner L, Shapira A, Wigderson Y. 2026. Is it easy to regularize a hypergraph
    with easy links? International Mathematics Research Notices. 2026(4), rnag018.
  mla: Gishboliner, Lior, et al. “Is It Easy to Regularize a Hypergraph with Easy
    Links?” <i>International Mathematics Research Notices</i>, vol. 2026, no. 4, rnag018,
    Oxford University Press, 2026, doi:<a href="https://doi.org/10.1093/imrn/rnag018">10.1093/imrn/rnag018</a>.
  short: L. Gishboliner, A. Shapira, Y. Wigderson, International Mathematics Research
    Notices 2026 (2026).
date_created: 2026-06-29T12:02:25Z
date_published: 2026-02-01T00:00:00Z
date_updated: 2026-07-14T09:25:22Z
day: '01'
doi: 10.1093/imrn/rnag018
extern: '1'
external_id:
  arxiv:
  - '2506.15582'
intvolume: '      2026'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2506.15582
month: '02'
oa: 1
oa_version: Preprint
publication: International Mathematics Research Notices
publication_identifier:
  eissn:
  - 1687-0247
  issn:
  - 1073-7928
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Is it easy to regularize a hypergraph with easy links?
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2026
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '22184'
abstract:
- lang: eng
  text: "Ramsey's theorem states that if N\r\n is sufficiently large, then no matter
    how one colors the edges among N\r\n vertices with two colors, there are always
    k\r\n vertices spanning edges in only one color. Given this theorem, it is natural
    to ask \"how large is sufficiently large?\" Ramsey's original proof showed that
    N=k!\r\n is sufficient, and five years later Erdős and Szekeres improved this
    bound to N=4^k\r\n. And then progress stalled for almost 90 years.\r\n\r\nIn this
    survey, I present the history of the problem, and discuss some of the ideas used
    in the recent breakthrough of Campos–Griffiths–Morris–Sahasrabudhe, who proved
    that N=3.993^k\r\n is sufficient. In addition, I discuss the subsequent work of
    Balister, Bollobás, Campos, Griffiths, Hurley, Morris, Sahasrabudhe, and Tiba,
    who gave an alternative, and more conceptual, proof."
- lang: fre
  text: "Le théorème de Ramsey stipule que si N\r\n est suffisamment grand, alors
    quelle que soit la manière dont l'on colore les arêtes entre N\r\n sommets avec
    deux couleurs, il y a toujours k\r\n sommets dont les arêtes ne sont colorées
    que d'une seule couleur. Compte tenu de ce théorème, il est naturel de se demander
    \"À quel point N\r\n doit être grand ?\" La preuve originale de Ramsey a montré
    que N=k!\r\n suffit, et cinq ans plus tard, Erdős et Szekeres ont amélioré cette
    borne à N=4k\r\n. Puis le progrès s'est arrêté pendant près de 90 ans.\r\n\r\nDans
    cet exposé, je présente l'histoire du problème et je discute certaines idées utilisées
    dans la percée récente de Campos--Griffiths-Morris--Sahasrabudhe, qui ont prouvé
    que N=3,993k\r\n suffit. De plus, je discute le travail suivant de Balister, Bollobás,
    Campos, Griffiths, Hurley, Morris, Sahasrabudhe, et Tiba, qui ont donné une preuve
    alternative et plus conceptuelle."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: 'Wigderson Y. Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers
    (after Campos, Griffiths, Morris, and Sahasrabudhe). <i>Astérisque</i>. 2026:85-138.
    doi:<a href="https://doi.org/10.24033/ast.1255">10.24033/ast.1255</a>'
  apa: 'Wigderson, Y. (2026). Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey
    numbers (after Campos, Griffiths, Morris, and Sahasrabudhe). <i>Astérisque</i>.
    Societe Mathematique de France. <a href="https://doi.org/10.24033/ast.1255">https://doi.org/10.24033/ast.1255</a>'
  chicago: 'Wigderson, Yuval. “Exposé Bourbaki 1230 : Upper Bounds on Diagonal Ramsey
    Numbers (after Campos, Griffiths, Morris, and Sahasrabudhe).” <i>Astérisque</i>.
    Societe Mathematique de France, 2026. <a href="https://doi.org/10.24033/ast.1255">https://doi.org/10.24033/ast.1255</a>.'
  ieee: 'Y. Wigderson, “Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers
    (after Campos, Griffiths, Morris, and Sahasrabudhe),” <i>Astérisque</i>. Societe
    Mathematique de France, pp. 85–138, 2026.'
  ista: 'Wigderson Y. 2026. Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey
    numbers (after Campos, Griffiths, Morris, and Sahasrabudhe). Astérisque., 85–138.'
  mla: 'Wigderson, Yuval. “Exposé Bourbaki 1230 : Upper Bounds on Diagonal Ramsey
    Numbers (after Campos, Griffiths, Morris, and Sahasrabudhe).” <i>Astérisque</i>,
    Societe Mathematique de France, 2026, pp. 85–138, doi:<a href="https://doi.org/10.24033/ast.1255">10.24033/ast.1255</a>.'
  short: Y. Wigderson, Astérisque (2026) 85–138.
date_created: 2026-06-29T12:02:59Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-07-14T09:53:07Z
day: '01'
doi: 10.24033/ast.1255
extern: '1'
external_id:
  arxiv:
  - '2411.09321'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: 'https://doi.org/10.48550/arXiv.2411.09321 '
mathsc:
- 05D10
- 05C55
month: '01'
oa: 1
oa_version: Preprint
page: 85-138
publication: Astérisque
publication_identifier:
  issn:
  - 0303-1179
  - 2492-5926
publication_status: published
publisher: Societe Mathematique de France
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Exposé Bourbaki 1230 : Upper bounds on diagonal Ramsey numbers (after Campos,
  Griffiths, Morris, and Sahasrabudhe)'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '22155'
abstract:
- lang: eng
  text: "The canonical Ramsey theorem of Erdős and Rado implies that for any graph
    \U0001D43B, any edge-coloring (with an arbitrary number of colors) of a sufficiently
    large complete graph \U0001D43E\U0001D441 contains a monochromatic, lexicographic,
    or rainbow copy of \U0001D43B. The least such \U0001D441 is called the Erdős–Rado
    number of \U0001D43B, denoted by \U0001D438⁢\U0001D445⁡(\U0001D43B). Erdős–Rado
    numbers of cliques have received considerable attention, and in this paper we
    extend this line of research by studying Erdős–Rado numbers of sparse graphs.
    For example, we prove that if \U0001D43B has bounded degree, then \U0001D438⁢\U0001D445⁡(\U0001D43B)
    is polynomial in |\U0001D449⁡(\U0001D43B)| if \U0001D43B is bipartite but exponential
    in general. We also study the closely related problem of constrained Ramsey numbers.
    For a given tree S and given path \U0001D443\U0001D461, we study the minimum \U0001D441
    such that every edge-coloring of \U0001D43E\U0001D441 contains a monochromatic
    copy of S or a rainbow copy of \U0001D443\U0001D461. We prove a nearly optimal
    upper bound for this problem, which differs from the best known lower bound by
    a function of inverse Ackermann type."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Lior
  full_name: Gishboliner, Lior
  last_name: Gishboliner
- first_name: Aleksa
  full_name: Milojević, Aleksa
  last_name: Milojević
- first_name: Benny
  full_name: Sudakov, Benny
  last_name: Sudakov
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Gishboliner L, Milojević A, Sudakov B, Wigderson Y. Canonical Ramsey numbers
    of sparse graphs. <i>SIAM Journal on Discrete Mathematics</i>. 2025;39(3):1491-1519.
    doi:<a href="https://doi.org/10.1137/24m1714964">10.1137/24m1714964</a>
  apa: Gishboliner, L., Milojević, A., Sudakov, B., &#38; Wigderson, Y. (2025). Canonical
    Ramsey numbers of sparse graphs. <i>SIAM Journal on Discrete Mathematics</i>.
    Society for Industrial &#38; Applied Mathematics. <a href="https://doi.org/10.1137/24m1714964">https://doi.org/10.1137/24m1714964</a>
  chicago: Gishboliner, Lior, Aleksa Milojević, Benny Sudakov, and Yuval Wigderson.
    “Canonical Ramsey Numbers of Sparse Graphs.” <i>SIAM Journal on Discrete Mathematics</i>.
    Society for Industrial &#38; Applied Mathematics, 2025. <a href="https://doi.org/10.1137/24m1714964">https://doi.org/10.1137/24m1714964</a>.
  ieee: L. Gishboliner, A. Milojević, B. Sudakov, and Y. Wigderson, “Canonical Ramsey
    numbers of sparse graphs,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 39,
    no. 3. Society for Industrial &#38; Applied Mathematics, pp. 1491–1519, 2025.
  ista: Gishboliner L, Milojević A, Sudakov B, Wigderson Y. 2025. Canonical Ramsey
    numbers of sparse graphs. SIAM Journal on Discrete Mathematics. 39(3), 1491–1519.
  mla: Gishboliner, Lior, et al. “Canonical Ramsey Numbers of Sparse Graphs.” <i>SIAM
    Journal on Discrete Mathematics</i>, vol. 39, no. 3, Society for Industrial &#38;
    Applied Mathematics, 2025, pp. 1491–519, doi:<a href="https://doi.org/10.1137/24m1714964">10.1137/24m1714964</a>.
  short: L. Gishboliner, A. Milojević, B. Sudakov, Y. Wigderson, SIAM Journal on Discrete
    Mathematics 39 (2025) 1491–1519.
date_created: 2026-06-29T10:49:48Z
date_published: 2025-09-01T00:00:00Z
date_updated: 2026-07-08T07:38:44Z
day: '01'
doi: 10.1137/24m1714964
extern: '1'
external_id:
  arxiv:
  - '2410.08644'
intvolume: '        39'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2410.08644
mathsc:
- 05D10
month: '09'
oa: 1
oa_version: Preprint
page: 1491-1519
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
  eissn:
  - 1095-7146
  issn:
  - 0895-4801
publication_status: published
publisher: Society for Industrial & Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Canonical Ramsey numbers of sparse graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 39
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '22157'
abstract:
- lang: eng
  text: "A graph \U0001D43A is said to be Ramsey for a tuple of graphs(\U0001D43B
    1 , … , \U0001D43B\U0001D45F ) if every \U0001D45F-coloring of the edges of \U0001D43A
    con-tains a monochromatic copy of \U0001D43B\U0001D456 in color \U0001D456, for
    some \U0001D456.A fundamental question at the intersection of Ramseytheory and
    the theory of random graphs is to deter-mine the threshold at which the binomial
    randomgraph \U0001D43A\U0001D45B,\U0001D45D becomes asymptotically almost surely
    Ram-sey for a fixed tuple (\U0001D43B 1 , … , \U0001D43B\U0001D45F ), and a famous
    conjectureof Kohayakawa and Kreuter predicts this threshold.Earlier work of Mousset–Nenadov–Samotij,
    Bowtell–Hancock–Hyde, and Kuperwasser–Samotij–Wigdersonhas reduced this probabilistic
    problem to a determinis-tic graph decomposition conjecture. In this paper, weresolve
    this deterministic problem, thus proving theKohayakawa–Kreuter conjecture. Along
    the way, weprove a number of novel graph decomposition resultsthat may be of independent
    interest."
article_number: e70013
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Micha
  full_name: Christoph, Micha
  last_name: Christoph
- first_name: Anders
  full_name: Martinsson, Anders
  last_name: Martinsson
- first_name: Raphael
  full_name: Steiner, Raphael
  last_name: Steiner
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Christoph M, Martinsson A, Steiner R, Wigderson Y. Resolution of the Kohayakawa–Kreuter
    conjecture. <i>Proceedings of the London Mathematical Society</i>. 2025;130(1).
    doi:<a href="https://doi.org/10.1112/plms.70013">10.1112/plms.70013</a>
  apa: Christoph, M., Martinsson, A., Steiner, R., &#38; Wigderson, Y. (2025). Resolution
    of the Kohayakawa–Kreuter conjecture. <i>Proceedings of the London Mathematical
    Society</i>. Wiley. <a href="https://doi.org/10.1112/plms.70013">https://doi.org/10.1112/plms.70013</a>
  chicago: Christoph, Micha, Anders Martinsson, Raphael Steiner, and Yuval Wigderson.
    “Resolution of the Kohayakawa–Kreuter Conjecture.” <i>Proceedings of the London
    Mathematical Society</i>. Wiley, 2025. <a href="https://doi.org/10.1112/plms.70013">https://doi.org/10.1112/plms.70013</a>.
  ieee: M. Christoph, A. Martinsson, R. Steiner, and Y. Wigderson, “Resolution of
    the Kohayakawa–Kreuter conjecture,” <i>Proceedings of the London Mathematical
    Society</i>, vol. 130, no. 1. Wiley, 2025.
  ista: Christoph M, Martinsson A, Steiner R, Wigderson Y. 2025. Resolution of the
    Kohayakawa–Kreuter conjecture. Proceedings of the London Mathematical Society.
    130(1), e70013.
  mla: Christoph, Micha, et al. “Resolution of the Kohayakawa–Kreuter Conjecture.”
    <i>Proceedings of the London Mathematical Society</i>, vol. 130, no. 1, e70013,
    Wiley, 2025, doi:<a href="https://doi.org/10.1112/plms.70013">10.1112/plms.70013</a>.
  short: M. Christoph, A. Martinsson, R. Steiner, Y. Wigderson, Proceedings of the
    London Mathematical Society 130 (2025).
date_created: 2026-06-29T10:50:35Z
date_published: 2025-01-01T00:00:00Z
date_updated: 2026-07-08T10:24:21Z
day: '01'
ddc:
- '500'
doi: 10.1112/plms.70013
extern: '1'
external_id:
  arxiv:
  - '2402.03045'
intvolume: '       130'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2402.03045
mathsc:
- 05C70
- 05D10
- 05C80
month: '01'
oa: 1
oa_version: Preprint
publication: Proceedings of the London Mathematical Society
publication_identifier:
  eissn:
  - 1460-244X
  issn:
  - 0024-6115
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Resolution of the Kohayakawa–Kreuter conjecture
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 130
year: '2025'
...
---
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: '22163'
abstract:
- lang: eng
  text: "For a field F and integers d and k, a set A ⊆ Fd is called k-nearly orthogonal
    if its\r\nmembers are non-self-orthogonal and every k + 1 vectors of A include
    an orthogonal pair.\r\nWe prove that for every prime p there exists some δ = δ(p)>
    0, such that for every field\r\nF of characteristic p and for all integers k ≥
    2 and d ≥ k, there exists a k-nearly orthogonal\r\nset of at least dδ·k/ logk
    vectors of Fd. The size of the set is optimal up to the logk term\r\nin the exponent.
    We further prove two extensions of this result. In the first, we provide a\r\nlarge
    set A of non-self-orthogonal vectors of Fd such that for every two subsets of
    A of\r\nsize k+1 each, some vector of one of the subsets is orthogonal to some
    vector of the other.\r\nIn the second extension, every k + 1 vectors of the produced
    set A include ℓ + 1 pairwise\r\northogonal vectors for an arbitrary fixed integer
    1 ≤ ℓ ≤ k. The proofs involve probabilistic\r\nand spectral arguments and the
    hypergraph container method"
article_number: '114373'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Ishay
  full_name: Haviv, Ishay
  last_name: Haviv
- first_name: Sam
  full_name: Mattheus, Sam
  last_name: Mattheus
- first_name: Aleksa
  full_name: Milojević, Aleksa
  last_name: Milojević
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Haviv I, Mattheus S, Milojević A, Wigderson Y. Larger nearly orthogonal sets
    over finite fields. <i>Discrete Mathematics</i>. 2025;348(4). doi:<a href="https://doi.org/10.1016/j.disc.2024.114373">10.1016/j.disc.2024.114373</a>
  apa: Haviv, I., Mattheus, S., Milojević, A., &#38; Wigderson, Y. (2025). Larger
    nearly orthogonal sets over finite fields. <i>Discrete Mathematics</i>. Elsevier.
    <a href="https://doi.org/10.1016/j.disc.2024.114373">https://doi.org/10.1016/j.disc.2024.114373</a>
  chicago: Haviv, Ishay, Sam Mattheus, Aleksa Milojević, and Yuval Wigderson. “Larger
    Nearly Orthogonal Sets over Finite Fields.” <i>Discrete Mathematics</i>. Elsevier,
    2025. <a href="https://doi.org/10.1016/j.disc.2024.114373">https://doi.org/10.1016/j.disc.2024.114373</a>.
  ieee: I. Haviv, S. Mattheus, A. Milojević, and Y. Wigderson, “Larger nearly orthogonal
    sets over finite fields,” <i>Discrete Mathematics</i>, vol. 348, no. 4. Elsevier,
    2025.
  ista: Haviv I, Mattheus S, Milojević A, Wigderson Y. 2025. Larger nearly orthogonal
    sets over finite fields. Discrete Mathematics. 348(4), 114373.
  mla: Haviv, Ishay, et al. “Larger Nearly Orthogonal Sets over Finite Fields.” <i>Discrete
    Mathematics</i>, vol. 348, no. 4, 114373, Elsevier, 2025, doi:<a href="https://doi.org/10.1016/j.disc.2024.114373">10.1016/j.disc.2024.114373</a>.
  short: I. Haviv, S. Mattheus, A. Milojević, Y. Wigderson, Discrete Mathematics 348
    (2025).
das_tickbox: '1'
date_created: 2026-06-29T10:53:05Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2026-07-14T08:17:17Z
day: '01'
doi: 10.1016/j.disc.2024.114373
extern: '1'
external_id:
  arxiv:
  - '2404.01057'
intvolume: '       348'
issue: '4'
keyword:
- Nearly orthogonal sets
- Ramsey theory
- Finite fields
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: 'https://doi.org/10.48550/arXiv.2404.01057 '
month: '04'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
  issn:
  - 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Larger nearly orthogonal sets over finite fields
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 348
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '22168'
abstract:
- lang: eng
  text: "Let us say that a graph G is Ramsey for a tuple (H1, ... , Hr) of graphs
    if every r-colouring\r\nof the edges of G contains a monochromatic copy of Hi
    in colour i, for some i ∈ [[r]].\r\nA famous conjecture of Kohayakawa and Kreuter,
    extending seminal work of Rödl and\r\nRucinski, predicts the threshold at which
    the binomial random graph ´ Gn,p becomes Ramsey\r\nfor (H1, ... , Hr) asymptotically
    almost surely.\r\nIn this paper, we resolve the Kohayakawa–Kreuter conjecture
    for almost all tuples of\r\ngraphs. Moreover, we reduce its validity to the truth
    of a certain deterministic statement,\r\nwhich is a clear necessary condition
    for the conjecture to hold. All of our results actually hold in greater generality,
    when one replaces the graphs H1, ... , Hr by finite families\r\nH1, ... , Hr.
    Additionally, we pose a natural (deterministic) graph-partitioning conjecture,\r\nwhich
    we believe to be of independent interest, and whose resolution would imply the\r\nKohayakawa–Kreuter
    conjecture."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: EDEN
  full_name: KUPERWASSER, EDEN
  last_name: KUPERWASSER
- first_name: WOJCIECH
  full_name: SAMOTIJ, WOJCIECH
  last_name: SAMOTIJ
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: KUPERWASSER E, SAMOTIJ W, Wigderson Y. On the Kohayakawa–Kreuter conjecture.
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>. 2025;178(3):293-320.
    doi:<a href="https://doi.org/10.1017/s0305004125000143">10.1017/s0305004125000143</a>
  apa: KUPERWASSER, E., SAMOTIJ, W., &#38; Wigderson, Y. (2025). On the Kohayakawa–Kreuter
    conjecture. <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>.
    Cambridge University Press. <a href="https://doi.org/10.1017/s0305004125000143">https://doi.org/10.1017/s0305004125000143</a>
  chicago: KUPERWASSER, EDEN, WOJCIECH SAMOTIJ, and Yuval Wigderson. “On the Kohayakawa–Kreuter
    Conjecture.” <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>.
    Cambridge University Press, 2025. <a href="https://doi.org/10.1017/s0305004125000143">https://doi.org/10.1017/s0305004125000143</a>.
  ieee: E. KUPERWASSER, W. SAMOTIJ, and Y. Wigderson, “On the Kohayakawa–Kreuter conjecture,”
    <i>Mathematical Proceedings of the Cambridge Philosophical Society</i>, vol. 178,
    no. 3. Cambridge University Press, pp. 293–320, 2025.
  ista: KUPERWASSER E, SAMOTIJ W, Wigderson Y. 2025. On the Kohayakawa–Kreuter conjecture.
    Mathematical Proceedings of the Cambridge Philosophical Society. 178(3), 293–320.
  mla: KUPERWASSER, EDEN, et al. “On the Kohayakawa–Kreuter Conjecture.” <i>Mathematical
    Proceedings of the Cambridge Philosophical Society</i>, vol. 178, no. 3, Cambridge
    University Press, 2025, pp. 293–320, doi:<a href="https://doi.org/10.1017/s0305004125000143">10.1017/s0305004125000143</a>.
  short: E. KUPERWASSER, W. SAMOTIJ, Y. Wigderson, Mathematical Proceedings of the
    Cambridge Philosophical Society 178 (2025) 293–320.
date_created: 2026-06-29T10:55:00Z
date_published: 2025-04-28T00:00:00Z
date_updated: 2026-07-14T08:38:08Z
day: '28'
doi: 10.1017/s0305004125000143
extern: '1'
external_id:
  arxiv:
  - '2307.16611'
intvolume: '       178'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2307.16611
mathsc:
- 05C80
- 05C55
- 05D10
month: '04'
oa: 1
oa_version: Preprint
page: 293-320
publication: Mathematical Proceedings of the Cambridge Philosophical Society
publication_identifier:
  eissn:
  - 1469-8064
  issn:
  - 0305-0041
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the Kohayakawa–Kreuter conjecture
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 178
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '22172'
abstract:
- lang: eng
  text: "A highly influential result of Nikiforov states that if an n-vertex graph
    G contains\r\nat least γnh copies of a fixed h-vertex graph H, then G contains
    a blowup of H of order\r\nΩγ,H(logn). While the dependence on n is optimal, the
    correct dependence on γ is unknown;\r\nall known proofs yield bounds that are
    polynomial in γ, but the best known upper bound,\r\ncoming from random graphs,
    is only logarithmic in γ. It is a major open problem to narrow\r\nthis gap.\r\nWe
    prove that if H is triangle-free, then the logarithmic behavior of the upper bound\r\nis
    the truth. That is, under the assumptions above, G contains a blowup of H of order\r\nΩH(logn/log(1/γ)).
    This is the first non-trivial instance where the optimal dependence in\r\nNikiforov’s
    theorem is known.\r\nAs a consequence, we also prove an upper bound on multicolor
    Ramsey numbers of\r\nblowups of triangle-free graphs, proving that the dependence
    on the number of colors is\r\npolynomial once the blowup is sufficiently large.
    This shows that, from the perspective\r\nof multicolor Ramsey numbers, blowups
    of fixed triangle-free graphs behave like bipartite\r\ngraphs."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: António
  full_name: Girão, António
  last_name: Girão
- first_name: Zach
  full_name: Hunter, Zach
  last_name: Hunter
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Girão A, Hunter Z, Wigderson Y. Blowups of triangle-free graphs. <i>Advances
    in Combinatorics</i>. 2025;10. doi:<a href="https://doi.org/10.19086/aic.2025.10">10.19086/aic.2025.10</a>
  apa: Girão, A., Hunter, Z., &#38; Wigderson, Y. (2025). Blowups of triangle-free
    graphs. <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals.
    <a href="https://doi.org/10.19086/aic.2025.10">https://doi.org/10.19086/aic.2025.10</a>
  chicago: Girão, António, Zach Hunter, and Yuval Wigderson. “Blowups of Triangle-Free
    Graphs.” <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals,
    2025. <a href="https://doi.org/10.19086/aic.2025.10">https://doi.org/10.19086/aic.2025.10</a>.
  ieee: A. Girão, Z. Hunter, and Y. Wigderson, “Blowups of triangle-free graphs,”
    <i>Advances in Combinatorics</i>, vol. 10. Alliance of Diamond Open Access Journals,
    2025.
  ista: Girão A, Hunter Z, Wigderson Y. 2025. Blowups of triangle-free graphs. Advances
    in Combinatorics. 10.
  mla: Girão, António, et al. “Blowups of Triangle-Free Graphs.” <i>Advances in Combinatorics</i>,
    vol. 10, Alliance of Diamond Open Access Journals, 2025, doi:<a href="https://doi.org/10.19086/aic.2025.10">10.19086/aic.2025.10</a>.
  short: A. Girão, Z. Hunter, Y. Wigderson, Advances in Combinatorics 10 (2025).
date_created: 2026-06-29T10:56:44Z
date_published: 2025-12-19T00:00:00Z
date_updated: 2026-07-14T08:50:55Z
day: '19'
doi: 10.19086/aic.2025.10
extern: '1'
external_id:
  arxiv:
  - '2408.12913'
intvolume: '        10'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2408.12913
month: '12'
oa: 1
oa_version: Preprint
publication: Advances in Combinatorics
publication_status: published
publisher: Alliance of Diamond Open Access Journals
quality_controlled: '1'
scopus_import: '1'
status: public
title: Blowups of triangle-free graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '22181'
abstract:
- lang: eng
  text: "A graph G is said to be Ramsey size-linear if r(G, H) = OG(e(H))\r\nfor every
    graph H with no isolated vertices. Erdős, Faudree,\r\nRousseau, and Schelp observed
    that K4 is not Ramsey size-linear,\r\nbut each of its proper subgraphs is, and
    they asked whether there\r\nexist infinitely many such graphs. In this short note,
    we answer\r\nthis question in the affirmative"
article_number: '104175'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Wigderson Y. Infinitely many minimally non-Ramsey size-linear graphs. <i>European
    Journal of Combinatorics</i>. 2025;128. doi:<a href="https://doi.org/10.1016/j.ejc.2025.104175">10.1016/j.ejc.2025.104175</a>
  apa: Wigderson, Y. (2025). Infinitely many minimally non-Ramsey size-linear graphs.
    <i>European Journal of Combinatorics</i>. Elsevier. <a href="https://doi.org/10.1016/j.ejc.2025.104175">https://doi.org/10.1016/j.ejc.2025.104175</a>
  chicago: Wigderson, Yuval. “Infinitely Many Minimally Non-Ramsey Size-Linear Graphs.”
    <i>European Journal of Combinatorics</i>. Elsevier, 2025. <a href="https://doi.org/10.1016/j.ejc.2025.104175">https://doi.org/10.1016/j.ejc.2025.104175</a>.
  ieee: Y. Wigderson, “Infinitely many minimally non-Ramsey size-linear graphs,” <i>European
    Journal of Combinatorics</i>, vol. 128. Elsevier, 2025.
  ista: Wigderson Y. 2025. Infinitely many minimally non-Ramsey size-linear graphs.
    European Journal of Combinatorics. 128, 104175.
  mla: Wigderson, Yuval. “Infinitely Many Minimally Non-Ramsey Size-Linear Graphs.”
    <i>European Journal of Combinatorics</i>, vol. 128, 104175, Elsevier, 2025, doi:<a
    href="https://doi.org/10.1016/j.ejc.2025.104175">10.1016/j.ejc.2025.104175</a>.
  short: Y. Wigderson, European Journal of Combinatorics 128 (2025).
date_created: 2026-06-29T10:59:47Z
date_published: 2025-08-01T00:00:00Z
date_updated: 2026-07-14T09:13:09Z
day: '01'
doi: 10.1016/j.ejc.2025.104175
extern: '1'
external_id:
  arxiv:
  - '2409.05931'
intvolume: '       128'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: 'https://doi.org/10.48550/arXiv.2409.05931 '
month: '08'
oa: 1
oa_version: Preprint
publication: European Journal of Combinatorics
publication_identifier:
  issn:
  - 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Infinitely many minimally non-Ramsey size-linear graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 128
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '22188'
abstract:
- lang: eng
  text: "A fundamental fact about bounded-degree graph expanders is that three notions
    of expansion—vertex expansion, edge expansion, and spectral expansion—are all
    equivalent. In this paper, we study to what extent such a statement is true for
    linear-algebraic notions of expansion.\r\n\r\nThere are two well-studied notions
    of linear-algebraic expansion, namely, dimension expansion (defined in analogy
    to vertex expansion of graphs) and quantum expansion (defined in analogy to spectral
    expansion of graphs). Lubotzky and Zelmanov proved that the latter implies the
    former. We prove that the converse is false: There are dimension expanders which
    are not quantum expanders. This also answers in the negative questions of Lubotzky--Zelmanov
    and Dvir--Shpilka on the relation between dimension expansion and Kazhdan's property
    T.\r\n\r\nMoreover, this asymmetry is explained by the fact that there are two
    distinct linear-algebraic analogues of edge expansion of graphs. The first of
    these is quantum edge expansion, which was introduced by Hastings, and which he
    proved to be equivalent to quantum expansion. We introduce a new notion, termed
    dimension edge expansion, which we prove is equivalent to dimension expansion
    and which is implied by quantum edge expansion. Thus, the separation above is
    implied by a finer one: dimension edge expansion is strictly weaker than quantum
    edge expansion. This new notion also leads to a new, more modular proof of the
    Lubotzky--Zelmanov result that quantum expanders are dimension expanders."
article_number: '1'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yinan
  full_name: Li, Yinan
  last_name: Li
- first_name: Youming
  full_name: Qiao, Youming
  last_name: Qiao
- first_name: Avi
  full_name: Wigderson, Avi
  last_name: Wigderson
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
- first_name: Chuanqi
  full_name: Zhang, Chuanqi
  last_name: Zhang
citation:
  ama: Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. On linear-algebraic notions
    of expansion. <i>Theory of Computing</i>. 2025;21. doi:<a href="https://doi.org/10.4086/toc.2025.v021a001">10.4086/toc.2025.v021a001</a>
  apa: Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., &#38; Zhang, C. (2025). On
    linear-algebraic notions of expansion. <i>Theory of Computing</i>. Theory of Computing
    Exchange. <a href="https://doi.org/10.4086/toc.2025.v021a001">https://doi.org/10.4086/toc.2025.v021a001</a>
  chicago: Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang.
    “On Linear-Algebraic Notions of Expansion.” <i>Theory of Computing</i>. Theory
    of Computing Exchange, 2025. <a href="https://doi.org/10.4086/toc.2025.v021a001">https://doi.org/10.4086/toc.2025.v021a001</a>.
  ieee: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “On linear-algebraic
    notions of expansion,” <i>Theory of Computing</i>, vol. 21. Theory of Computing
    Exchange, 2025.
  ista: Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. 2025. On linear-algebraic
    notions of expansion. Theory of Computing. 21, 1.
  mla: Li, Yinan, et al. “On Linear-Algebraic Notions of Expansion.” <i>Theory of
    Computing</i>, vol. 21, 1, Theory of Computing Exchange, 2025, doi:<a href="https://doi.org/10.4086/toc.2025.v021a001">10.4086/toc.2025.v021a001</a>.
  short: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, C. Zhang, Theory of Computing
    21 (2025).
date_created: 2026-06-29T12:14:06Z
date_published: 2025-04-12T00:00:00Z
date_updated: 2026-07-14T09:47:56Z
day: '12'
doi: 10.4086/toc.2025.v021a001
extern: '1'
external_id:
  arxiv:
  - '2212.13154'
intvolume: '        21'
keyword:
- linear algebraic expansion
- quantum expanders
- dimension expanders
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2212.13154
mathsc:
- 05C18
- 68R10
month: '04'
oa: 1
oa_version: Preprint
publication: Theory of Computing
publication_identifier:
  issn:
  - 1557-2862
publication_status: published
publisher: Theory of Computing Exchange
quality_controlled: '1'
scopus_import: '1'
status: public
title: On linear-algebraic notions of expansion
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 21
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '22154'
abstract:
- lang: eng
  text: 'The inertia bound and ratio bound (also known as the Cvetković bound and
    Hoffman bound) are two fundamental inequalities in spectral graph theory, giving
    upper bounds on the independence number a(G) of a graph G in terms of spectral
    information about a weighted adjacency matrix of G. For both inequalities, given
    a graph G, one needs to make a judicious choice of weighted adjacency matrix to
    obtain as strong a bound as possible. While there is a well‐established theory
    surrounding the ratio bound, the inertia bound is much more mysterious, and its
    limits are rather unclear. In fact, only recently did Sinkovic find the first
    example of a graph for which the inertia bound is not tight (for any weighted
    adjacency matrix), answering a longstanding question of Godsil. We show that the
    inertia bound can be extremely far from tight, and in fact can significantly underperform
    the ratio bound: for example, one of our results is that for infinitely many n,
    there is an n‐vertex graph for which even the unweighted ratio bound can prove
    a(G)<4n^3/4, but the inertia bound is always at least n/4. In particular, these
    results address questions of Rooney, Sinkovic, and Wocjan–Elphick–Abiad.'
acknowledgement: Open access funding provided by Eidgenossische Technische Hochschule
  Zurich.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Matthew
  full_name: Kwan, Matthew
  last_name: Kwan
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Kwan M, Wigderson Y. The inertia bound is far from tight. <i>Bulletin of the
    London Mathematical Society</i>. 2024;56(10):3196-3208. doi:<a href="https://doi.org/10.1112/blms.13127">10.1112/blms.13127</a>
  apa: Kwan, M., &#38; Wigderson, Y. (2024). The inertia bound is far from tight.
    <i>Bulletin of the London Mathematical Society</i>. Wiley. <a href="https://doi.org/10.1112/blms.13127">https://doi.org/10.1112/blms.13127</a>
  chicago: Kwan, Matthew, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.”
    <i>Bulletin of the London Mathematical Society</i>. Wiley, 2024. <a href="https://doi.org/10.1112/blms.13127">https://doi.org/10.1112/blms.13127</a>.
  ieee: M. Kwan and Y. Wigderson, “The inertia bound is far from tight,” <i>Bulletin
    of the London Mathematical Society</i>, vol. 56, no. 10. Wiley, pp. 3196–3208,
    2024.
  ista: Kwan M, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin of
    the London Mathematical Society. 56(10), 3196–3208.
  mla: Kwan, Matthew, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.”
    <i>Bulletin of the London Mathematical Society</i>, vol. 56, no. 10, Wiley, 2024,
    pp. 3196–208, doi:<a href="https://doi.org/10.1112/blms.13127">10.1112/blms.13127</a>.
  short: M. Kwan, Y. Wigderson, Bulletin of the London Mathematical Society 56 (2024)
    3196–3208.
date_created: 2026-06-29T10:49:18Z
date_published: 2024-10-01T00:00:00Z
date_updated: 2026-07-08T07:34:36Z
day: '01'
ddc:
- '500'
doi: 10.1112/blms.13127
extern: '1'
external_id:
  arxiv:
  - '2312.04925'
intvolume: '        56'
issue: '10'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1112/blms.13127
month: '10'
oa: 1
oa_version: Published Version
page: 3196-3208
publication: Bulletin of the London Mathematical Society
publication_identifier:
  eissn:
  - 1469-2120
  issn:
  - 0024-6093
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: The inertia bound is far from tight
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 56
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '22179'
abstract:
- lang: eng
  text: "Burr and Erd˝os in 1975 conjectured, and Chv´atal, R¨odl, Szemer´edi and\r\nTrotter
    later proved, that the Ramsey number of any bounded degree\r\ngraph is linear
    in the number of vertices. In this paper, we disprove\r\nthe natural directed
    analogue of the Burr–Erd˝os conjecture, answering a\r\nquestion of Buci´c, Letzter,
    and Sudakov. If H is an acyclic digraph, the\r\noriented Ramsey number of H, denoted
    −→r1(H), is the least N such that\r\nevery tournament on N vertices contains a
    copy of H. We show that for\r\nany Δ ≥ 2 and any sufficiently large n, there exists
    an acyclic digraph H\r\nwith n vertices and maximum degree Δ such that\r\n−→r1(H)
    ≥ nΩ(Δ2/3/ log5/3 Δ).\r\nThis proves that −→r1(H) is not always linear in the
    number of vertices for\r\nbounded-degree H. On the other hand, we show that −→r1(H)
    is nearly linear\r\nin the number of vertices for typical bounded-degree acyclic
    digraphs H,\r\nand obtain linear or nearly linear bounds for several natural families
    of\r\nbounded-degree acyclic digraphs.\r\nFor multiple colors, we prove a quasi-polynomial
    upper bound −→rk(H)=\r\n2(log n)Ok(1) for all bounded-degree acyclic digraphs
    H on n vertices, where −→rk(H) is the least N such that every k-edge-colored tournament
    on N\r\nvertices contains a monochromatic copy of H. For k ≥ 2 and n ≥ 4, we\r\nexhibit
    an acyclic digraph H with n vertices and maximum degree 3 such\r\nthat −→rk(H)
    ≥ nΩ(log n/ log log n), showing that these Ramsey numbers can\r\ngrow faster than
    any polynomial in the number of vertices."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, He X, Wigderson Y. Ramsey numbers of sparse digraphs. <i>Israel Journal
    of Mathematics</i>. 2024;263(1):1-48. doi:<a href="https://doi.org/10.1007/s11856-024-2624-y">10.1007/s11856-024-2624-y</a>
  apa: Fox, J., He, X., &#38; Wigderson, Y. (2024). Ramsey numbers of sparse digraphs.
    <i>Israel Journal of Mathematics</i>. Springer Nature. <a href="https://doi.org/10.1007/s11856-024-2624-y">https://doi.org/10.1007/s11856-024-2624-y</a>
  chicago: Fox, Jacob, Xiaoyu He, and Yuval Wigderson. “Ramsey Numbers of Sparse Digraphs.”
    <i>Israel Journal of Mathematics</i>. Springer Nature, 2024. <a href="https://doi.org/10.1007/s11856-024-2624-y">https://doi.org/10.1007/s11856-024-2624-y</a>.
  ieee: J. Fox, X. He, and Y. Wigderson, “Ramsey numbers of sparse digraphs,” <i>Israel
    Journal of Mathematics</i>, vol. 263, no. 1. Springer Nature, pp. 1–48, 2024.
  ista: Fox J, He X, Wigderson Y. 2024. Ramsey numbers of sparse digraphs. Israel
    Journal of Mathematics. 263(1), 1–48.
  mla: Fox, Jacob, et al. “Ramsey Numbers of Sparse Digraphs.” <i>Israel Journal of
    Mathematics</i>, vol. 263, no. 1, Springer Nature, 2024, pp. 1–48, doi:<a href="https://doi.org/10.1007/s11856-024-2624-y">10.1007/s11856-024-2624-y</a>.
  short: J. Fox, X. He, Y. Wigderson, Israel Journal of Mathematics 263 (2024) 1–48.
date_created: 2026-06-29T10:59:02Z
date_published: 2024-10-01T00:00:00Z
date_updated: 2026-07-14T09:08:32Z
day: '01'
doi: 10.1007/s11856-024-2624-y
extern: '1'
external_id:
  arxiv:
  - '2105.02383'
intvolume: '       263'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2105.02383
month: '10'
oa: 1
oa_version: Preprint
page: 1-48
publication: Israel Journal of Mathematics
publication_identifier:
  eissn:
  - 1565-8511
  issn:
  - 0021-2172
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ramsey numbers of sparse digraphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 263
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '22180'
abstract:
- lang: eng
  text: Given a graph , its Ramsey number  is the minimum  so that every two‐coloring
    of  contains a monochromatic copy of . It was conjectured by Conlon, Fox, and
    Sudakov that if one deletes a single vertex from , the Ramsey number can change
    by at most a constant factor. We disprove this conjecture, exhibiting an infinite
    family of graphs such that deleting a single vertex from each decreases the Ramsey
    number by a super‐constant factor. One consequence of this result is the following.
    There exists a family of graphs  so that in any Ramsey coloring for  (i.e., a
    coloring of a clique on  vertices with no monochromatic copy of ), one of the
    color classes has density .
article_processing_charge: No
article_type: original
author:
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Wigderson Y. Ramsey numbers upon vertex deletion. <i>Journal of Graph Theory</i>.
    2024;106(3):663-675. doi:<a href="https://doi.org/10.1002/jgt.23093">10.1002/jgt.23093</a>
  apa: Wigderson, Y. (2024). Ramsey numbers upon vertex deletion. <i>Journal of Graph
    Theory</i>. Wiley. <a href="https://doi.org/10.1002/jgt.23093">https://doi.org/10.1002/jgt.23093</a>
  chicago: Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” <i>Journal of
    Graph Theory</i>. Wiley, 2024. <a href="https://doi.org/10.1002/jgt.23093">https://doi.org/10.1002/jgt.23093</a>.
  ieee: Y. Wigderson, “Ramsey numbers upon vertex deletion,” <i>Journal of Graph Theory</i>,
    vol. 106, no. 3. Wiley, pp. 663–675, 2024.
  ista: Wigderson Y. 2024. Ramsey numbers upon vertex deletion. Journal of Graph Theory.
    106(3), 663–675.
  mla: Wigderson, Yuval. “Ramsey Numbers upon Vertex Deletion.” <i>Journal of Graph
    Theory</i>, vol. 106, no. 3, Wiley, 2024, pp. 663–75, doi:<a href="https://doi.org/10.1002/jgt.23093">10.1002/jgt.23093</a>.
  short: Y. Wigderson, Journal of Graph Theory 106 (2024) 663–675.
date_created: 2026-06-29T10:59:24Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2026-07-14T09:10:28Z
day: '01'
doi: 10.1002/jgt.23093
extern: '1'
external_id:
  unknown:
  - '2208.11181'
intvolume: '       106'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2208.11181
month: '07'
oa: 1
oa_version: Preprint
page: 663-675
publication: Journal of Graph Theory
publication_identifier:
  eissn:
  - 1097-0118
  issn:
  - 0364-9024
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ramsey numbers upon vertex deletion
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 106
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '22162'
abstract:
- lang: eng
  text: "Given a bipartite graph G, the graphical matrix space SG consists of\r\nmatrices
    whose non-zero entries can only be at those positions corresponding to edges in
    G. Tutte (J. London Math. Soc., 1947), Edmonds\r\n(J. Res. Nat. Bur. Standards
    Sect. B, 1967) and Lov´asz (FCT, 1979) observed connections between perfect matchings
    in G and full-rank matrices\r\nin SG. Dieudonn´e (Arch. Math., 1948) proved a
    tight upper bound on\r\nthe dimensions of those matrix spaces containing only
    singular matrices.\r\nThe starting point of this paper is a simultaneous generalization
    of these\r\ntwo classical results: we show that the largest dimension over subspaces\r\nof
    SG containing only singular matrices is equal to the maximum size over\r\nsubgraphs
    of G without perfect matchings, based on Meshulam’s proof of\r\nDieudonn´e’s result
    (Quart. J. Math., 1985).\r\nStarting from this result, we go on to establish more
    connections\r\nbetween properties of graphs and matrix spaces. For example, we\r\nestablish
    connections between acyclicity and nilpotency, between strong\r\nconnectivity
    and irreducibility, and between isomorphism and\r\nconjugacy/congruence. For each
    connection, we study three types of correspondences, namely the basic correspondence,
    the inherited correspondence (for subgraphs and subspaces), and the induced correspondence\r\n(for
    induced subgraphs and restrictions). Some correspondences lead to\r\nintriguing
    generalizations of classical results, such as Dieudonn´e’s result\r\nmentioned
    above, and a celebrated theorem of Gerstenhaber regarding the\r\nlargest dimension
    of nil matrix spaces (Amer. J. Math., 1958).\r\nFinally, we show some implications
    of our results to quantum information and present open problems in computational
    complexity motivated\r\nby these results."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yinan
  full_name: Li, Yinan
  last_name: Li
- first_name: Youming
  full_name: Qiao, Youming
  last_name: Qiao
- first_name: Avi
  full_name: Wigderson, Avi
  last_name: Wigderson
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
- first_name: Chuanqi
  full_name: Zhang, Chuanqi
  last_name: Zhang
citation:
  ama: Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. Connections between graphs
    and matrix spaces. <i>Israel Journal of Mathematics</i>. 2023;256(2):513-580.
    doi:<a href="https://doi.org/10.1007/s11856-023-2515-7">10.1007/s11856-023-2515-7</a>
  apa: Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., &#38; Zhang, C. (2023). Connections
    between graphs and matrix spaces. <i>Israel Journal of Mathematics</i>. Springer
    Nature. <a href="https://doi.org/10.1007/s11856-023-2515-7">https://doi.org/10.1007/s11856-023-2515-7</a>
  chicago: Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang.
    “Connections between Graphs and Matrix Spaces.” <i>Israel Journal of Mathematics</i>.
    Springer Nature, 2023. <a href="https://doi.org/10.1007/s11856-023-2515-7">https://doi.org/10.1007/s11856-023-2515-7</a>.
  ieee: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “Connections between
    graphs and matrix spaces,” <i>Israel Journal of Mathematics</i>, vol. 256, no.
    2. Springer Nature, pp. 513–580, 2023.
  ista: Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. 2023. Connections between
    graphs and matrix spaces. Israel Journal of Mathematics. 256(2), 513–580.
  mla: Li, Yinan, et al. “Connections between Graphs and Matrix Spaces.” <i>Israel
    Journal of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 513–80,
    doi:<a href="https://doi.org/10.1007/s11856-023-2515-7">10.1007/s11856-023-2515-7</a>.
  short: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, C. Zhang, Israel Journal of Mathematics
    256 (2023) 513–580.
date_created: 2026-06-29T10:52:37Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2026-07-08T10:44:50Z
day: '01'
doi: 10.1007/s11856-023-2515-7
extern: '1'
external_id:
  arxiv:
  - '2206.04815'
intvolume: '       256'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2206.04815
month: '09'
oa: 1
oa_version: Preprint
page: 513-580
publication: Israel Journal of Mathematics
publication_identifier:
  eissn:
  - 1565-8511
  issn:
  - 0021-2172
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Connections between graphs and matrix spaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 256
year: '2023'
...
---
OA_place: repository
OA_type: green
_id: '22159'
abstract:
- lang: eng
  text: 'The size Ramsey number of a graph H is defined as the minimum number of edges
    in a graph G such that there is a monochromatic copy of H in every two-coloring
    of E(G). The size Ramsey number was introduced by Erdős, Faudree, Rousseau, and
    Schelp in 1978 and they ended their foundational paper by asking whether one can
    determine up to a constant factor the size Ramsey numbers of three families of
    graphs: complete bipartite graphs, book graphs (obtained by adding many common
    neighbors to the vertices of a clique), and starburst graphs (obtained by adding
    many pendant edges to each vertex of a clique). In this paper, we completely resolve
    the latter two questions and make substantial progress on the first by determining
    the size Ramsey number of Ks,t up to a constant factor for all t=Ω(s log s).'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: David
  full_name: Conlon, David
  last_name: Conlon
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Conlon D, Fox J, Wigderson Y. Three early problems on size Ramsey numbers.
    <i>Combinatorica</i>. 2023;43(4):743-768. doi:<a href="https://doi.org/10.1007/s00493-023-00034-7">10.1007/s00493-023-00034-7</a>
  apa: Conlon, D., Fox, J., &#38; Wigderson, Y. (2023). Three early problems on size
    Ramsey numbers. <i>Combinatorica</i>. Springer Nature. <a href="https://doi.org/10.1007/s00493-023-00034-7">https://doi.org/10.1007/s00493-023-00034-7</a>
  chicago: Conlon, David, Jacob Fox, and Yuval Wigderson. “Three Early Problems on
    Size Ramsey Numbers.” <i>Combinatorica</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s00493-023-00034-7">https://doi.org/10.1007/s00493-023-00034-7</a>.
  ieee: D. Conlon, J. Fox, and Y. Wigderson, “Three early problems on size Ramsey
    numbers,” <i>Combinatorica</i>, vol. 43, no. 4. Springer Nature, pp. 743–768,
    2023.
  ista: Conlon D, Fox J, Wigderson Y. 2023. Three early problems on size Ramsey numbers.
    Combinatorica. 43(4), 743–768.
  mla: Conlon, David, et al. “Three Early Problems on Size Ramsey Numbers.” <i>Combinatorica</i>,
    vol. 43, no. 4, Springer Nature, 2023, pp. 743–68, doi:<a href="https://doi.org/10.1007/s00493-023-00034-7">10.1007/s00493-023-00034-7</a>.
  short: D. Conlon, J. Fox, Y. Wigderson, Combinatorica 43 (2023) 743–768.
date_created: 2026-06-29T10:51:32Z
date_published: 2023-08-01T00:00:00Z
date_updated: 2026-07-08T10:34:40Z
day: '01'
doi: 10.1007/s00493-023-00034-7
extern: '1'
external_id:
  arxiv:
  - '2111.05420'
intvolume: '        43'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2111.05420
month: '08'
oa: 1
oa_version: Preprint
page: 743-768
publication: Combinatorica
publication_identifier:
  eissn:
  - 1439-6912
  issn:
  - 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Three early problems on size Ramsey numbers
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 43
year: '2023'
...
---
OA_place: repository
OA_type: green
_id: '22164'
abstract:
- lang: eng
  text: 'The clique removal lemma says that for every ≥r 3 andε > 0, there exists
    some δ > 0 so that every n‐vertex graph G with fewer than δnr copies of K r can
    be made K r ‐free by removing at most εn2 edges. The dependence of δ on ε in this
    result is notoriously difficult to determine: it is known that δ−1 must be at
    least super‐polynomial in ε−1, and that it is at most of tower type in εlog −1.
    We prove that if one imposes an appropriate minimum degree condition on G, then
    one can actually take δ to be a linear function of ε in the clique removal lemma.
    Moreover, we determine the threshold for such a minimum degree requirement, showing
    that above this threshold we have linear bounds, whereas below the threshold the
    bounds are once again super‐polynomial, as in the unrestricted removal lemma.
    We also investigate this question for other graphs besides cliques, and prove
    some general results about how minimum degree conditions affect the bounds in
    the graph removal lemma.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, Wigderson Y. Minimum degree and the graph removal lemma. <i>Journal
    of Graph Theory</i>. 2023;102(4):648-665. doi:<a href="https://doi.org/10.1002/jgt.22891">10.1002/jgt.22891</a>
  apa: Fox, J., &#38; Wigderson, Y. (2023). Minimum degree and the graph removal lemma.
    <i>Journal of Graph Theory</i>. Wiley. <a href="https://doi.org/10.1002/jgt.22891">https://doi.org/10.1002/jgt.22891</a>
  chicago: Fox, Jacob, and Yuval Wigderson. “Minimum Degree and the Graph Removal
    Lemma.” <i>Journal of Graph Theory</i>. Wiley, 2023. <a href="https://doi.org/10.1002/jgt.22891">https://doi.org/10.1002/jgt.22891</a>.
  ieee: J. Fox and Y. Wigderson, “Minimum degree and the graph removal lemma,” <i>Journal
    of Graph Theory</i>, vol. 102, no. 4. Wiley, pp. 648–665, 2023.
  ista: Fox J, Wigderson Y. 2023. Minimum degree and the graph removal lemma. Journal
    of Graph Theory. 102(4), 648–665.
  mla: Fox, Jacob, and Yuval Wigderson. “Minimum Degree and the Graph Removal Lemma.”
    <i>Journal of Graph Theory</i>, vol. 102, no. 4, Wiley, 2023, pp. 648–65, doi:<a
    href="https://doi.org/10.1002/jgt.22891">10.1002/jgt.22891</a>.
  short: J. Fox, Y. Wigderson, Journal of Graph Theory 102 (2023) 648–665.
date_created: 2026-06-29T10:53:26Z
date_published: 2023-04-01T00:00:00Z
date_updated: 2026-07-14T08:24:20Z
day: '01'
doi: 10.1002/jgt.22891
extern: '1'
external_id:
  arxiv:
  - '2105.09194'
intvolume: '       102'
issue: '4'
keyword:
- chromatic threshold
- graph removal lemma
- homomorphism threshold
- minimum degree conditions
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2105.09194
month: '04'
oa: 1
oa_version: Preprint
page: 648-665
publication: Journal of Graph Theory
publication_identifier:
  eissn:
  - 1097-0118
  issn:
  - 0364-9024
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Minimum degree and the graph removal lemma
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 102
year: '2023'
...
---
OA_place: repository
OA_type: green
_id: '22165'
abstract:
- lang: eng
  text: "The book graph \U0001D435(\U0001D458)\r\n\U0001D45B consists of \U0001D45B
    copies of \U0001D43E\U0001D458+1 joined along a common \U0001D43E\U0001D458. In
    the prequel to this paper, we studied the diagonal Ramsey number \U0001D45F⁡(\U0001D435(\U0001D458)\r\n\U0001D45B,\U0001D435(\U0001D458)\r\n\U0001D45B).
    Here we consider the natural off-diagonal variant \U0001D45F⁡(\U0001D435(\U0001D458)\r\n\U0001D450⁢\U0001D45B,\U0001D435(\U0001D458)\r\n\U0001D45B)
    for fixed \U0001D450 ∈(0,1]. In this more general setting, we show that an interesting
    dichotomy emerges: for very small \U0001D450, a simple \U0001D458-partite construction
    dictates the Ramsey function and all nearly-extremal colourings are close to being
    \U0001D458-partite, while, for \U0001D450 bounded away from 0, random colourings
    of an appropriate density are asymptotically optimal and all nearly-extremal colourings
    are quasirandom. Our investigations also open up a range of questions about what
    happens for intermediate values of \U0001D450.\r\n\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: David
  full_name: Conlon, David
  last_name: Conlon
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Conlon D, Fox J, Wigderson Y. Off-diagonal book Ramsey numbers. <i>Combinatorics,
    Probability and Computing</i>. 2023;32(3):516-545. doi:<a href="https://doi.org/10.1017/s0963548322000360">10.1017/s0963548322000360</a>
  apa: Conlon, D., Fox, J., &#38; Wigderson, Y. (2023). Off-diagonal book Ramsey numbers.
    <i>Combinatorics, Probability and Computing</i>. Cambridge University Press. <a
    href="https://doi.org/10.1017/s0963548322000360">https://doi.org/10.1017/s0963548322000360</a>
  chicago: Conlon, David, Jacob Fox, and Yuval Wigderson. “Off-Diagonal Book Ramsey
    Numbers.” <i>Combinatorics, Probability and Computing</i>. Cambridge University
    Press, 2023. <a href="https://doi.org/10.1017/s0963548322000360">https://doi.org/10.1017/s0963548322000360</a>.
  ieee: D. Conlon, J. Fox, and Y. Wigderson, “Off-diagonal book Ramsey numbers,” <i>Combinatorics,
    Probability and Computing</i>, vol. 32, no. 3. Cambridge University Press, pp.
    516–545, 2023.
  ista: Conlon D, Fox J, Wigderson Y. 2023. Off-diagonal book Ramsey numbers. Combinatorics,
    Probability and Computing. 32(3), 516–545.
  mla: Conlon, David, et al. “Off-Diagonal Book Ramsey Numbers.” <i>Combinatorics,
    Probability and Computing</i>, vol. 32, no. 3, Cambridge University Press, 2023,
    pp. 516–45, doi:<a href="https://doi.org/10.1017/s0963548322000360">10.1017/s0963548322000360</a>.
  short: D. Conlon, J. Fox, Y. Wigderson, Combinatorics, Probability and Computing
    32 (2023) 516–545.
date_created: 2026-06-29T10:53:47Z
date_published: 2023-05-01T00:00:00Z
date_updated: 2026-07-14T08:27:40Z
day: '01'
doi: 10.1017/s0963548322000360
extern: '1'
external_id:
  arxiv:
  - '2110.14483'
intvolume: '        32'
issue: '3'
keyword:
- Ramsey theory
- book graphs
- Ramsey goodness
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2110.14483
mathsc:
- 05C55
- 05D10
month: '05'
oa: 1
oa_version: Preprint
page: 516-545
publication: Combinatorics, Probability and Computing
publication_identifier:
  eissn:
  - 1469-2163
  issn:
  - 0963-5483
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Off-diagonal book Ramsey numbers
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 32
year: '2023'
...
---
OA_place: repository
OA_type: green
_id: '22170'
abstract:
- lang: eng
  text: "Extending an earlier conjecture of Erdős, Burr and Rosta conjectured that
    among all two-colorings of the edges of a complete graph, the uniformly random
    coloring asymptotically minimizes the number of monochromatic copies of any fixed
    graph H. This conjecture was disproved independently by Sidorenko and Thomason.
    The first author later found quantitatively stronger counterexamples, using the
    Turán coloring, in which one of the two colors spans a balanced complete multipartite
    graph.\r\nWe prove that the Turán coloring is extremal for an infinite family
    of graphs, and that it is the unique extremal coloring. This yields the first
    determination of the Ramsey multiplicity constant of a graph for which the Burr--Rosta
    conjecture fails.\r\nWe also prove an analogous three-color result. In this case,
    our result is conditional on a certain natural conjecture on the behavior of two-color
    Ramsey numbers."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, Wigderson Y. Ramsey multiplicity and the Turán coloring. <i>Advances
    in Combinatorics</i>. 2023. doi:<a href="https://doi.org/10.19086/aic.2023.2">10.19086/aic.2023.2</a>
  apa: Fox, J., &#38; Wigderson, Y. (2023). Ramsey multiplicity and the Turán coloring.
    <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals. <a
    href="https://doi.org/10.19086/aic.2023.2">https://doi.org/10.19086/aic.2023.2</a>
  chicago: Fox, Jacob, and Yuval Wigderson. “Ramsey Multiplicity and the Turán Coloring.”
    <i>Advances in Combinatorics</i>. Alliance of Diamond Open Access Journals, 2023.
    <a href="https://doi.org/10.19086/aic.2023.2">https://doi.org/10.19086/aic.2023.2</a>.
  ieee: J. Fox and Y. Wigderson, “Ramsey multiplicity and the Turán coloring,” <i>Advances
    in Combinatorics</i>. Alliance of Diamond Open Access Journals, 2023.
  ista: Fox J, Wigderson Y. 2023. Ramsey multiplicity and the Turán coloring. Advances
    in Combinatorics.
  mla: Fox, Jacob, and Yuval Wigderson. “Ramsey Multiplicity and the Turán Coloring.”
    <i>Advances in Combinatorics</i>, Alliance of Diamond Open Access Journals, 2023,
    doi:<a href="https://doi.org/10.19086/aic.2023.2">10.19086/aic.2023.2</a>.
  short: J. Fox, Y. Wigderson, Advances in Combinatorics (2023).
date_created: 2026-06-29T10:55:46Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2026-07-14T08:45:53Z
day: '01'
doi: 10.19086/aic.2023.2
extern: '1'
external_id:
  arxiv:
  - '2207.07775'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2207.07775
month: '01'
oa: 1
oa_version: Preprint
publication: Advances in Combinatorics
publication_identifier:
  eissn:
  - 2517-5599
publication_status: published
publisher: Alliance of Diamond Open Access Journals
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ramsey multiplicity and the Turán coloring
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...