16 papers
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 theo…
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 o…
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…
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…
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…