Micha Christoph

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 $λ (G)$ denote the spectral radius (maximum eigenvalue) of $G$ ,…

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 $d$ contains a cycle of length at least $d$ . 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 $0/1$ polytopes

Micha Christoph, Sahar Diskin, Lyuben Lichev +1

We study the edge-expansion of the graph of a random $0/1$ polytope $P_{p}^{d}$ , defined as the convex hull of a random subset of the points in ${0, 1}^{d}$ where every point is retaine…

Subgraph discrepancies in the complete graph

Micha Christoph, Lior Gishboliner, Michael Krivelevich

Given a 2-edge-coloring $f : E (K_{n}) \to {\pm 1}$ , the discrepancy of a subgraph $F \subseteq K_{n}$ is defined as $\sum_{e \in E (F)} f (e)$ . Erdős, Füredi, Lo…

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 $k, g \in N$ there exists some $d = d (k, g) \in N$ such that every graph of minimum degree at leas…

Cycle-factors of regular graphs via entropy

Micha Christoph, Nemanja Draganić, António Girão +3

It is a classical result that a random permutation of $n$ elements has, on average, about $lo g n$ cycles. We generalise this fact to all directed $d$ -regular graphs on $n$ vertice…

On a Ramsey--Turán variant of Roth's theorem

Matija Bucić, Micha Christoph, Jaehoon Kim +2

A classical theorem of Roth states that the maximum size of a solution-free set of a homogeneous linear equation $L$ in $F_{p}$ is $o (p)$ if and only if the sum of…

New bounds for linear arboricity and related problems

Micha Christoph, Nemanja Draganić, António Girão +3

A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture states that every graph of maximum degree $Δ$ can be decomposed into at most $\lceil(Δ+1)…

Proof of the KAMAK tree conjecture

Micha Christoph, Raphael Steiner

There are many intriguing questions in extremal graph theory that are well-understood in the undirected setting and yet remain elusive for digraphs. A natural instance of such a pr…

Universality for transversal Hamilton cycles in random graphs

Micha Christoph, Anders Martinsson, Aleksa Milojević

A tuple $(G_{1}, \dots, G_{n})$ of graphs on the same vertex set of size $n$ is said to be Hamilton-universal if for every map $χ : [n] \to [n]$ there exists a Hamilton cycle whose $i$ -th e…

Almost-perfect colorful matchings in three-edge-colored bipartite graphs

Simona Boyadzhiyska, Micha Christoph, Tibor Szabó

We prove that, for positive integers $n, a_{1}, a_{2}, a_{3}$ satisfying $a_{1} + a_{2} + a_{3} = n - 1$ , it holds that any bipartite graph $G$ which is the union of three perfect matchings $M_{1}$ , $M…

math.CO2024★ 1 cited

Almost-full transversals in equi- $n$ -squares

Debsoumya Chakraborti, Micha Christoph, Zach Hunter +2

In 1975, Stein made a wide generalisation of the Ryser-Brualdi-Stein conjecture on transversals in Latin squares, conjecturing that every equi- $n$ -square (an $n \times n$ array fill…

Unique subgraphs are rare

Domagoj Bradač, Micha Christoph

A folklore result attributed to Pólya states that there are $(1 + o (1)) 2^{(2 n)} / n!$ non-isomorphic graphs on $n$ vertices. Given two graphs $G$ and $H$ , we say that $G$ is…

Topological Minors in Typical Lifts

Matija Bucić, Micha Christoph, Alp Müyesser +1

An $ℓ$ -lift of a graph $G$ is any graph obtained by replacing every vertex of $G$ with an independent set of size $ℓ$ , and connecting every pair of two such independent sets…

Improved bounds for zero-sum cycles in $Z_{p}^{d}$

Micha Christoph, Charlotte Knierim, Anders Martinsson +1

For a finite Abelian group $(Γ, +)$ , let $n (Γ)$ denote the smallest positive integer $n$ such that for each labelling of the arcs of the complete digraph of order $n$ using elements…

The Hamilton space of pseudorandom graphs

Micha Christoph, Rajko Nenadov, Kalina Petrova

We show that if $n$ is odd and $p \geq C lo g n / n$ , then with high probability Hamilton cycles in $G (n, p)$ span its cycle space. More generally, we show this holds for a class of…