9 citations · 29 across the 37 of their papers we have counts for
47 papers
Duality for matrix space questions
Yuval Wigderson
We present a new proof of a classical theorem of Dieudonné: if a linear space of matrices consists entirely of singular matrices, then its dimension is at most .…
Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth
Romain Bourneuf, Raphael Steiner, Stéphan Thomassé +1
We determine the asymmetric homomorphism threshold from graphs of odd girth at least to triangle-free graphs, showing that .…
The critical probability for percolation on finite graphs
Micha Christoph, Patryk Morawski, Yuval Wigderson
We determine the critical probability for Bernoulli bond percolation on essentially any finite graph. Namely, letting denote the spectral radius (maximum eigenvalue) of ,…
Robustness and hyperstability for the Erdős-Gallai theorem
Micha Christoph, Alp Müyesser, Yuval Wigderson
The Erdős--Gallai theorem states that every graph of average degree contains a cycle of length at least . We prove the following robust extension of the Erdős--Gallai theore…
Finding blowups one vertex at a time
Jacob Fox, Yuval Wigderson, Yunkun Zhou
An influential theorem of Nikiforov states that if an -vertex graph contains at least copies of some fixed -vertex graph , then contains an -blowup of or…
Jacobian graphs
Arthur Forey, Javier Fresán, Emmanuel Kowalski +1
We introduce jacobian graphs, which are explicit families of regular graphs that are spectrally indistinguishable from random graphs, but whose local structure is very different fr…
Color-avoiding directed paths in tournaments
Jacob Fox, Benny Sudakov, Yuval Wigderson
We study the following Ramsey-theoretic question: given a -coloring of the edges of a tournament, how long of a directed path can we guarantee whose edges avoid one of the color…
Disproof of the Odd Hadwiger Conjecture
Marcus Kühn, Lisa Sauermann, Raphael Steiner +1
We prove that there exist graphs which do not contain as an odd minor and whose chromatic number is at least . This disproves, in a strong form, the odd Had…
Spectrally indistinguishable pseudorandom graphs
Arthur Forey, Javier Fresán, Emmanuel Kowalski +1
We construct explicit families of graphs whose eigenvalues are asymptotically distributed according to Wigner's semicircle law; in other words, that are spectrally indistinguishabl…
Ramsey numbers of digraphs with local edge structure
Domagoj Bradač, Patryk Morawski, Benny Sudakov +1
One of the classical topics in graph Ramsey theory is the study of which -vertex graphs have Ramsey numbers that are linear in . In this paper, we consider this problem in th…
Regularity for hypergraphs with bounded VC dimension
Lior Gishboliner, Asaf Shapira, Yuval Wigderson
While Szemerédi's graph regularity lemma is an indispensable tool for studying extremal problems in graph theory, using it comes with a hefty price, since a worst-case graph may on…
Off-Diagonal Ramsey Numbers for Linear Hypergraphs
Xiaoyu He, Jiaxi Nie, Yuval Wigderson +1
We study off-diagonal Ramsey numbers of -uniform hypergraphs, where is a fixed linear -uniform hypergraph and is complete on vertices. R…
Is it easy to regularize a hypergraph with easy links?
Lior Gishboliner, Asaf Shapira, Yuval Wigderson
A partition of a (hyper)graph is -homogenous if the edge densities between almost all clusters are either at most or at least . Suppose a…
Asymmetric results about graph homomorphisms
Lior Gishboliner, Eoin Hurley, Yuval Wigderson
Many important results in extremal graph theory can be roughly summarised as "if a triangle-free graph has certain properties, then it has a homomorphism to a triangle-free gra…
Ordered Ramsey numbers of graphs with edges
Domagoj Bradač, Patryk Morawski, Benny Sudakov +1
Given a vertex-ordered graph , the ordered Ramsey number is the minimum integer such that every -coloring of the edges of the complete ordered graph contai…
Upper bounds on diagonal Ramsey numbers [after Campos, Griffiths, Morris, and Sahasrabudhe]
Yuval Wigderson
Ramsey's theorem states that if is sufficiently large, then no matter how one colors the edges among vertices with two colors, there are always vertices spanning edges…
Canonical Ramsey numbers of sparse graphs
Lior Gishboliner, Aleksa Milojević, Benny Sudakov +1
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 c…
Infinitely many minimally non-Ramsey size-linear graphs
Yuval Wigderson
A graph is said to be Ramsey size-linear if for every graph with no isolated vertices. Erdős, Faudree, Rousseau, and Schelp observed that is not…
Blowups of triangle-free graphs
António Girão, Zach Hunter, Yuval Wigderson
A highly influential result of Nikiforov states that if an -vertex graph contains at least copies of a fixed -vertex graph , then contains a blowup of o…
Counting subgraphs in locally dense graphs
Domagoj Bradač, Benny Sudakov, Yuval Wigderson
A graph is said to be -locally dense if every induced subgraph of with linearly many vertices has edge density at least . A famous conjecture of Kohayakawa, Nagle, Rö…
Oriented Ramsey numbers of graded digraphs
Patryk Morawski, Yuval Wigderson
We show that any graded digraph on vertices with maximum degree has an oriented Ramsey number of at most for some absolute constant , improving upon a rec…
Larger Nearly Orthogonal Sets over Finite Fields
Ishay Haviv, Sam Mattheus, Aleksa Milojević +1
For a field and integers and , a set is called -nearly orthogonal if its members are non-self-orthogonal and every ve…
Resolution of the Kohayakawa-Kreuter conjecture
Micha Christoph, Anders Martinsson, Raphael Steiner +1
A graph is said to be Ramsey for a tuple of graphs if every -coloring of the edges of contains a monochromatic copy of in color , for some …
The inertia bound is far from tight
Matthew Kwan, Yuval Wigderson
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 indepe…