Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPositional games on randomly perturbed graphs
101
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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
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).
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})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
