On the minimum degree of minimal Ramsey graphs for multiple colours

DOI10.1016/J.JCTB.2016.03.006MaRDI QIDQ290809zbMATH OpenOpenAlexFDO

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

Publication date 3 June 2016

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

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

zbMATH Keywords

minimum degreeRamsey theoryminimal Ramsey graphsErdős-Rogers function

Mathematics Subject Classification ID

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

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.

Recommendations

• The minimum degree of minimal Ramsey graphs for cliques
• Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs
• The minimum degree of Ramsey-minimal graphs
• Vertex Folkman numbers and the minimum degree of minimal Ramsey graphs
• On Ramsey Minimal Graphs

Cites work

• scientific article; zbMATH DE number 16104 (Why is no real title available?)
• scientific article; zbMATH DE number 3520447 (Why is no real title available?)
• K^s-Free Graphs Without Large K^r-Free Subgraphs
• A new upper bound for diagonal Ramsey numbers
• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• Asymptotic lower bounds for Ramsey functions
• Constructive lower bounds on classical multicolor Ramsey numbers
• Dynamic concentration of the triangle-free process
• Extremal graphs with no \(C^{4,}\)s, \(C^{6,}\)s, or \(C^{10,}\)s
• Graphs without large triangle free subgraphs
• On Ramsey Minimal Graphs
• On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
• On generalized Ramsey numbers for 3-uniform hypergraphs
• On generalized Ramsey numbers of Erdős and Rogers
• On size Ramsey number of paths, trees, and circuits. I
• On size Ramsey numbers of graphs with bounded degree
• On the independence number of sparse graphs
• On the use of senders in generalized Ramsey theory for graphs
• Ramsey's theorem - a new lower bound
• Some remarks on the theory of graphs
• The Construction of Certain Graphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The minimum degree of Ramsey-minimal graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The size Ramsey number
• The size-Ramsey number of trees
• The triangle-free process
• Upper bounds for ramsey numbers R(3, 3, ?, 3) and Schur numbers

Cited in

(16)

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

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)