اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLarge rainbow cliques in randomly perturbed dense graphs
83
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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_{leftlceil s/2 rightrceil})}$; 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_{2ell - 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_{2ell - 1}$. It is worth mentioning that for even cycles, or more generally for any fixed bipartite graph, no random edges are needed at all.
قيم البحث
اقرأ أيضاً
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} pr
operties 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_{leftlceil ell/2 rightrceil})}$, 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.
Given an $n$-vertex graph $G$ with minimum degree at least $d n$ for some fixed $d > 0$, the distribution $G cup mathbb{G}(n,p)$ over the supergraphs of $G$ is referred to as a (random) {sl perturbation} of $G$. We consider the distribution of edge-c
oloured graphs arising from assigning each edge of the random perturbation $G cup mathbb{G}(n,p)$ a colour, chosen independently and uniformly at random from a set of colours of size $r := r(n)$. We prove that such edge-coloured graph distributions a.a.s. admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies $p := p(n) geq C/n$, for some fixed $C > 0$, and $r = (1 + o(1))n$. The number of colours used is clearly asymptotically best possible. In particular, this improves upon a recent result of Anastos and Frieze (2019) in this regard. As an intermediate result, which may be of independent interest, we prove that randomly edge-coloured sparse pseudo-random graphs a.a.s. admit an almost spanning rainbow path.
Maker-Breaker games are played on a hypergraph $(X,mathcal{F})$, where $mathcal{F} subseteq 2^X$ denotes the family of winning sets. Both players alternately claim a predefined amount of edges (called bias) from the board $X$, and Maker wins the game
if she is able to occupy any winning set $F in mathcal{F}$. These games are well studied when played on the complete graph $K_n$ or on a random graph $G_{n,p}$. In this paper we consider Maker-Breaker games played on randomly perturbed graphs instead. These graphs consist of the union of a deterministic graph $G_alpha$ with minimum degree at least $alpha n$ and a binomial random graph $G_{n,p}$. Depending on $alpha$ and Breakers bias $b$ we determine the order of the threshold probability for winning the Hamiltonicity game and the $k$-connectivity game on $G_{alpha}cup G_{n,p}$, and we discuss the $H$-game when $b=1$. Furthermore, we give optimal results for the Waiter-Clie
Given a dense subset $A$ of the first $n$ positive integers, we provide a short proof showing that for $p=omega(n^{-2/3})$ the so-called {sl randomly perturbed} set $A cup [n]_p$ a.a.s. has the property that any $2$-colouring of it has a monochromati
c Schur triple, i.e. a triple of the form $(a,b,a+b)$. This result is optimal since there are dense sets $A$, for which $Acup [n]_p$ does not possess this property for $p=o(n^{-2/3})$.
We determine, up to a multiplicative constant, the optimal number of random edges that need to be added to a $k$-graph $H$ with minimum vertex degree $Omega(n^{k-1})$ to ensure an $F$-factor with high probability, for any $F$ that belongs to a certai
n class $mathcal{F}$ of $k$-graphs, which includes, e.g., all $k$-partite $k$-graphs, $K_4^{(3)-}$ and the Fano plane. In particular, taking $F$ to be a single edge, this settles a problem of Krivelevich, Kwan and Sudakov [Combin. Probab. Comput. 25 (2016), 909--927]. We also address the case in which the host graph $H$ is not dense, indicating that starting from certain such $H$ is essentially the same as starting from an empty graph (namely, the purely random model).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
