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: No Dense Subgraphs Appear in the Triangle-free Graph Process. | No Dense Subgraphs Appear in the Triangle-free Graph Process Stefanie Gerke Royal Holloway College University of London Egham TW20 0EX United Kingdom Tamas Makai Royal Holloway College University of London Egham TW20 0EX United Kingdom Submitted Nov 22 2010 Accepted Aug 3 2011 Published Aug 26 2011 Mathematics Subject Classification 05C80 Abstract Consider the triangle-free graph process which starts from the empty graph on n vertices and in every step an edge is added that is chosen uniformly at random from all non-edges that do not form a triangle with the existing edges. We will show that there exists a constant c such that asymptotically almost surely no copy of any fixed finite triangle-free graph on k vertices with at least ck edges appears in the triangle-free graph process. 1 Introduction The Erdos-Renyi random graph process starts from the empty graph on n vertices Gn 0 and at the ith step Gn i is obtained from Gn i-1 by adding an edge chosen uniformly at random from the set of non-edges in Gn i_1. We are interested in typical structural properties of Gn m when n is large. We say an event holds asymptotically almost surely . if the probability that it occurs tends to one as the number of vertices n tends to infinity. The random graph process is well understood partly as Gn m has strong connections to the random graph model Gn p when p m n . In Gn p each edge is present independently of the presence or absence of all other edges with probability p see 4 7 . A variant of this process namely the triangle-free graph process where at step i of the random graph process an edge is chosen uniformly at random from the set of nonedges in Gn i_1 fulfilling the additional condition that when added to Gn i_1 the graph remains triangle free. The process terminates when no more edges can be inserted. In this paper we show that there exists a constant c such that given any fixed finite triangle-free THE .
