---
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.
Combinatorics, Probability and Computing. 2026:1-14. doi:10.1017/s0963548326100443
apa: He, X., Nie, J., Wigderson, Y., & Yu, H.-H. (2026). Off-diagonal Ramsey
numbers for linear hypergraphs. Combinatorics, Probability and Computing.
Cambridge University Press. https://doi.org/10.1017/s0963548326100443
chicago: He, Xiaoyu, Jiaxi Nie, Yuval Wigderson, and Hung-Hsun Yu. “Off-Diagonal
Ramsey Numbers for Linear Hypergraphs.” Combinatorics, Probability and Computing.
Cambridge University Press, 2026. https://doi.org/10.1017/s0963548326100443.
ieee: X. He, J. Nie, Y. Wigderson, and H.-H. Yu, “Off-diagonal Ramsey numbers for
linear hypergraphs,” Combinatorics, Probability and Computing. 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.” Combinatorics,
Probability and Computing, Cambridge University Press, 2026, pp. 1–14, doi:10.1017/s0963548326100443.
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: '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. SIAM Journal on Discrete Mathematics. 2025;39(3):1491-1519.
doi:10.1137/24m1714964
apa: Gishboliner, L., Milojević, A., Sudakov, B., & Wigderson, Y. (2025). Canonical
Ramsey numbers of sparse graphs. SIAM Journal on Discrete Mathematics.
Society for Industrial & Applied Mathematics. https://doi.org/10.1137/24m1714964
chicago: Gishboliner, Lior, Aleksa Milojević, Benny Sudakov, and Yuval Wigderson.
“Canonical Ramsey Numbers of Sparse Graphs.” SIAM Journal on Discrete Mathematics.
Society for Industrial & Applied Mathematics, 2025. https://doi.org/10.1137/24m1714964.
ieee: L. Gishboliner, A. Milojević, B. Sudakov, and Y. Wigderson, “Canonical Ramsey
numbers of sparse graphs,” SIAM Journal on Discrete Mathematics, vol. 39,
no. 3. Society for Industrial & 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.” SIAM
Journal on Discrete Mathematics, vol. 39, no. 3, Society for Industrial &
Applied Mathematics, 2025, pp. 1491–519, doi:10.1137/24m1714964.
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. Proceedings of the London Mathematical Society. 2025;130(1).
doi:10.1112/plms.70013
apa: Christoph, M., Martinsson, A., Steiner, R., & Wigderson, Y. (2025). Resolution
of the Kohayakawa–Kreuter conjecture. Proceedings of the London Mathematical
Society. Wiley. https://doi.org/10.1112/plms.70013
chicago: Christoph, Micha, Anders Martinsson, Raphael Steiner, and Yuval Wigderson.
“Resolution of the Kohayakawa–Kreuter Conjecture.” Proceedings of the London
Mathematical Society. Wiley, 2025. https://doi.org/10.1112/plms.70013.
ieee: M. Christoph, A. Martinsson, R. Steiner, and Y. Wigderson, “Resolution of
the Kohayakawa–Kreuter conjecture,” Proceedings of the London Mathematical
Society, 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.”
Proceedings of the London Mathematical Society, vol. 130, no. 1, e70013,
Wiley, 2025, doi:10.1112/plms.70013.
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. Forum of Mathematics, Sigma. 2025;13. doi:10.1017/fms.2024.68
apa: Gishboliner, L., Shapira, A., & Wigderson, Y. (2025). An efficient asymmetric
removal lemma and its limitations. Forum of Mathematics, Sigma. Cambridge
University Press. https://doi.org/10.1017/fms.2024.68
chicago: Gishboliner, Lior, Asaf Shapira, and Yuval Wigderson. “An Efficient Asymmetric
Removal Lemma and Its Limitations.” Forum of Mathematics, Sigma. Cambridge
University Press, 2025. https://doi.org/10.1017/fms.2024.68.
ieee: L. Gishboliner, A. Shapira, and Y. Wigderson, “An efficient asymmetric removal
lemma and its limitations,” Forum of Mathematics, Sigma, 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.”
Forum of Mathematics, Sigma, vol. 13, e38, Cambridge University Press,
2025, doi:10.1017/fms.2024.68.
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: 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. Bulletin of the
London Mathematical Society. 2024;56(10):3196-3208. doi:10.1112/blms.13127
apa: Kwan, M., & Wigderson, Y. (2024). The inertia bound is far from tight.
Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.13127
chicago: Kwan, Matthew, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.”
Bulletin of the London Mathematical Society. Wiley, 2024. https://doi.org/10.1112/blms.13127.
ieee: M. Kwan and Y. Wigderson, “The inertia bound is far from tight,” Bulletin
of the London Mathematical Society, 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.”
Bulletin of the London Mathematical Society, vol. 56, no. 10, Wiley, 2024,
pp. 3196–208, doi:10.1112/blms.13127.
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: '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. Israel Journal of Mathematics. 2023;256(2):513-580.
doi:10.1007/s11856-023-2515-7
apa: Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., & Zhang, C. (2023). Connections
between graphs and matrix spaces. Israel Journal of Mathematics. Springer
Nature. https://doi.org/10.1007/s11856-023-2515-7
chicago: Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang.
“Connections between Graphs and Matrix Spaces.” Israel Journal of Mathematics.
Springer Nature, 2023. https://doi.org/10.1007/s11856-023-2515-7.
ieee: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “Connections between
graphs and matrix spaces,” Israel Journal of Mathematics, 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.” Israel
Journal of Mathematics, vol. 256, no. 2, Springer Nature, 2023, pp. 513–80,
doi:10.1007/s11856-023-2515-7.
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.
Combinatorica. 2023;43(4):743-768. doi:10.1007/s00493-023-00034-7
apa: Conlon, D., Fox, J., & Wigderson, Y. (2023). Three early problems on size
Ramsey numbers. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-023-00034-7
chicago: Conlon, David, Jacob Fox, and Yuval Wigderson. “Three Early Problems on
Size Ramsey Numbers.” Combinatorica. Springer Nature, 2023. https://doi.org/10.1007/s00493-023-00034-7.
ieee: D. Conlon, J. Fox, and Y. Wigderson, “Three early problems on size Ramsey
numbers,” Combinatorica, 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.” Combinatorica,
vol. 43, no. 4, Springer Nature, 2023, pp. 743–68, doi:10.1007/s00493-023-00034-7.
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: '22160'
abstract:
- lang: eng
text: 'Motivated by higher vanishing multiplicity generalizations of Alon''s Combinatorial
Nullstellensatz and its applications, we study the following problem: for fixed
and large with respect to , what is the minimum possible degree of a polynomial
with such that has zeroes of multiplicity at least at all points in ? For , a
classical theorem of Alon and Füredi states that the minimum possible degree of
such a polynomial equals . In this paper, we solve the problem for all , proving
that the answer is . As an application, we improve a result of Clifton and Huang
on configurations of hyperplanes in such that each point in is covered by at least
hyperplanes, but the point is uncovered. Surprisingly, the proof of our result
involves Catalan numbers and arguments from enumerative combinatorics.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Lisa
full_name: Sauermann, Lisa
last_name: Sauermann
- first_name: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: Sauermann L, Wigderson Y. Polynomials that vanish to high order on most of
the hypercube. Journal of the London Mathematical Society. 2022;106(3):2379-2402.
doi:10.1112/jlms.12637
apa: Sauermann, L., & Wigderson, Y. (2022). Polynomials that vanish to high
order on most of the hypercube. Journal of the London Mathematical Society.
Wiley. https://doi.org/10.1112/jlms.12637
chicago: Sauermann, Lisa, and Yuval Wigderson. “Polynomials That Vanish to High
Order on Most of the Hypercube.” Journal of the London Mathematical Society.
Wiley, 2022. https://doi.org/10.1112/jlms.12637.
ieee: L. Sauermann and Y. Wigderson, “Polynomials that vanish to high order on most
of the hypercube,” Journal of the London Mathematical Society, vol. 106,
no. 3. Wiley, pp. 2379–2402, 2022.
ista: Sauermann L, Wigderson Y. 2022. Polynomials that vanish to high order on most
of the hypercube. Journal of the London Mathematical Society. 106(3), 2379–2402.
mla: Sauermann, Lisa, and Yuval Wigderson. “Polynomials That Vanish to High Order
on Most of the Hypercube.” Journal of the London Mathematical Society,
vol. 106, no. 3, Wiley, 2022, pp. 2379–402, doi:10.1112/jlms.12637.
short: L. Sauermann, Y. Wigderson, Journal of the London Mathematical Society 106
(2022) 2379–2402.
date_created: 2026-06-29T10:51:52Z
date_published: 2022-10-01T00:00:00Z
date_updated: 2026-07-08T10:37:38Z
day: '01'
doi: 10.1112/jlms.12637
extern: '1'
external_id:
arxiv:
- '2010.00077'
intvolume: ' 106'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2010.00077
month: '10'
oa: 1
oa_version: Preprint
page: 2379-2402
publication: Journal of the London Mathematical Society
publication_identifier:
eissn:
- 1469-7750
issn:
- 0024-6107
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Polynomials that vanish to high order on most of the hypercube
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 106
year: '2022'
...
---
OA_place: repository
OA_type: green
_id: '22156'
abstract:
- lang: eng
text: Extending a recent breakthrough of Shitov, we prove that the chromatic number
of the tensor product of two graphs can be a constant factor smaller than the
minimum chromatic number of the two graphs. More precisely, we prove that there
exists an absolute constant δ>0 such that for all c sufficiently large, there
exist graphs G and H with chromatic number at least (1+δ)c for which χ(G×H)≤c.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- 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: He X, Wigderson Y. Hedetniemi’s conjecture is asymptotically false. Journal
of Combinatorial Theory, Series B. 2021;146:485-494. doi:10.1016/j.jctb.2020.03.003
apa: He, X., & Wigderson, Y. (2021). Hedetniemi’s conjecture is asymptotically
false. Journal of Combinatorial Theory, Series B. Elsevier. https://doi.org/10.1016/j.jctb.2020.03.003
chicago: He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically
False.” Journal of Combinatorial Theory, Series B. Elsevier, 2021. https://doi.org/10.1016/j.jctb.2020.03.003.
ieee: X. He and Y. Wigderson, “Hedetniemi’s conjecture is asymptotically false,”
Journal of Combinatorial Theory, Series B, vol. 146. Elsevier, pp. 485–494,
2021.
ista: He X, Wigderson Y. 2021. Hedetniemi’s conjecture is asymptotically false.
Journal of Combinatorial Theory, Series B. 146, 485–494.
mla: He, Xiaoyu, and Yuval Wigderson. “Hedetniemi’s Conjecture Is Asymptotically
False.” Journal of Combinatorial Theory, Series B, vol. 146, Elsevier,
2021, pp. 485–94, doi:10.1016/j.jctb.2020.03.003.
short: X. He, Y. Wigderson, Journal of Combinatorial Theory, Series B 146 (2021)
485–494.
date_created: 2026-06-29T10:50:09Z
date_published: 2021-01-01T00:00:00Z
date_updated: 2026-07-08T07:43:57Z
day: '01'
doi: 10.1016/j.jctb.2020.03.003
extern: '1'
external_id:
arxiv:
- '1906.06783'
intvolume: ' 146'
keyword:
- Graph coloring
- Hedetniemi's conjecture
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1906.06783
month: '01'
oa: 1
oa_version: Preprint
page: 485-494
publication: Journal of Combinatorial Theory, Series B
publication_identifier:
issn:
- 0095-8956
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Hedetniemi's conjecture is asymptotically false
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2021'
...
---
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. Journal
of Combinatorics. 2021;12(1):1-15. doi:10.4310/joc.2021.v12.n1.a1
apa: Fox, J., Luo, S., & Wigderson, Y. (2021). Extremal and Ramsey results on
graph blowups. Journal of Combinatorics. International Press of Boston.
https://doi.org/10.4310/joc.2021.v12.n1.a1
chicago: Fox, Jacob, Sammy Luo, and Yuval Wigderson. “Extremal and Ramsey Results
on Graph Blowups.” Journal of Combinatorics. International Press of Boston,
2021. https://doi.org/10.4310/joc.2021.v12.n1.a1.
ieee: J. Fox, S. Luo, and Y. Wigderson, “Extremal and Ramsey results on graph blowups,”
Journal of Combinatorics, 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.” Journal
of Combinatorics, vol. 12, no. 1, International Press of Boston, 2021, pp.
1–15, doi:10.4310/joc.2021.v12.n1.a1.
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'
...
---
OA_place: repository
OA_type: green
_id: '22153'
abstract:
- lang: eng
text: "A weakly optimal Ks-free (n,d,λ)-graph is a d-regular Ks-free graph on n
vertices with d=Θ(n1−α) and spectral expansion λ=Θ(n1−(s−1)α), for some fixed
α>0. Such a graph is called optimal if additionally α=12s−3. We prove that if
s1,…,sk≥3 are fixed positive integers and weakly optimal Ksi-free pseudorandom
graphs exist for each 1≤i≤k, then the multicolor Ramsey numbers satisfy\r\nΩ(tS+1log2St)≤r(s1,…,sk,t)≤O(tS+1logSt),\r\nas
t→∞, where S=∑ki=1(si−2). This generalizes previous results of Mubayi and Verstraëte,
who proved the case k=1, and Alon and Rödl, who proved the case s1=⋯=sk=3. Both
previous results used the existence of optimal rather than weakly optimal Ksi-free
graphs."
article_number: P1.32
article_processing_charge: No
article_type: original
arxiv: 1
author:
- 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: He X, Wigderson Y. Multicolor Ramsey numbers via pseudorandom graphs. The
Electronic Journal of Combinatorics. 2020;27(1). doi:10.37236/9071
apa: He, X., & Wigderson, Y. (2020). Multicolor Ramsey numbers via pseudorandom
graphs. The Electronic Journal of Combinatorics. The Electronic Journal
of Combinatorics. https://doi.org/10.37236/9071
chicago: He, Xiaoyu, and Yuval Wigderson. “Multicolor Ramsey Numbers via Pseudorandom
Graphs.” The Electronic Journal of Combinatorics. The Electronic Journal
of Combinatorics, 2020. https://doi.org/10.37236/9071.
ieee: X. He and Y. Wigderson, “Multicolor Ramsey numbers via pseudorandom graphs,”
The Electronic Journal of Combinatorics, vol. 27, no. 1. The Electronic
Journal of Combinatorics, 2020.
ista: He X, Wigderson Y. 2020. Multicolor Ramsey numbers via pseudorandom graphs.
The Electronic Journal of Combinatorics. 27(1), P1.32.
mla: He, Xiaoyu, and Yuval Wigderson. “Multicolor Ramsey Numbers via Pseudorandom
Graphs.” The Electronic Journal of Combinatorics, vol. 27, no. 1, P1.32,
The Electronic Journal of Combinatorics, 2020, doi:10.37236/9071.
short: X. He, Y. Wigderson, The Electronic Journal of Combinatorics 27 (2020).
date_created: 2026-06-29T10:47:47Z
date_published: 2020-02-07T00:00:00Z
date_updated: 2026-07-08T07:27:57Z
day: '07'
doi: 10.37236/9071
extern: '1'
external_id:
arxiv:
- '1910.06287'
intvolume: ' 27'
issue: '1'
language:
- iso: eng
month: '02'
oa_version: Preprint
publication: The Electronic Journal of Combinatorics
publication_identifier:
issn:
- 1077-8926
publication_status: published
publisher: The Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multicolor Ramsey numbers via pseudorandom graphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2020'
...