Path Ramsey number for random graphs

DOI10.1017/S0963548315000279MaRDI QIDQ5366907zbMATH OpenOpenAlexWikidataFDO

Authors Shoham Letzter

Publication date 10 October 2017

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

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

Mathematics Subject Classification ID

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

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$.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3961650 (Why is no real title available?)
• scientific article; zbMATH DE number 3724483 (Why is no real title available?)
• scientific article; zbMATH DE number 16104 (Why is no real title available?)
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• An alternative proof of the linearity of the size-Ramsey number of paths
• Combinatorial theorems relative to a random set
• Monochromatic cycles in 2-coloured graphs
• On size Ramsey number of paths, trees, and circuits. I
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Paths in graphs
• Star versus two stripes Ramsey numbers and a conjecture of Schelp
• Szemerédi’s Regularity Lemma for Sparse Graphs

Cited in

(36)

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