12 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…
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 t…
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…
Universality for transversal Hamilton cycles in random graphs
Micha Christoph, Anders Martinsson, Aleksa MilojeviÄ
A tuple of graphs on the same vertex set of size is said to be Hamilton-universal if for every map there exists a Hamilton cycle whose -th…
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,…
Extending Thomassen's conjecture to directed graphs
Micha Christoph, Barnabás Janzer, Kalina Petrova +1
A famous conjecture by Thomassen from 1983 asserts that for any given there exists some such that every graph of minimum degree at leas…