What is Ramsey-equivalent to a clique?

DOI10.1016/J.JCTB.2014.06.003zbMATH Open1301.05226arXiv1312.0299OpenAlexW2028276181MaRDI QIDQ462928FDOQ462928

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

Publication date: 22 October 2014

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

Abstract: A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H' are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H'. In this paper, we study the problem of determining which graphs are Ramsey-equivalent to the complete graph K_k. A famous theorem of Nesetril and Rodl implies that any graph H which is Ramsey-equivalent to K_k must contain K_k. We prove that the only connected graph which is Ramsey-equivalent to K_k is itself. This gives a negative answer to the question of Szabo, Zumstein, and Zurcher on whether K_k is Ramsey-equivalent to K_k.K_2, the graph on k+1 vertices consisting of K_k with a pendent edge. In fact, we prove a stronger result. A graph G is Ramsey minimal for a graph H if it is Ramsey for H but no proper subgraph of G is Ramsey for H. Let s(H) be the smallest minimum degree over all Ramsey minimal graphs for H. The study of s(H) was introduced by Burr, Erdos, and Lovasz, where they show that s(K_k)=(k-1)^2. We prove that s(K_k.K_2)=k-1, and hence K_k and K_k.K_2 are not Ramsey-equivalent. We also address the question of which non-connected graphs are Ramsey-equivalent to K_k. Let f(k,t) be the maximum f such that the graph H=K_k+fK_t, consisting of K_k and f disjoint copies of K_t, is Ramsey-equivalent to K_k. Szabo, Zumstein, and Zurcher gave a lower bound on f(k,t). We prove an upper bound on f(k,t) which is roughly within a factor 2 of the lower bound.

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

Recommendations

• Ramsey equivalence of \(K_n\) and \(K_n+K_{n-1}\)
• Conditions on Ramsey nonequivalence
• On minimal Ramsey graphs and Ramsey equivalence in multiple colours
• On Ramsey minimal graphs
• The minimum degree of Ramsey-minimal graphs

zbMATH Keywords

graph Ramsey theoryminimal Ramsey graphsRamsey-equivalence

Mathematics Subject Classification ID

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

Cites Work

• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Some remarks on the theory of graphs
• On the minimum degree of minimal Ramsey graphs for multiple colours
• The minimum degree of Ramsey-minimal graphs
• A new upper bound for diagonal Ramsey numbers
• On chromatic number of graphs and set-systems
• The Ramsey property for graphs with forbidden complete subgraphs
• On the minimum degree of minimal Ramsey graphs

Cited In (14)

• Minimal Ramsey graphs with many vertices of small degree
• Ramsey Equivalence for Asymmetric Pairs of Graphs
• On minimal Ramsey graphs and Ramsey equivalence in multiple colours
• Chromatic number is Ramsey distinguishing
• On the use of senders for asymmetric tuples of cliques in Ramsey theory
• Minimum degrees and codegrees of minimal Ramsey 3-uniform hypergraphs
• Minimum degrees and codegrees of Ramsey-minimal 3-uniform hypergraphs
• The Size Ramsey Number of Graphs with Bounded Treewidth
• Mini-workshop: Positional games. Abstracts from the mini-workshop held September 30 -- October 6, 2018
• Minimal ordered Ramsey graphs
• How many cliques can a clique cover cover?
• Ramsey equivalence of \(K_n\) and \(K_n+K_{n-1}\)
• On the Minimum Degree of Minimal Ramsey Graphs for Cliques Versus Cycles
• Conditions on Ramsey nonequivalence

This page was built for publication: What is Ramsey-equivalent to a clique?

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