8 citations · 10 across the 25 of their papers we have counts for
31 papers · 1 filter
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…
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…