Ramsey Results for Cycle Spectra. Issue 2 (4th December 2012)

• Record Type: Journal Article
• Authors: Brandt, Stephan; Joos, Felix; Müttel, Janina; Rautenbach, Dieter
• Is Part Of: Journal of graph theory. Volume 74:Issue 2(2013)
• Page Start: 210
• Page End: 215
• Publication Date: 2012-12-04
• Subjects: Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.21704
• Languages: English
• ISSNs: 0364-9024

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28rj6" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">C</mml:mi><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives> denote the set of lengths of cycles of a graph <italic>G</italic> of order <italic>n</italic> and let <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28rrh" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mover><mml:mi>G</mml:mi><mml:mo>¯</mml:mo></mml:mover></mml:math></alternatives> denote the complement of <italic>G</italic>. We show that if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28rpd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>n</mml:mi><mml:mo>≥</mml:mo><mml:mn>6</mml:mn></mml:mrow></mml:math></alternatives>, then <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28rwq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">C</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>∪</mml:mo><mml:mi mathvariant="script">C</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mover><mml:mi>G</mml:mi><mml:mo>¯</mml:mo></mml:mover><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives> contains all odd ℓ with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28rv5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>3</mml:mn><mml:mo>≤</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>≤</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mi>o</mml:mi></mml:msub></mml:mrow></mml:math></alternatives> and all even ℓ with <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28s0w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>4</mml:mn><mml:mo>≤</mml:mo><mml:mi>ℓ</mml:mi><mml:mo>≤</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mi>e</mml:mi></mml:msub></mml:mrow></mml:math></alternatives>, where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28rzt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>c</mml:mi><mml:mi>o</mml:mi></mml:msub></mml:math></alternatives> and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28s20" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>c</mml:mi><mml:mi>e</mml:mi></mml:msub></mml:math></alternatives> denote the maximum odd and the maximum even integer in <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28s1f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">C</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>∪</mml:mo><mml:mi mathvariant="script">C</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mover><mml:mi>G</mml:mi><mml:mo>¯</mml:mo></mml:mover><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives>, respectively. From this we deduce that the set <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28njn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi mathvariant="script">C</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>G</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mo>∪</mml:mo><mml:mi mathvariant="script">C</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mover><mml:mi>G</mml:mi><mml:mo>¯</mml:mo></mml:mover><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math></alternatives> contains at least <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg37c28nbb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:03649024:media:jgt21704:jgt21704-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mfenced open="⌈" close="⌉"><mml:mfrac><mml:mrow><mml:mn>2</mml:mn><mml:mi>n</mml:mi></mml:mrow><mml:mn>3</mml:mn></mml:mfrac></mml:mfenced><mml:mo>−</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></alternatives> integers, which is sharp.</p> </abstract>