Note on a problem of M. Talagrand1. Issue 4 (1st July 2014) - DeMarco, B.; Kahn, J.
Abstract Answering a question of M. Talagrand, we show that there is a fixed L with the following property. For positive integers <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgc4q" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k≤n</alternatives> and <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgc2p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p∈[0, 1]</alternatives>, if <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgc0n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ℱ</alternatives> is the set of subgraphs of Kn containing at least <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgbwm" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(nk)p(k2)</alternatives> copies of Kk, then there is a set <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgbv3" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G</alternatives> of subgraphs of Kn such that (i) each member of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgbtk" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ℱ</alternatives> contains a member of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgbs2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G</alternatives> and (ii) <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgbrj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />∑S∈G(p/L)|S|≤1/2</alternatives> (where <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgkrnvgbq1" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />|S|</alternatives> means number of edges). © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 663–668, 2015