Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The t-stability number of a random graph. | The t-stability number of a random graph Nikolaos Fountoulakis Max-Planck-Institut fur Informatik Campus E1 4 Saarbrucken 66123 Germany Ross J. Kang School of Engineering and Computing Sciences Durham University South Road Durham DH1 3LE United Kingdom Colin McDiarmid Department of Statistics University of Oxford 1 South Parks Road Oxford OX1 3TG United Kingdom Submitted Nov 14 2009 Accepted Apr 2 2010 Published Apr 19 2010 Mathematics Subject Classification 05C80 05A16 Abstract Given a graph G V E a vertex subset S c V is called t-stable or Independent if the subgraph G S induced on S has maximum degree at most t. The t-stability number a-t G of G is the maximum order of a t-stable set in G. The theme of this paper is the typical values that this parameter takes on a random graph on n vertices and edge probability equal to p. For any fixed 0 p 1 and fixed non-negative integer t we show that with probability tending to 1 as n TO the t-stability number takes on at most two values which we identify as functions of t p and n. The main tool we use is an asymptotic expression for the expected number of t-stable sets of order k. We derive this expression by performing a precise count of the number of graphs on k vertices that have maximum degree at most t. 1 Introduction Given a graph G V E a vertex subset S c V is called t-stable or t-dependent if the subgraph G S induced on S has maximum degree at most t. The t-stability number Part of this work was completed while this author was a doctoral student at the University of Oxford part while he was a postdoctoral fellow at McGill University. He was supported by NSERC Canada and the Commonwealth Scholarship Commission UK . THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R59 1 at G of G is the maximum order of a t-stable set in G. The main topic of this paper is to give a precise formula for the t-stability number of a dense random graph. The notion of a t-stable set is a generalisation of the notion of a stable set. Recall
