Proceedings of the American Mathematical Society · 1972 · 72 citations · 6 references
Natural SciencesMathematicsCombinatoricsDiscrete MathematicsTopologyDirected Acyclic GraphsGeometric GraphsGraph AlgorithmsGraph TheoryRamsey TheoryAnnotation EncodingDiagonal Ramsey NumbersRamsey AlgebrasRamsey GraphsRamsey Property
Consider a finite nonnull graph <italic>G</italic> with no loops or multiple edges and no isolated points. Its <italic>Ramsey number</italic> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis upper G right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>G</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r(G)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is defined as the minimum number <italic>p</italic> such that every 2-coloring of the lines of the complete graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K Subscript p"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>p</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{K_p}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> must contain a monochromatic <italic>G</italic> . This generalizes the classical diagonal Ramsey numbers <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r left-parenthesis n comma n right-parenthesis equals r left-parenthesis upper K Subscript n Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>,</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">r(n,n) = r({K_n})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We obtain the exact value of the Ramsey number of every such graph with at most four points.
6