R. Steiner

activity

20142023

most citedUniform bounds on sup-norms of holomorphic forms of real weight

7 citations · 44 across the 35 of their papers we have counts for

collaborators

58 papers

math.CO2023

Clustered Colouring of Odd- $H$ -Minor-Free Graphs

Robert Hickingbotham, Dong Yeap Kang, Sang-il Oum +2

The clustered chromatic number of a graph class $G$ is the minimum integer $c$ such that every graph $G \in G$ has a $c$ -colouring where each monochromatic compon…

math.CO2023

Finding dense minors using average degree

Kevin Hendrey, Sergey Norin, Raphael Steiner +1

Motivated by Hadwiger's conjecture, we study the problem of finding the densest possible $t$ -vertex minor in graphs of average degree at least $t - 1$ . We show that if $G$ has averag…

math.CO2023

Size-Ramsey numbers of structurally sparse graphs

Nemanja Draganić, Marc Kaufmann, David Munhá Correia +2

Size-Ramsey numbers are a central notion in combinatorics and have been widely studied since their introduction by Erdős, Faudree, Rousseau and Schelp in 1978. Research has mainly…

math.CO2023

A logarithmic bound for simultaneous embeddings of planar graphs

Raphael Steiner

A set $G$ of planar graphs on the same number $n$ of vertices is called simultaneously embeddable if there exists a set $P$ of $n$ points in the plane such that every gra…

math.CO2023

Chromatic number is not tournament-local

António Girão, Kevin Hendrey, Freddie Illingworth +4

Scott and Seymour conjectured the existence of a function $f : N \to N$ such that, for every graph $G$ and tournament $T$ on the same vertex set, $χ(G) \geqs…

math.CO2023

On Connectivity in Random Graph Models with Limited Dependencies

Johannes Lengler, Anders Martinsson, Kalina Petrova +4

For any positive edge density $p$ , a random graph in the Erdős-Renyi $G_{n, p}$ model is connected with non-zero probability, since all edges are mutually independent. We consider r…

math.CO2023

On the choosability of $H$ -minor-free graphs

Olivier Fischer, Raphael Steiner

Given a graph $H$ , let us denote by $f_{χ} (H)$ and $f_{ℓ} (H)$ , respectively, the maximum chromatic number and the maximum list chromatic number of $H$ -minor-free graphs. Hadwiger's…

cs.CG2023

Linear Size Universal Point Sets for Classes of Planar Graphs

Stefan Felsner, Hendrik Schrezenmaier, Felix Schröder +1

A finite set $P$ of points in the plane is $n$ -universal with respect to a class $C$ of planar graphs if every $n$ -vertex graph in $C$ admits a crossing-free st…

math.NT2023

Sums of Cusp Form Coefficients Along Quadratic Sequences

Chan Ieong Kuan, David Lowry-Duda, Alexander Walker +1

