Raphael Steiner

activity

20242026

collaborators

11 papers

math.CO2026

Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

Romain Bourneuf, Raphael Steiner, Stéphan Thomassé +1

We determine the asymmetric homomorphism threshold from graphs of odd girth at least $7$ to triangle-free graphs, showing that $δ_{hom} ({C_{3}, C_{5}}, {C_{3}}) = \frac{1}{9}$ .…

math.CO2026

Proof of Lichiardopol's conjecture on disjoint directed cycles of distinct lengths

Sandra Albrechtsen, Raphael Steiner

There is a fascinating array of interrelated questions studying which structures can be guaranteed in digraphs of large minimum out-degree. These often have intriguingly simple sta…

math.CO2026

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…

math.CO2025

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…

math.CO2025

Critical edge sets in vertex-critical graphs

Ema Skottova, Raphael Steiner

Criticality is a fundamental notion in graph theory that has been studied continually since its introduction in the early 50s by Dirac. A graph is called $k$ -vertex-critical ( $k$ -e…

math.CO2025

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…

math.CO2024

Local Shearer bound

Anders Martinsson, Raphael Steiner

We prove the following local strengthening of Shearer's classic bound on the independence number of triangle-free graphs: For every triangle-free graph $G$ there exists a probabili…

math.CO2024

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…

math.CO2024

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…

math.CO2024

Resolution of the Kohayakawa-Kreuter conjecture

Micha Christoph, Anders Martinsson, Raphael Steiner +1

A graph $G$ is said to be Ramsey for a tuple of graphs $(H_{1}, \dots, H_{r})$ if every $r$ -coloring of the edges of $G$ contains a monochromatic copy of $H_{i}$ in color $i$ , for some $i$ …

math.CO2024

Hadwiger's conjecture and topological bounds

Raphael Steiner

The Odd Hadwiger's conjecture, formulated by Gerards and Seymour in 1995, is a substantial strengthening of Hadwiger's famous coloring conjecture from 1943. We investigate whether…

Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

Proof of Lichiardopol's conjecture on disjoint directed cycles of distinct lengths

Towards the Lovász conjecture via sublinear expanders

Extending Thomassen's conjecture to directed graphs

Critical edge sets in vertex-critical graphs

Proof of the KAMAK tree conjecture

Local Shearer bound

Topological Minors in Typical Lifts

Improved bounds for zero-sum cycles in Zpd​

Resolution of the Kohayakawa-Kreuter conjecture

Hadwiger's conjecture and topological bounds

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