Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNote on induced paths in sparse random graphs
92
0
0.0
(
0
)
Authors
Stefan Glock
Ask ChatGPT about the research
No Arabic abstract
We show that for $dge d_0(epsilon)$, with high probability, the random graph $G(n,d/n)$ contains an induced path of length $(3/2-epsilon)frac{n}{d}log d$. This improves a result obtained independently by Luczak and Suen in the early 90s, and answers a question of Fernandez de la Vega. Along the way, we generalize a recent result of Cooley, Draganic, Kang and Sudakov who studied the analogous problem for induced matchings.
rate research
Read More
Given a graph $G=(V,E)$ whose vertices have been properly coloured, we say that a path in $G$ is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy-Vitaver Theorem that every properly coloured graph contains a colourful path on $chi(G)$ vertices. We explore a conjecture that states that every properly coloured triangle-free graph $G$ contains an induced colourful path on $chi(G)$ vertices and prove its correctness when the girth of $G$ is at least $chi(G)$. Recent work on this conjecture by Gyarfas and Sarkozy, and Scott and Seymour has shown the existence of a function $f$ such that if $chi(G)geq f(k)$, then an induced colourful path on $k$ vertices is guaranteed to exist in any properly coloured triangle-free graph $G$.
Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, ODonnel, Tamuz and Tan conjectured that, in the ErdH{o}s--Renyi random graph $G(n,p)$, the random initial $pm 1$-assignment converges to a $99%$-agreement with high probability whenever $p=omega(1/n)$. This conjecture was first confirmed for $pgeqlambda n^{-1/2}$ for a large constant $lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p< lambda n^{-1/2}$. We break this $Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $lambda n^{-3/5}log n leq p leq lambda n^{-1/2}$ with a large constant $lambda>0$.
An edge-ordering of a graph $G=(V,E)$ is a bijection $phi:Eto{1,2,...,|E|}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,...,e_k$ is an increasing path if it is a path in $G$ which satisfies $phi(e_i)<phi(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $ell$ such that every edge-ordering of $G$ contains an increasing path of length $ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.
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 show that for any $d=d(n)$ with $d_0(epsilon) le d =o(n)$, with high probability, the size of a largest induced cycle in the random graph $G(n,d/n)$ is $(2pm epsilon)frac{n}{d}log d$. This settles a long-standing open problem in random graph theory.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
