On independent sets in hypergraphs1. Issue 2 (2nd August 2012) - Kostochka, Alexandr; Mubayi, Dhruv; Verstraëte, Jacques
Abstract The independence number<alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrvg" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α(H)</alternatives> of a hypergraph H is the size of a largest set of vertices containing no edge of H. In this paper, we prove that if Hn is an n‐vertex <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrtx" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(r+1)</alternatives>‐uniform hypergraph in which every r‐element set is contained in at most d edges, where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrsc" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />0<d<n/(logn)3r2</alternatives>, then <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrq8" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α(Hn)≥cr(ndlog⁡nd)1/r</alternatives> where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrrt" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cr>0</alternatives> satisfies <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrn5" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />cr∼r/e</alternatives> as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vrpq" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />r→∞</alternatives>. The value of cr 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" />r≥2</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" />d∈ℕ</alternatives>, there are infinitely many Hn such that <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vs6h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α(Hn)≤br(ndlog⁡nd)1/r</alternatives> where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vs3v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />br>0</alternatives> depends only on r. In addition, for many values of d we show <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vs29" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />br∼cr</alternatives> as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgg40d2vs5z" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />r→∞</alternatives>, so the result is almost sharp for large r. We give an application to hypergraph Ramsey numbers involving independent neighborhoods.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 224‐239, 2014