Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Almost all graphs with 2.522n edges are not 3-colorable"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Almost all graphs with 2.522n edges are not 3-colorable. | Almost all graphs with 2.522n edges are not 3-colorable Dimitris Achlioptas Michael Molloy 1 optas@cs.toronto.edu molloy@cs.toronto.edu Department of Computer Science University of Toronto Toronto Ontario M5S 3G4 Canada. Abstract We prove that for c 2.522 a random graph with n vertices and m cn edges is not 3-colorable with probability 1 o 1 . Similar bounds for non-fc-colorability are given for k 3. 1991 Mathematics Subject Classification Primary 05C80 Secondary 05C15. 1 Introduction Let N n m A denote the number of graphs with vertices 1 . ng m m n edges and some property A. The term almost all in the title has the meaning introduced by Erdos and Rényi 5 1 N mA 1. Equivalently one can consider a random graph G G V E where V I n and E is a uniformly random m-subset of all n possible edges on V i.e. the G n m model of random graphs. If n is an index running over probability spaces we will say that a sequence of events En occurs with high probability w.h.p. if limn 1 Pr En 1. In particular we will say that G n m n has property A w.h.p. if m n is such that 1 holds for A. In their seminal paper introducing random graphs 5 Erdoos and Réenyi pointed out that a number of interesting properties exhibit a sharp threshold behavior on G n m for each such property A there exists a critical number of edges mA n such that for m around Researh supported in part by an NSERC PGS Scholarship. Current address Microsoft Research One Microsoft Way Redmond WA 98052 U.S.A. Email optas@microsoft.com 1 Researh supported in part by an NSERC grant. 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 6 1999 R29 2 m n the probability of G n m having A changes rapidly from near 0 to near 1. Such properties include having a multicyclic component having a perfect matching connectivity Hamiltonicity and others. A central property in this context is the k-colorability of G n cn where k is a fixed integer. For k 2 this is very well-understood as bipartiteness is equivalent to containing no odd cycles. In .