Path Ramsey number for random graphs

DOI10.1017/S0963548315000279zbMATH Open1372.05228arXiv1405.6670OpenAlexW2516261732WikidataQ105585015 ScholiaQ105585015MaRDI QIDQ5366907FDOQ5366907

Authors: Shoham Letzter 

Publication date: 10 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: Answering a question raised by Dudek and Pral{}at, we show that if $pnightarrowinfty$, w.h.p.,~whenever $G=G(n,p)$ is $2$-coloured, there exists a monochromatic path of length $n(2/3+o(1))$. This result is optimal in the sense that $2/3$ cannot be replaced by a larger constant. As part of the proof we obtain the following result which may be of independent interest. We show that given a graph $G$ on $n$ vertices with at least $$ edges, whenever $G$ is $2$-edge-coloured, there is a monochromatic path of length at least $(2/3-100sqrtepsilon)n$. This is an extension of the classical result by Gerencs'er and Gy'arf'as which says that whenever $K_n$ is $2$-coloured there is a monochromatic path of length at least $2n/3$.

Full work available at URL: https://arxiv.org/abs/1405.6670

Recommendations

• On some multicolor Ramsey properties of random graphs
• Monochromatic paths in random tournaments
• Monochromatic paths in random tournaments
• Bipartite Ramsey numbers of paths for random graphs
• Ramsey goodness of clique versus paths in random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Monochromatic cycles in 2-coloured graphs
• Star versus two stripes Ramsey numbers and a conjecture of Schelp
• Title not available (Why is that?)
• On size Ramsey number of paths, trees, and circuits. I
• Paths in graphs
• An alternative proof of the linearity of the size-Ramsey number of paths
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Title not available (Why is that?)
• Szemerédi’s Regularity Lemma for Sparse Graphs
• Combinatorial theorems relative to a random set
• Title not available (Why is that?)

Cited In (36)

• On the size-Ramsey number of tight paths
• Lower bounds of size Ramsey number for graphs with small independence number
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• The size‐Ramsey number of short subdivisions
• The size-Ramsey number of powers of bounded degree trees
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• On the size-Ramsey number of cycles
• On some multicolor Ramsey properties of random graphs
• The size Ramsey number of short subdivisions of bounded degree graphs
• Short proofs for long induced paths
• An alternative proof of the linearity of the size-Ramsey number of paths
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• The size-Ramsey number of powers of bounded degree trees
• Large monochromatic components in expansive hypergraphs
• On the restricted size Ramsey number for a pair of cycles
• Bipartite Ramsey numbers of cycles for random graphs
• Random bipartite Ramsey numbers of long cycles
• Note on the multicolour size-Ramsey number for paths
• On the size-Ramsey number of grid graphs
• The multicolor size-Ramsey numbers of cycles
• Ramsey numbers of trails and circuits
• The size-Ramsey number of 3-uniform tight paths
• Ramsey goodness of trees in random graphs
• On the size Ramsey number of all cycles versus a path
• The multicolour size-Ramsey number of powers of paths
• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• Color‐biased Hamilton cycles in random graphs
• New lower bounds on the size-Ramsey number of a path
• Ordered size Ramsey number of paths
• Stability of the path-path Ramsey number
• Size-Ramsey numbers of cycles versus a path
• On the restricted size Ramsey number involving a path \(P_3\)
• Partitioning random graphs into monochromatic components
• Ramsey goodness of clique versus paths in random graphs
• On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles
• Bipartite Ramsey numbers of paths for random graphs

This page was built for publication: Path Ramsey number for random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5366907)