We gratefully acknowledge support from
the Simons Foundation and member institutions.
Full-text links:

Download:

Current browse context:

math.CO

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo

Mathematics > Combinatorics

Title: Rainbow Hamiltonicity in uniformly coloured perturbed digraphs

Abstract: We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed digraph. We show that for every $\delta \in (0,1)$ there exists $C = C(\delta) > 0$ such that the following holds. Let $D_0$ be an $n$-vertex digraph with minimum semidegree at least $\delta n$ and suppose that each edge of the union of $D_0$ with the random digraph $D(n, p)$ on the same vertex set gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $D_0 \cup D(n, p)$ has a rainbow directed Hamilton cycle.
This improves a result of Aigner-Horev and Hefetz (2021) who proved the same in the undirected setting when the edges are coloured uniformly in a set of $(1 + \varepsilon)n$ colours.
Comments: Incorporated referee's comments. Accepted for publication in Combinatorics, Probability and Computing
Subjects: Combinatorics (math.CO)
Cite as: arXiv:2304.09155 [math.CO]
  (or arXiv:2304.09155v3 [math.CO] for this version)

Submission history

From: Kyriakos Katsamaktsis [view email]
[v1] Tue, 18 Apr 2023 17:49:57 GMT (136kb,D)
[v2] Fri, 27 Oct 2023 17:05:31 GMT (462kb,D)
[v3] Wed, 27 Mar 2024 12:31:01 GMT (184kb,D)

Link back to: arXiv, form interface, contact.