On the minimum degree of minimal Ramsey graphs for multiple colours

DOI10.1016/J.JCTB.2016.03.006zbMATH Open1337.05076arXiv1502.02881OpenAlexW1864971073MaRDI QIDQ290809FDOQ290809

Jacob Fox, Tibor Szabó, Andrey Grinshpun, Yury Person, Anita Liebenau

Publication date: 3 June 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: A graph G is r-Ramsey for a graph H, denoted by G ightarrow (H)_r, if every r-colouring of the edges of G contains a monochromatic copy of H. The graph G is called r-Ramsey-minimal for H if it is r-Ramsey for H but no proper subgraph of G possesses this property. Let s_r(H) denote the smallest minimum degree of G over all graphs G that are r-Ramsey-minimal for H. The study of the parameter s_2 was initiated by Burr, ErdH{o}s, and Lov'{a}sz in 1976 when they showed that for the clique s_2(K_k)=(k-1)^2. In this paper, we study the dependency of s_r(K_k) on r and show that, under the condition that k is constant, s_r(K_k) = r^2 polylog r. We also give an upper bound on s_r(K_k) which is polynomial in both r and k, and we determine s_r(K_3) up to a factor of log r.

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

zbMATH Keywords

minimum degreeRamsey theory[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Rogers+function&go=Go Erd��s-Rogers function]minimal Ramsey graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55)

Cites Work

• The size Ramsey number
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On size Ramsey number of paths, trees, and circuits. I
• Some remarks on the theory of graphs
• On size Ramsey numbers of graphs with bounded degree
• The triangle-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• A note on the independence number of triangle-free graphs
• A note on Ramsey numbers
• On the use of senders in generalized Ramsey theory for graphs
• Graphs without large triangle free subgraphs
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Ramsey's theorem - a new lower bound
• Asymptotic lower bounds for Ramsey functions
• Constructive lower bounds on classical multicolor Ramsey numbers
• The minimum degree of Ramsey-minimal graphs
• On Ramsey Minimal Graphs
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• Upper bounds for ramsey numbers R(3, 3, ?, 3) and Schur numbers
• On generalized Ramsey numbers of Erdős and Rogers
• On the independence number of sparse graphs
• Dynamic concentration of the triangle-free process
• On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs
• The Construction of Certain Graphs
• The size-Ramsey number of trees
• On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
• A new upper bound for diagonal Ramsey numbers

Cited In (12)

• Vertex Folkman Numbers and the Minimum Degree of Minimal Ramsey Graphs
• Packing nearly optimal Ramsey \(R(3,t)\) graphs
• On minimal Ramsey graphs and Ramsey equivalence in multiple colours
• The minimum degree of minimal Ramsey graphs for cliques
• Two problems in graph Ramsey theory
• On the use of senders for asymmetric tuples of cliques in Ramsey theory
• Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs
• What is Ramsey-equivalent to a clique?
• Minimal Ramsey Graphs with Many Vertices of Small Degree
• Saturation numbers for Ramsey-minimal graphs
• On Ramsey-minimal infinite graphs
• On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles

This page was built for publication: On the minimum degree of minimal Ramsey graphs for multiple colours

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