On some multicolor Ramsey properties of random graphs

DOI10.1137/16M1069717zbMATH Open1370.05211arXiv1601.02564OpenAlexW2963265343MaRDI QIDQ5357963FDOQ5357963

Authors: Andrzej Dudek, Paweł Prałat 

Publication date: 18 September 2017

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (37)

• On the size-Ramsey number of tight paths
• Large monochromatic components in edge colored graphs with a minimum degree condition
• 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
• Path Ramsey number for random graphs
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• 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
• 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
• 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
• Large monochromatic components in expansive hypergraphs
• Long cycles in locally expanding graphs, with applications
• A Ramsey property of random regular and \(k \)-out graphs
• On the restricted size Ramsey number for a pair of cycles
• A strengthening of the Erdős-Szekeres theorem
• 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 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
• 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
• 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)