Raphael Steiner

Last Name

Steiner

First Name

Raphael

ORCID

0000-0001-8391-8949

Show all metadata

Search Results

Publications1 - 10 of 38

Oriented Cycles in Digraphs of Large Outdegree
Gishboliner, Lior; Steiner, Raphael; Szabó, Tibor (2022)
Combinatorica
In 1985, Mader conjectured that for every acyclic digraph F there exists K = K(F) such that every digraph D with minimum out-degree at least K contains a subdivision of F. This conjecture remains widely open, even for digraphs F on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomassé studied special cases of Mader’s problem and made the following conjecture: for every ℓ ≥ 2 there exists K = K(ℓ) such that every digraph D with minimum out-degree at least K contains a subdivision of every orientation of a cycle of length ℓ. We prove this conjecture and answer further open questions raised by Aboulker et al.
On connectivity in random graph models with limited dependencies
Lengler, Johannes; Martinsson, Anders; Petrova, Kalina; et al. (2024)
Random Structures & Algorithms
Improved bound for improper colourings of graphs with no odd clique minor
Steiner, Raphael (2023)
Combinatorics, Probability & Computing
Strengthening Hadwiger's conjecture, Gerards and Seymour conjectured in 1995 that every graph with no odd K-t-minor is properly (t - 1)-colourable. This is known as the Odd Hadwiger's conjecture. We prove a relaxation of the above conjecture, namely we show that every graph with no odd K-t-minor admits a vertex (2t - 2)-colouring such that all monochromatic components have size at most inverted right perpendicular1/2 (t - 2)inverted left perpendicular. The bound on the number of colours is optimal up to a factor of 2, improves previous bounds for the same problem by Kawarabayashi (2008, Combin. Probab. Comput. 17 815-821), Kang and Oum (2019, Combin. Probab. Comput. 28 740-754), Liu and Wood (2021, arXiv preprint, arXiv:1905.09495), and strengthens a result by van den Heuvel and Wood (2018, J. Lond. Math. Soc. 98 129-148), who showed that the above conclusion holds under the more restrictive assumption that the graph is K-t-minor-free. In addition, the bound on the component-size in our result is much smaller than those of previous results, in which the dependency on t was given by a function arising from the graph minor structure theorem of Robertson and Seymour. Our short proof combines the method by van den Heuvel and Wood for K-t-minor-free graphs with some additional ideas, which make the extension to odd K-t-minor-free graphs possible.
Fractional Chromatic Number Vs. Hall Ratio
Steiner, Raphael (2025)
Combinatorica
On an Induced Version of Menger's Theorem
Hendrey, Kevin; Norin, Sergey; Steiner, Raphael; et al. (2024)
The Electronic Journal of Combinatorics
We prove Menger-type results in which the obtained paths are pairwise nonadjacent, both for graphs of bounded maximum degree and, more generally, for graphs excluding a topological minor. More precisely, we show the existence of a constant C, depending only on the maximum degree or on the forbidden topological minor, such that for any pair of sets of vertices X, Y and any positive integer k, there exist either k pairwise non-adjacent X-Y-paths, or a set of fewer than Ck vertices which separates X and Y. We further show better bounds in the sub cubic case, and in particular obtain a tight result for two paths using a computer-assisted proof.
Kloosterman sums do not correlate with periodic functions
Steiner, Raphael (2024)
Mathematika
We provide uniform bounds for sums of Kloosterman sums in all arithmetic progressions. As a consequence, we find that Kloosterman sums do not correlate with periodic functions.
Theta functions, fourth moments of eigenforms and the sup-norm problem II
Khayutin, Ilya; Nelson, Paul D.; Steiner, Raphael (2024)
Forum of Mathematics, Pi
Colorings of oriented planar graphs avoiding a monochromatic subgraph
Bergold, Helena; Hochstättler, Winfried; Steiner, Raphael (2022)
Discrete Applied Mathematics
For a fixed simple digraph F and a given simple digraph D, an F-free k-coloring of D is a vertex-coloring in which no induced copy of F in D is monochromatic. We study the complexity of deciding for fixed F and k whether a given simple digraph admits an F-free k-coloring. Our main focus is on the restriction of the problem to planar input digraphs, where it is only interesting to study the cases k ∈ {2, 3}. From known results it follows that for every fixed digraph F whose underlying graph is not a forest, every planar digraph D admits an F-free 2-coloring, and that for every fixed digraph F with ∆(F) ≥ 3, every oriented planar graph D admits an F-free 3-coloring. We show in contrast, that • if F is an orientation of a path of length at least 2, then it is NP-hard to decide whether an acyclic and planar input digraph D admits an F -free 2-coloring. • if F is an orientation of a path of length at least 1, then it is NP-hard to decide whether an acyclic and planar input digraph D admits an F-free 3-coloring.
Colouring Non-Even Digraphs
Garlet Millani, Marcelo; Steiner, Raphael; Wiederrecht, Sebastian (2022)
The Electronic Journal of Combinatorics
A colouring of a digraph as defined by Neumann-Lara in 1982 is a vertex-colouring such that no monochromatic directed cycles exist. The minimal number of colours required for such a colouring of a loopless digraph is defined to be its dichromatic number. This quantity has been widely studied in the last decades and can be considered as a natural directed analogue of the chromatic number of a graph. A digraph D is called even if for every 0-1-weighting of the edges it contains a directed cycle of even total weight. We show that every non-even digraph has dichromatic number at most 2 and an optimal colouring can be found in polynomial time. We strengthen a previously known NP-hardness result by showing that deciding whether a directed graph is 2-colourable remains NP-hard even if it contains a feedback vertex set of bounded size.
Inapproximability of shortest paths on perfect matching polytopes
Cardinal, Jean; Steiner, Raphael (2023)
Mathematical Programming
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 = NP, there is no polynomial-time algorithm that computes a path of constant length between two vertices at distance two of the perfect matching polytope of a bipartite graph. Conditioned on P ≠ NP, this disproves a conjecture by Ito et al. (SIAM J Discrete Math 36(2):1102–1123, 2022). Assuming the Exponential Time Hypothesis we prove the stronger result that there exists no polynomial-time algorithm computing a path of length at most (1/4 - o(1)) log N / log log N between two vertices at distance two of the perfect matching polytope of an N-vertex bipartite graph. These results remain true if the bipartite graph is restricted to be of maximum degree three. The above has the following interesting implication for the performance of pivot rules for the simplex algorithm on simply-structured combinatorial polytopes: If P ≠ NP, then for every simplex pivot rule executable in polynomial time and every constant k ∈ N there exists a linear program on a perfect matching polytope and a starting vertex of the polytope such that the optimal solution can be reached in two monotone non-degenerate steps from the starting vertex, yet the pivot rule will require at least k non-degenerate steps to reach the optimal solution. This result remains true in the more general setting of pivot rules for so-called circuit-augmentation algorithms.

Publications1 - 10 of 38

Raphael Steiner

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results