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 evolution of uniform random planar graphs. | The evolution of uniform random planar graphs Chris Dowden LIX École Polytechnique 91128 Palaiseau Cedex France dowden@ Submitted Jun 2 2009 Accepted Dec 18 2009 Published Jan 5 2010 Mathematics Subject Classification 05C10 05C80 Abstract Let Pn m denote the graph taken uniformly at random from the set of all planar graphs on 1 2 . n with exactly m n edges. We use counting arguments to investigate the probability that Pn m will contain given components and subgraphs finding that there is different asymptotic behaviour depending on the ratio mm. 1 Introduction Random planar graphs have recently been the subject of much activity and many properties of the standard random planar graph Pn taken uniformly at random from the set of all planar graphs on 1 2 . n are now known. For example in 7 it was shown that Pn will asymptotically almost surely . that is with probability tending to 1 as n tends to infinity contain at least linearly many copies of any given planar graph. By combining the counting methods of 7 with some rather precise results of 5 obtained using generating functions the exact limiting probability for the event that Pn will contain any given comp onent is also known. More recently attention has turned to the graph Pn m taken uniformly at random from the set P n m of all planar graphs on 1 2 . n with exactly m n edges. It is well known that we must have m 3n for planarity to be possible and also that Pn m behaves in exactly the same way as the general random graph Gn m if mm 2 - n2 3 see for example 6 so the interest lies with the region 1 liminf mm c limsup mm c 3. In 4 the case when m qn for fixed q was investigated using counting arguments and it was shown that for all q G 1 3 Pn qn will . contain at least linearly many copies of any given planar graph as with Pn . It was also shown that the probability that Pn _qn will contain an isolated vertex is bounded away from 0 as n X for all q 3 and hence that the probability that .