Suman Chakraborty (TU/e)

k-core in random subgraphs of dense graphs

k-core is the maximal subgraph of vertices with degree at least k in the subgraph. These subgraphs not only have interesting structures, they have also turned out to be important in other areas of studies as well. For example, they arose in the study of chromatic number of sparse random graphs, and graph mining problems in computer science. In this talk we will discuss the size of the k-core in random subgraphs of dense random graph sequences. Here the random subgraph of a dense graph on n-vertices is formed by retaining every edge with probability c/n, independently (c is a fixed positive constant). We show that the under mild assumptions on the graph we can asymptotically determine the size of the k-core.  (Joint ongoing work with Erhan Bayraktar and Xin Zhang)

VIDEO STREAM