On some multicolor Ramsey properties of random graphs

DOI10.1137/16M1069717MaRDI QIDQ5357963zbMATH OpenOpenAlexFDO

Authors Andrzej Dudek, Paweł Prałat

Publication date 18 September 2017

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graphssize-Ramsey numbermonochromatic components and paths

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: The size-Ramsey number $hatR(F)$ of a graph $F$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges with the property that any colouring of the edges of $G$ with two colours yields a monochromatic copy of $F$. In this paper, first we focus on the size-Ramsey number of a path $P_n$ on $n$ vertices. In particular, we show that $5n/2-15/2lehatR(P_n)le74n$ for $n$ sufficiently large. (The upper bound uses expansion properties of random $d$-regular graphs.) This improves the previous lower bound, $hatR(P_n)ge(1+sqrt2)n-O(1)$, due to Bollob'as, and the upper bound, $hatR(P_n)le91n$, due to Letzter. Next we study long monochromatic paths in edge-coloured random graph $G(n,p)$ with $pnoinfty$. Let $alpha>0$ be an arbitrarily small constant. Recently, Letzter showed that a.a.s. any $2$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(2/3-alpha)n$, which is optimal. Extending this result, we show that a.a.s. any $3$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(1/2-alpha)n$, which is also optimal. In general, we prove that for $rge4$ a.a.s. any $r$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(1/r-alpha)n$. We also consider a related problem and show that for any $rge2$, a.a.s. any $r$-edge colouring of $G(n,p)$ yields a monochromatic connected subgraph on $(1/(r-1)-alpha)n$ vertices, which is also tight.

Recommendations

• Path Ramsey number for random graphs
• New lower bounds on the size-Ramsey number of a path
• scientific article; zbMATH DE number 16104

Cites work

• scientific article; zbMATH DE number 3961650 (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 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• scientific article; zbMATH DE number 3334898 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• An alternative proof of the linearity of the size-Ramsey number of paths
• Coloring the edges of a random graph without a monochromatic giant component
• Combinatorial theorems relative to a random set
• Corrigendum. Three-color Ramsey numbers for paths
• Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
• Highly connected monochromatic subgraphs of multicolored graphs
• Introduction to Random Graphs
• Long cycles in locally expanding graphs, with applications
• Long cycles in subgraphs of (pseudo)random directed graphs
• Maximum degree and fractional matchings in uniform hypergraphs
• On a problem of K. Zarankiewicz
• On generalized Ramsey numbers for trees
• On maximal paths and circuits of graphs
• On size Ramsey number of paths, trees, and circuits. I
• On the combinatorial problems which I would most like to see solved
• On the multi-colored Ramsey numbers of paths and even cycles
• On the resilience of long cycles in random graphs
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• Path Ramsey number for random graphs
• Path Ramsey numbers in multicolorings
• Ramsey games with giants
• Random graphs.
• Sandwiching random graphs: universality between random graph models
• Szemerédi's regularity Lemma for matrices and sparse graphs
• Szemerédi’s Regularity Lemma for Sparse Graphs
• The Ramsey number for a triple of long even cycles
• The size Ramsey number of a directed path
• Three-color Ramsey numbers for paths

Cited in

(37)

• Large monochromatic components in edge colored graphs with a minimum degree condition
• On the size-Ramsey number of tight paths
• A lower bound on the multicolor size-Ramsey numbers of paths in hypergraphs
• Lower bounds of size Ramsey number for graphs with small independence number
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• Path Ramsey number for random graphs
• An analogue of the Erdős-Gallai theorem for random graphs
• The size‐Ramsey number of short subdivisions
• Size Ramsey number of bipartite graphs and bipartite Ramanujan graphs
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• The size-Ramsey number of powers of bounded degree trees
• On the size-Ramsey number of cycles
• Short proofs for long induced paths
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• The size-Ramsey number of powers of bounded degree trees
• Long cycles in locally expanding graphs, with applications
• Large monochromatic components in expansive hypergraphs
• A Ramsey property of random regular and \(k \)-out graphs
• A strengthening of the Erdős-Szekeres theorem
• On the restricted size Ramsey number for a pair of cycles
• Bipartite Ramsey numbers of cycles for random graphs
• Note on the multicolour size-Ramsey number for paths
• Random bipartite Ramsey numbers of long cycles
• On edge-ordered Ramsey numbers
• On the size-Ramsey number of grid graphs
• The multicolor size-Ramsey numbers of cycles
• The size-Ramsey number of 3-uniform tight paths
• 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
• New lower bounds on the size-Ramsey number of a path
• Stability of the path-path Ramsey number
• Ordered size Ramsey number of paths
• Color‐biased Hamilton cycles in random graphs
• Size-Ramsey numbers of cycles versus a path
• Ramsey goodness of clique versus paths in random graphs
• Bipartite Ramsey numbers of paths for random graphs

This page was built for publication: On some multicolor Ramsey properties of random graphs

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