On independent sets in hypergraphs1. Issue 2 (2nd August 2012)

• Record Type: Journal Article
• Authors: Kostochka, Alexandr; Mubayi, Dhruv; Verstraëte, Jacques
• Is Part Of: Random structures & algorithms. Volume 44:Issue 2(2014)
• Page Start: 224
• Page End: 239
• Publication Date: 2012-08-02
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20453
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>The <italic>independence number</italic><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrvg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>α</mml:mo><mml:mo>(</mml:mo><mml:mi>H</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives> of a hypergraph <italic>H</italic> is the size of a largest set of vertices containing no edge of <italic>H</italic>. In this paper, we prove that if <italic>H</italic><sub><italic>n</italic></sub> is an <italic>n</italic>‐vertex <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrtx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>(</mml:mo><mml:mi>r</mml:mi><mml:mo>+</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math></alternatives>‐uniform hypergraph in which every <italic>r</italic>‐element set is contained in at most <italic>d</italic> edges, where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrsc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>0</mml:mn><mml:mo><</mml:mo><mml:mi>d</mml:mi><mml:mo><</mml:mo><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mi>log</mml:mi><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow><mml:mrow><mml:mn>3</mml:mn><mml:msup><mml:mi>r</mml:mi><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:msup></mml:mrow></mml:math></alternatives>, then <disp-formula content-type="mathematics" id="rsa20453-disp-0001"><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrq8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="block" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>α</mml:mo><mml:mo>(</mml:mo><mml:msub><mml:mi>H</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>)</mml:mo><mml:mo>≥</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mi>r</mml:mi></mml:msub><mml:msup><mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mfrac><mml:mi>n</mml:mi><mml:mi>d</mml:mi></mml:mfrac><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mfrac><mml:mi>n</mml:mi><mml:mi>d</mml:mi></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>r</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></alternatives></disp-formula> where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrrt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mi>r</mml:mi></mml:msub><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives> satisfies <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrn5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>c</mml:mi><mml:mi>r</mml:mi></mml:msub><mml:mo>∼</mml:mo><mml:mi>r</mml:mi><mml:mo>/</mml:mo><mml:mi>e</mml:mi></mml:mrow></mml:math></alternatives> as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrpq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:math></alternatives>. The value of <italic>c</italic><sub><italic>r</italic></sub> improves and generalizes several earlier results that all use a theorem of Ajtai, Komlós, Pintz, Spencer and Szemerédi (J Comb Theory Ser A 32 (1982), 321–335). Our relatively short proof extends a method due to Shearer (Random Struct Algorithms 7 (1995), 269–271) and Alon (Random Struct Algorithms 9 (1996), 271–278). The above statement is close to best possible, in the sense that for each <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrk2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>≥</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math></alternatives> and all values of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrmm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>d</mml:mi><mml:mo>∈</mml:mo><mml:mo>ℕ</mml:mo></mml:mrow></mml:math></alternatives>, there are infinitely many <italic>H</italic><sub><italic>n</italic></sub> such that <disp-formula content-type="mathematics" id="rsa20453-disp-0002"><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vs6h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="block" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0010" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>α</mml:mo><mml:mo>(</mml:mo><mml:msub><mml:mi>H</mml:mi><mml:mi>n</mml:mi></mml:msub><mml:mo>)</mml:mo><mml:mo>≤</mml:mo><mml:msub><mml:mi>b</mml:mi><mml:mi>r</mml:mi></mml:msub><mml:msup><mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mfrac><mml:mi>n</mml:mi><mml:mi>d</mml:mi></mml:mfrac><mml:mi>log</mml:mi><mml:mo>⁡</mml:mo><mml:mfrac><mml:mi>n</mml:mi><mml:mi>d</mml:mi></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow></mml:mrow><mml:mrow><mml:mn>1</mml:mn><mml:mo>/</mml:mo><mml:mi>r</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math></alternatives></disp-formula> where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vs3v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0011" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>b</mml:mi><mml:mi>r</mml:mi></mml:msub><mml:mo>></mml:mo><mml:mn>0</mml:mn></mml:mrow></mml:math></alternatives> depends only on <italic>r</italic>. In addition, for many values of <italic>d</italic> we show <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vs29" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0012" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>b</mml:mi><mml:mi>r</mml:mi></mml:msub><mml:mo>∼</mml:mo><mml:msub><mml:mi>c</mml:mi><mml:mi>r</mml:mi></mml:msub></mml:mrow></mml:math></alternatives> as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vs5z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley::media:rsa20453:rsa20453-math-0013" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>→</mml:mo><mml:mo>∞</mml:mo></mml:mrow></mml:math></alternatives>, so the result is almost sharp for large <italic>r</italic>. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 224‐239, 2014</p> </abstract>