Kunal Dutta

Induced paths, holes and trees in random graphs


We study the concentration of the largest induced paths, trees and cycles (holes) in the random graph model G(n, p) and prove a 2-point concentration for the size of the largest induced path and hole, for all p=Ω(n^(-1/2) log^2 n). As a corollary, we obtain an improvement over a result of Erdős and Palka concerning the size of the largest induced tree in a random graph. Further, we study the path chromatic number and tree chromatic number, i.e. the smallest number of parts into which the vertex set of a graph can be partitioned such that every part induces a (i) path or (ii) tree respectively, for G(n, p). The arguments involve the application of a modified version of a probabilistic inequality of Krivelevich, Sudakov, Vu and Wormald. We also prove a lower bound showing the tightness of the application of the inequality up to logarithmic factors in the exponent.

Joint work with C. R. Subramanian.