Yuval Wigderson

Last Name

Wigderson

First Name

Yuval

ORCID

0000-0001-5909-9250

Organisational unit

02889 - ETH Institut für Theoretische Studien / ETH Institute for Theoretical Studies

Show all metadata

Search Results

Publications 1 - 10 of 10

An efficient asymmetric removal lemma and its limitations
Gishboliner, Lior; Shapira, Asaf; Wigderson, Yuval (2025)
Forum of Mathematics, Sigma
On Linear-Algebraic Notions of Expansion
Li, Yinan; Qiao, Youming; Wigderson, Avi; et al. (2025)
Theory of Computing
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. There 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. Moreover, 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.
Resolution of the Kohayakawa–Kreuter conjecture
Christoph, Micha; Martinsson, Anders; Steiner, Raphael; et al. (2025)
Proceedings of the London Mathematical Society
A graph G is said to be Ramsey for a tuple of grahps (H₁,…,Hᵣ) if every r-coloring of the edges of G contains a monochromatic copy of Hᵢ in color i, for some i. A fundamental question at the intersection of Ramsey theory and the theory of random graphs is to determine the threshold at which the binomial random graph Gₙ,ₚ becomes asymptotically almost surely Ramsey for a fixed tuple (H₁,…,Hᵣ), and a famous conjecture of Kohayakawa and Kreuter predicts this threshold. Earlier work of Mousset-Nenadov-Samotij, Bowtell-Hancock-Hyde, and Kuperwasser-Samotij-Wigderson has reduced this probabilistic problem to a deterministic graph decomposition conjecture. In this paper, we resolve this deterministic problem, thus proving the Kohayakawa–Kreuter conjecture. Along the way, we prove a number of novel graph decomposition results that may be of independent interest.
Larger nearly orthogonal sets over finite fields
Haviv, Ishay; Mattheus, Sam; Milojević, Aleksa; et al. (2025)
Discrete Mathematics
Ramsey numbers of sparse digraphs
Fox, Jacob; He, Xiaoyu; Wigderson, Yuval (2024)
Israel Journal of Mathematics
Canonical Ramsey Numbers of Sparse Graphs
Gishboliner, Lior; Milojević, Aleksa; Sudakov, Benny; et al. (2025)
SIAM Journal on Discrete Mathematics
The canonical Ramsey theorem of Erdős and Rado implies that for any graph Η, any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph ΚN contains a monochromatic, lexicographic, or rainbow copy of H. The least such N is called the Erdős-Rado number of H, denoted by ER(H). 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 H has bounded degree, then ER(H) is polynomial in | V (H)| if H 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 Pt, we study the minimum N such that every edge-coloring of KN contains a monochromatic copy of S or a rainbow copy of Pt. 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.
Infinitely many minimally non-Ramsey size-linear graphs
Wigderson, Yuval (2025)
European Journal of Combinatorics
A graph G is said to be Ramsey size-linear if r(G,H)=OG(e(H)) for every graph H with no isolated vertices. Erdős, Faudree, Rousseau, and Schelp observed that K4 is not Ramsey size-linear, but each of its proper subgraphs is, and they asked whether there exist infinitely many such graphs. In this short note, we answer this question in the affirmative.
Ramsey numbers upon vertex deletion
Wigderson, Yuval (2024)
Journal of Graph Theory
Given a graph G $G$, its Ramsey number r( G ) $r(G)$ is the minimum N $N$ so that every two-coloring of E( K N ) $E({K}_{N})$ contains a monochromatic copy of G $G$. It was conjectured by Conlon, Fox, and Sudakov that if one deletes a single vertex from G $G$, 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 { G n } $\{{G}_{n}\}$ so that in any Ramsey coloring for G n ${G}_{n}$ (i.e., a coloring of a clique on r( G n ) - 1 $r({G}_{n})-1$ vertices with no monochromatic copy of G n ${G}_{n}$), one of the color classes has density o( 1 ) $o(1)$.
The inertia bound is far from tight
Kwan, Matthew; Wigderson, Yuval (2024)
Bulletin of the London Mathematical Society
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 α(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 α(G) ≤ 4n³/⁴, but the inertia bound is always at least n/4. In particular, these results address questions of Rooney, Sinkovic, and Wocjan–Elphick–Abiad.
On the Kohayakawa-Kreuter conjecture
Kuperwasser, Eden; Samotij, Wojciech; Wigderson, Yuval (2025)
Mathematical Proceedings of the Cambridge Philosophical Society
Let us say that a graph $G$ is Ramsey for a tuple $(H_1,\ldots,H_r)$ of graphs if every r-colouring of the edges of G contains a monochromatic copy of $H_i$ in colour i, for some $i \in [\![{r}]\!]$ . A famous conjecture of Kohayakawa and Kreuter, extending seminal work of R & ouml;dl and Ruci & nacute;ski, predicts the threshold at which the binomial random graph $G_{n,p}$ becomes Ramsey for $(H_1,\ldots,H_r)$ asymptotically almost surely.In this paper, we resolve the Kohayakawa-Kreuter conjecture for almost all tuples of graphs. Moreover, we reduce its validity to the truth of a certain deterministic statement, which is a clear necessary condition for the conjecture to hold. All of our results actually hold in greater generality, when one replaces the graphs $H_1,\ldots,H_r$ by finite families $\mathcal{H}_1,\ldots,\mathcal{H}_r$ . Additionally, we pose a natural (deterministic) graph-partitioning conjecture, which we believe to be of independent interest, and whose resolution would imply the Kohayakawa-Kreuter conjecture.

Publications 1 - 10 of 10

Yuval Wigderson

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results