Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpanning $F$-cycles in random graphs
130
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We extend a recent argument of Kahn, Narayanan and Park (Proceedings of the AMS, to appear) about the threshold for the appearance of the square of a Hamilton cycle to other spanning structures. In particular, for any spanning graph, we give a sufficient condition under which we may determine its threshold. As an application, we find the threshold for a set of cyclically ordered copies of $C_4$ that span the entire vertex set, so that any two consecutive copies overlap in exactly one edge and all overlapping edges are disjoint. This answers a question of Frieze. We also determine the threshold for edge-overlapping spanning $K_r$-cycles.
rate research
Read More
We show that, in almost every $n$-vertex random directed graph process, a copy of every possible $n$-vertex oriented cycle will appear strictly before a directed Hamilton cycle does, except of course for the directed cycle itself. Furthermore, given an arbitrary $n$-vertex oriented cycle, we determine the sharp threshold for its appearance in the binomial random directed graph. These results confirm, in a strong form, a conjecture of Ferber and Long.
The bandwidth theorem [Mathematische Annalen, 343(1):175--205, 2009] states that any $n$-vertex graph $G$ with minimum degree $(frac{k-1}{k}+o(1))n$ contains all $n$-vertex $k$-colourable graphs $H$ with bounded maximum degree and bandwidth $o(n)$. In [arXiv:1612.00661] a random graph analogue of this statement is proved: for $pgg (frac{log n}{n})^{1/Delta}$ a.a.s. each spanning subgraph $G$ of $G(n,p)$ with minimum degree $(frac{k-1}{k}+o(1))pn$ contains all $n$-vertex $k$-colourable graphs $H$ with maximum degree $Delta$, bandwidth $o(n)$, and at least $C p^{-2}$ vertices not contained in any triangle. This restriction on vertices in triangles is necessary, but limiting. In this paper we consider how it can be avoided. A special case of our main result is that, under the same conditions, if additionally all vertex neighbourhoods in $G$ contain many copies of $K_Delta$ then we can drop the restriction on $H$ that $Cp^{-2}$ vertices should not be in triangles.
Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C={c_1,c_2,ldots,c_r}$, we define the Hamilton cycle color profile $hcp(G)$ to be the set of vectors $(m_1,m_2,ldots,m_r)in [0,n]^r$ such that there exists a Hamilton cycle that is the concatenation of $r$ paths $P_1,P_2,ldots,P_r$, where $P_i$ contains $m_i$ edges. We study $hcp(G_{n,p})$ when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when $hcp(G_{n,p})={(m_1,m_2,ldots,m_r)in [0,n]^r:m_1+m_2+cdots+m_r=n}$.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
We prove that for each $Dge 2$ there exists $c>0$ such that whenever $ble cbig(tfrac{n}{log n}big)^{1/D}$, in the $(1:b)$ Maker-Breaker game played on $E(K_n)$, Maker has a strategy to guarantee claiming a graph $G$ containing copies of all graphs $H$ with $v(H)le n$ and $Delta(H)le D$. We show further that the graph $G$ guaranteed by this strategy also contains copies of any graph $H$ with bounded maximum degree and degeneracy at most $tfrac{D-1}{2}$. This lower bound on the threshold bias is sharp up to the $log$-factor when $H$ consists of $tfrac{n}{3}$ vertex-disjoint triangles or $tfrac{n}{4}$ vertex-disjoint $K_4$-copies.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
