List coloring triangle‐free hypergraphs. Issue 3 (11th June 2014)

• Record Type: Journal Article
• Authors: Cooper, Jeff; Mubayi, Dhruv
• Is Part Of: Random structures & algorithms. Volume 47:Issue 3(2015)
• Page Start: 487
• Page End: 519
• Publication Date: 2014-06-11
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20552
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>A triangle in a hypergraph is a collection of distinct vertices <italic>u, v, w</italic> and distinct edges <italic>e, f, g</italic> with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw8cg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>u</mml:mi><mml:mo>, </mml:mo><mml:mi>v</mml:mi><mml:mo>∈</mml:mo><mml:mi>e</mml:mi><mml:mo>, </mml:mo><mml:mo> </mml:mo><mml:mi>v</mml:mi><mml:mo>, </mml:mo><mml:mi>w</mml:mi><mml:mo>∈</mml:mo><mml:mi>f</mml:mi></mml:mrow></mml:math></alternatives></inline-formula>, <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw89c" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>w</mml:mi><mml:mo>, </mml:mo><mml:mi>u</mml:mi><mml:mo>∈</mml:mo><mml:mi>g</mml:mi></mml:mrow></mml:math></alternatives></inline-formula> and <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw8bx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>{</mml:mo><mml:mi>u</mml:mi><mml:mo>, </mml:mo><mml:mi>v</mml:mi><mml:mo>, </mml:mo><mml:mi>w</mml:mi><mml:mo>}</mml:mo><mml:mo>∩</mml:mo><mml:mi>e</mml:mi><mml:mo>∩</mml:mo><mml:mi>f</mml:mi><mml:mo>∩</mml:mo><mml:mi>g</mml:mi><mml:mo>=</mml:mo><mml:mo>∅</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. Johansson [Tech. report (1996)] proved that every triangle‐free graph with maximum degree Δ has list chromatic number <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7h5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mo>Δ</mml:mo><mml:mo>/</mml:mo><mml:mi>log</mml:mi><mml:mo>Δ</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. Frieze and Mubayi (Electron J Comb 15 (2008), 27) proved that every <italic>linear</italic> (meaning that every two edges share at most one vertex) triangle‐free triple system with maximum degree Δ has chromatic number <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7gm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msqrt><mml:mrow><mml:mo>Δ</mml:mo><mml:mo>/</mml:mo><mml:mi>log</mml:mi><mml:mo>Δ</mml:mo></mml:mrow></mml:msqrt><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. The restriction to linear triple systems was crucial to their proof.</p> <p>We provide a common generalization of both these results for rank 3 hypergraphs (edges have size 2 or 3). Our result removes the <italic>linear</italic> restriction from <xref ref-type="link" rid="rsa20552-bib-0008">8</xref>, while reducing to the (best possible) result [Johansson, Tech. report (1996)] for graphs. In addition, our result provides a positive answer to a restricted version of a question of Ajtai Erdős, Komlós, and Szemerédi (combinatorica 1 (1981), 313–317) concerning sparse 3‐uniform hypergraphs.</p> <p>As an application, we prove that if <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7f2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mn>3</mml:mn></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> is the collection of 3‐uniform triangles, then the Ramsey number <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7dh" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>R</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:msubsup><mml:mi>K</mml:mi><mml:mi>t</mml:mi><mml:mn>3</mml:mn></mml:msubsup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> satisfies <disp-formula content-type="mathematics" id="rsa20552-disp-0001"><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7nc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="block" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mfrac><mml:mrow><mml:mi>a</mml:mi><mml:msup><mml:mi>t</mml:mi><mml:mrow><mml:mn>3</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mi>t</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mrow><mml:mn>3</mml:mn><mml:mo>/</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:mfrac><mml:mo>≤</mml:mo><mml:mi>R</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi mathvariant="script">C</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:msubsup><mml:mi>K</mml:mi><mml:mi>t</mml:mi><mml:mn>3</mml:mn></mml:msubsup><mml:mo stretchy="false">)</mml:mo><mml:mo>≤</mml:mo><mml:mfrac><mml:mrow><mml:mi>b</mml:mi><mml:msup><mml:mi>t</mml:mi><mml:mrow><mml:mn>3</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mi>t</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup></mml:mrow></mml:mfrac></mml:mrow></mml:math></alternatives></disp-formula> for some positive constants <italic>a</italic> and <italic>b</italic>. The upper bound makes progress towards the recent conjecture of Kostochka, Mubayi, and Verstraëte (J Comb Theory Ser A 120 (2013), 1491–1507) that <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tw7mt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20552:rsa20552-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>R</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msub><mml:mi>C</mml:mi><mml:mn>3</mml:mn></mml:msub><mml:mo>, </mml:mo><mml:msubsup><mml:mi>K</mml:mi><mml:mi>t</mml:mi><mml:mn>3</mml:mn></mml:msubsup><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>o</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>t</mml:mi><mml:mrow><mml:mn>3</mml:mn><mml:mo>/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> where <italic>C</italic><sub>3</sub> is the linear triangle. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 487–519, 2015</p> </abstract>