Sandwiching a densest subgraph by consecutive cores1. Issue 2 (10th April 2014) - Gao, Pu
Abstract In this paper, we show that in the random graph <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh1h2" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, c/n)</alternatives>, with high probability, there exists an integer <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh1gh" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k˜</alternatives> such that a subgraph of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh1fz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, c/n)</alternatives>, whose vertex set differs from a densest subgraph of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh1dd" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, c/n)</alternatives> by <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh1cv" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(log2n)</alternatives> vertices, is sandwiched by the <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh1b9" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k˜</alternatives> and the <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh19r" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />(k˜+1)</alternatives>‐core, for almost all sufficiently large c. We determine the value of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh186" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />k˜</alternatives>. We also prove that (a), the threshold of the k‐core being balanced coincides with the threshold that the average degree of the k‐core is at most <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh17n" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />2(k−1)</alternatives>, for all sufficiently large k; (b) with high probability, there is a subgraph of <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj23twh0sz" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />G(n, c/n)</alternatives> whose density is significantly denser than any of its nonempty cores, for almost all sufficiently large c > 0. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 341–360, 2015