Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMonochromatic Schur triples in randomly perturbed dense sets of integers
127
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 monochromatic 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})$.
rate research
Read More
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-coloured 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.
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} 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_{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.
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 certain 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).
The dynamics of escape from an attractive state due to random perturbations is of central interest to many areas in science. Previous studies of escape in chaotic systems have rather focused on the case of unbounded noise, usually assumed to have Gaussian distribution. In this paper, we address the problem of escape induced by bounded noise. We show that the dynamics of escape from an attractors basin is equivalent to that of a closed system with an appropriately chosen hole. Using this equivalence, we show that there is a minimum noise amplitude above which escape takes place, and we derive analytical expressions for the scaling of the escape rate with noise amplitude near the escape transition. We verify our analytical predictions through numerical simulations of a two-dimensional map with noise.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