Let $f (z) = \sum A (n) n^{(k - 1) /2} e (n z)$ be a cusp form of weight $k \geq 3$ on $Γ_{0} (N)$ with character $χ$ . By studying a certain shifted convolution sum, we prove that $\sum_{n \…

math.OC2022

Inapproximability of shortest paths on perfect matching polytopes

Jean Cardinal, Raphael Steiner

We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless $P = N P$ , there is no polynom…

math.CO2022

Subdigraphs of prescribed size and outdegree

Raphael Steiner

In 2006, Noga Alon raised the following open problem: Does there exist an absolute constant $c > 0$ such that every $2 n$ -vertex digraph with minimum out-degree at least $s$ contains…

math.CO2022

Strengthening Hadwiger's conjecture for $4$ - and $5$ -chromatic graphs

Anders Martinsson, Raphael Steiner

Hadwiger's famous coloring conjecture states that every $t$ -chromatic graph contains a $K_{t}$ -minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139--144] conjectured the follo…

math.CO2022

Subdivisions with congruence constraints in digraphs of large chromatic number

Raphael Steiner

We prove that for every digraph $F$ and every assignment of pairs of integers $(r_{e}, q_{e})_{e \in A (F)}$ to its arcs there exists an integer $N$ such that every digraph $D$ with dich…

math.NT2022★ 3 cited

Small diameters and generators for arithmetic lattices in $SL_{2} (R)$ and certain Ramanujan graphs

Raphael S. Steiner

We show that arithmetic lattices in $SL_{2} (R)$ , stemming from the proper units of an Eichler order in an indefinite quaternion algebra over $Q$ , admit a…

math.NT2022★ 6 cited

Theta functions, fourth moments of eigenforms, and the sup-norm problem II

Ilya Khayutin, Paul D. Nelson, Raphael S. Steiner

For an $L^{2}$ -normalized holomorphic newform $f$ of weight $k$ on a hyperbolic surface of volume $V$ attached to an Eichler order of squarefree level in an indefinite quaternion alg…

cs.DS2022

Exact Matching: Correct Parity and FPT Parameterized by Independence Number

Nicolas {El Maalouly}, Raphael Steiner, Lasse Wulf

Given an integer $k$ and a graph where every edge is colored either red or blue, the goal of the exact matching problem is to find a perfect matching with the property that exactly…

math.CO2022

Coloring hypergraphs with excluded minors

Raphael Steiner

Hadwiger's conjecture, among the most famous open problems in graph theory, states that every graph that does not contain $K_{t}$ as a minor is properly $(t - 1)$ -colorable. The purpos…

math.CO2022

Coloring circle arrangements: New $4$ -chromatic planar graphs

Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher +3

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most $3$ . Motivated by this conjecture, we…

math.CO2022

Cycle lengths modulo $k$ in expanders

Anders Martinsson, Raphael Steiner

Given a constant $α > 0$ , an $n$ -vertex graph is called an $α$ -expander if every set $X$ of at most $n /2$ vertices in $G$ has an external neighborhood of size at least $α ∣ X ∣$ . Addres…

math.CO2022

Improved bound for improper colorings of graphs with no odd clique minor

Raphael Steiner

Strengthening Hadwiger's conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd $K_{t}$ -minor is properly $(t - 1)$ -colorable, this is known as the Odd Hadwig…

math.CO2022★ 1 cited

Heroes in orientations of chordal graphs

Pierre Aboulker, Guillaume Aubian, Raphael Steiner

We characterize all digraphs $H$ such that orientations of chordal graphs with no induced copy of $H$ have bounded dichromatic number.

cs.DS2022

Exact Matching in Graphs of Bounded Independence Number

Nicolas El Maalouly, Raphael Steiner

In the Exact Matching Problem (EM), we are given a graph equipped with a fixed coloring of its edges with two colors (red and blue), as well as a positive integer $k$ . The task is…

math.CO2022

Matching Theory and Barnette's Conjecture

Maximilian Gorsky, Raphael Steiner, Sebastian Wiederrecht

Barnette's Conjecture claims that all cubic, 3-connected, planar, bipartite graphs are Hamiltonian. We give a translation of this conjecture into the matching-theoretic setting. Th…

math.CO2022

Disproof of a Conjecture by Woodall

Raphael Steiner

In 2001, Woodall conjectured that for every pair of integers $s, t \geq 1$ , all graphs without a $K_{s, t}$ -minor are $(s + t - 1)$ -choosable. In this note we refute this conjecture in a…

Clustered Colouring of Odd-H-Minor-Free Graphs

Finding dense minors using average degree

Size-Ramsey numbers of structurally sparse graphs

A logarithmic bound for simultaneous embeddings of planar graphs

Chromatic number is not tournament-local

On Connectivity in Random Graph Models with Limited Dependencies

On the choosability of H-minor-free graphs

Linear Size Universal Point Sets for Classes of Planar Graphs

Sums of Cusp Form Coefficients Along Quadratic Sequences

Inapproximability of shortest paths on perfect matching polytopes

Subdigraphs of prescribed size and outdegree

Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs

Subdivisions with congruence constraints in digraphs of large chromatic number

Small diameters and generators for arithmetic lattices in SL2​(R) and certain Ramanujan graphs

Theta functions, fourth moments of eigenforms, and the sup-norm problem II

Exact Matching: Correct Parity and FPT Parameterized by Independence Number

Coloring hypergraphs with excluded minors

Coloring circle arrangements: New 4-chromatic planar graphs

Cycle lengths modulo k in expanders

Improved bound for improper colorings of graphs with no odd clique minor

Heroes in orientations of chordal graphs

Exact Matching in Graphs of Bounded Independence Number

Matching Theory and Barnette's Conjecture

Disproof of a Conjecture by Woodall

Clustered Colouring of Odd- $H$ -Minor-Free Graphs

On the choosability of $H$ -minor-free graphs

Strengthening Hadwiger's conjecture for $4$ - and $5$ -chromatic graphs

Small diameters and generators for arithmetic lattices in $SL_{2} (R)$ and certain Ramanujan graphs

Coloring circle arrangements: New $4$ -chromatic planar graphs

Cycle lengths modulo $k$ in expanders