1 citations · 1 across the 17 of their papers we have counts for
6 papers · 1 filter
Thinning and sprinkling: from robust sampling to almost Hamiltonicity
Micha Christoph, Zach Hunter, Benny Sudakov
We develop the thinning--sprinkling technique, a general method for proving robustness of graph properties under random vertex sampling. Using it, we show that random induced subgr…
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…
Towards the Lovász conjecture via sublinear expanders
Matija Bucić, Micha Christoph, Alexey Pokrovskiy +1
Lovász' famous Hamiltonicity conjecture (1969) states that every connected vertex-transitive graph has a Hamiltonian path. A stronger version of the conjecture, often attributed to…
The Mihail-Vazirani conjecture and strong edge-expansion in random polytopes
Micha Christoph, Sahar Diskin, Lyuben Lichev +1
We study the edge-expansion of the graph of a random polytope , defined as the convex hull of a random subset of the points in where every point is retaine…
Subgraph discrepancies in the complete graph
Micha Christoph, Lior Gishboliner, Michael Krivelevich
Given a 2-edge-coloring , the discrepancy of a subgraph is defined as . Erdős, Füredi, Lo…