9 citations · 29 across the 37 of their papers we have counts for
7 papers · 1 filter
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…