Department of
Applied
Mathematics

Concentration of extension counts in random graphs

Matas Šileikis

Abstract

A graph is epsilon-regular when the ratio of its maximum and minimum vertex degrees is at most 1 + epsilon. Given a fixed graph H, one can generalize the notion of regularity by replacing a vertex degree deg(v) by the number of copies of H containing vertex v (the vertex degrees correspond to the case H = K_2). In late 1980s Joel Spencer gave sufficient conditions for the random graph G(n,p) being epsilon-regular with respect to general H. I will present joint work with Lutz Warnke in which we study the sharpness of Spencer's results and refine them.