Source author record

Oran Danon

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Large rainbow cliques in randomly perturbed dense graphs

For two graphs $G$ and $H$ , write $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ if $G$ has the property that every {\sl proper} colouring of its edges yields a {\sl rainbow} copy of $H$ . We study the thresholds for such so-called {\sl anti-Ramsey} properties in randomly perturbed dense graphs, which are unions of the form $G \cup \mathbb{G}(n,p)$ , where $G$ is an $n$ -vertex graph with edge-density at least $d$ , and $d$ is a constant that does not depend on $n$ . Our results in this paper, combined with our results in a companion paper, determine the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} K_s$ for every $s$ . In this paper, we show that for $s \geq 9$ the threshold is $n^{-1/m_2(K_{\left\lceil s/2 \right\rceil})}$ ; in fact, our $1$ -statement is a supersaturation result. This turns out to (almost) be the threshold for $s=8$ as well, but for every $4 \leq s \leq 7$ , the threshold is lower; see our companion paper for more details. In this paper, we also consider the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} C_{2\ell - 1}$ , and show that the threshold for this property is $n^{-2}$ for every $\ell \geq 2$ ; in particular, it does not depend on the length of the cycle $C_{2\ell - 1}$ . It is worth mentioning that for even cycles, or more generally for any fixed bipartite graph, no random edges are needed at all.

preprint2022arXiv

Small rainbow cliques in randomly perturbed dense graphs

For two graphs $G$ and $H$ , write $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ if $G$ has the property that every \emph{proper} colouring of its edges yields a \emph{rainbow} copy of $H$ . We study the thresholds for such so-called \emph{anti-Ramsey} properties in randomly perturbed dense graphs, which are unions of the form $G \cup \mathbb{G}(n,p)$ , where $G$ is an $n$ -vertex graph with edge-density at least $d >0$ , and $d$ is independent of $n$ . In a companion article, we proved that the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} K_\ell$ is $n^{-1/m_2(K_{\left\lceil \ell/2 \right\rceil})}$ , whenever $\ell \geq 9$ . For smaller $\ell$ , the thresholds behave more erratically, and for $4 \le \ell \le 7$ they deviate downwards significantly from the aforementioned aesthetic form capturing the thresholds for \emph{large} cliques. In particular, we show that the thresholds for $\ell \in \{4, 5, 7\}$ are $n^{-5/4}$ , $n^{-1}$ , and $n^{-7/15}$ , respectively. For $\ell \in \{6, 8\}$ we determine the threshold up to a $(1 + o(1))$ -factor in the exponent: they are $n^{-(2/3 + o(1))}$ and $n^{-(2/5 + o(1))}$ , respectively. For $\ell = 3$ , the threshold is $n^{-2}$ ; this follows from a more general result about odd cycles in our companion paper.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.