Kunal Dutta
Induced paths, holes and trees in random graphs
Abstract:
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.
- P. Erdős and Z. Palka, Trees in Random Graphs. Discrete Mathematics 46 (1983), 145-150.
- M. Krivelevich, B. Sudakov, V. Vu and N. Wormald, On the probability of independent sets in random graphs, Rand. Struct. Alg. 22 (2003), 1-14.