Ramsey-goodness -- and otherwise

DOI10.1007/S00493-013-2778-4zbMATH Open1324.05130arXiv1010.5079OpenAlexW2155870908MaRDI QIDQ2259367FDOQ2259367

Authors: Yanyan Li 

Publication date: 3 March 2015

Published in: Combinatorica (Search for Journal in Brave)

Abstract: A celebrated result of Chv'atal, R"odl, Szemer'edi and Trotter states (in slightly weakened form) that, for every natural number $Delta$, there is a constant $r_{D}elta$ such that, for any connected $n$-vertex graph $G$ with maximum degree $Delta$, the Ramsey number $R(G,G)$ is at most $r_{D}eltan$, provided $n$ is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take $r_{D}elta=Delta$. However, Graham, R"odl and Ruci'nski showed, by taking $G$ to be a suitable expander graph, that necessarily $r_{D}elta>2^{cDelta}$ for some constant $c>0$. We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of $G$ be at most some function $$, then $R(G,G)le(2chi(G)+4)nleq(2Delta+6)n$, i.e., $r_{D}elta=2Delta+6$ suffices. On the other hand, we show that Burr's conjecture itself fails even for $P_n^k$, the $k$th power of a path $P_n$. Brandt showed that for any $c$, if $Delta$ is sufficiently large, there are connected $n$-vertex graphs $G$ with $Delta(G)leqDelta$ but $R(G,K_3)>cn$. We show that, given $Delta$ and $H$, there are $$ and $n_0$ such that, if $G$ is a connected graph on $nge{n}_0$ vertices with maximum degree at most $Delta$ and bandwidth at most $$, then we have $R(G,H)=(chi(H)-1)(n-1)+sigma(H)$, where $sigma(H)$ is the smallest size of any part in any $chi(H)$-partition of $H$. We also show that the same conclusion holds without any restriction on the maximum degree of $G$ if the bandwidth of $G$ is at most $epsilon(H)logn/loglogn$.

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

Recommendations

• Ramsey numbers of large books and bipartite graphs with small bandwidth
• Bipartite Ramsey numbers for graphs of small bandwidth
• Ramsey numbers for bipartite graphs with small bandwidth
• Ramsey numbers for bipartite graphs with small bandwidth
• The Ramsey number of a graph with bounded maximum degree

zbMATH Keywords

Ramsey-goodness

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55)

Cites Work

• On maximal paths and circuits of graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some remarks on the theory of graphs
• All Ramsey numbers for cycles in graphs
• Blow-up lemma
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• Covering Two-Edge-Coloured Complete Graphs with Two Disjoint Monochromatic Cycles
• Edge disjoint placement of graphs
• Asymptotic lower bounds for Ramsey functions
• Ramsey Numbers Involving Graphs with Long Suspended Paths
• Title not available (Why is that?)
• Ramsey goodness and beyond
• Ramsey numbers for cycles in graphs
• Hypergraph packing and sparse bipartite Ramsey numbers
• On two problems in graph Ramsey theory
• Radius two trees specify χ‐bounded classes
• On graphs with linear Ramsey numbers
• The Ramsey number of a graph with bounded maximum degree
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Density theorems for bipartite graphs and related Ramsey-type results
• Small Ramsey numbers
• Generalized Ramsey theory for graphs. III: Small off-diagonal numbers
• Generalizations of a Ramsey-theoretic result of chvátal
• On cycle—Complete graph ramsey numbers
• The Cycle-Complete Graph Ramsey Numbers
• On a Ramsey-type problem of J. A. Bondy and P. Erdős. I
• Graphs with linearly bounded Ramsey numbers
• What can we hope to accomplish in generalized Ramsey theory ?
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (32)

• Cycles Are Strongly Ramsey-Unsaturated
• Ramsey numbers of cycles versus general graphs
• Ramsey good graphs with long suspended paths
• RAMSEY’S COHEIRS
• A large tree is \(tK_m\)-good
• Spanning embeddings of arrangeable graphs with sublinear bandwidth
• Ramsey numbers for bipartite graphs with small bandwidth
• Title not available (Why is that?)
• Ramsey numbers of squares of paths
• Title not available (Why is that?)
• Calculating Ramsey numbers by partitioning colored graphs
• On the bandwidth of the Kneser graph
• Ramsey goodness of paths
• Exact Ramsey numbers of odd cycles via nonlinear optimisation
• The Ramsey number of the clique and the hypercube
• Ramsey numbers of large books versus multipartite graphs
• Ramsey numbers of cubes versus cliques
• Degree conditions for Ramsey goodness of paths
• Monochromatic square-cycle and square-path partitions
• The Size Ramsey Number of Graphs with Bounded Treewidth
• Ramsey numbers involving a long path
• The Ramsey number for a forest versus disjoint union of complete graphs
• Monochromatic cycle power partitions
• Ramsey theory and bandwidth of graphs
• Ramsey goodness of cycles
• Ramsey numbers of connected clique matchings
• Three-color Ramsey number of an odd cycle versus bipartite graphs with small bandwidth
• On the Ramsey number of the triangle and the cube
• Ramsey goodness of clique versus paths in random graphs
• Ramsey number of a connected triangle matching
• Ramsey goodness of bounded degree trees
• The Ramsey numbers of squares of paths and cycles

This page was built for publication: Ramsey-goodness -- and otherwise

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