TAILIEUCHUNG - Báo cáo toán học: "Coloring the edges of a random graph without a monochromatic giant component"

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:Coloring the edges of a random graph without a monochromatic giant component. | Coloring the edges of a random graph without a monochromatic giant component Reto Spohel Angelika Steger Institute of Theoretical Computer Science Institute of Theoretical Computer Science ETH Zurich Switzerland ETH Zurich Switzerland rspoehel@ asteger@ Henning Thomas Institute of Theoretical Computer Science ETH Zuurich Switzerland hthomas@ Submitted Mar 25 2010 Accepted Sep 19 2010 Published Oct 5 2010 Mathematics Subject Classification 05C80 05C15 Abstract We study the following two problems i Given a random graph Gn m a graph drawn uniformly at random from all graphs on n vertices with exactly m edges can we color its edges with r colors such that no color class contains a component of size O n ii Given a random graph Gn m with a random partition of its edge set into sets of size r can we color its edges with r colors subject to the restriction that every color is used for exactly one edge in every set of the partition such that no color class contains a component of size O n We prove that for any fixed r 2 in both settings the sharp threshold for the existence of such a coloring coincides with the known threshold for r-orientability of Gnm which is at m rc n for some analytically computable constant c . The fact that the two problems have the same threshold is in contrast with known results for the two corresponding Achlioptas-type problems. 1 Introduction One of the most prominent areas of research in random graph theory is the component structure of the random graph Gn m a graph drawn uniformly at random from all graphs A preliminary version of this paper appeared in the proceedings of the European Conference on Combinatorics Graph Theory and Applications EuroComb 2009 17 . iThe author was supported by the Swiss National Science Foundation grant 200020-119918. He is now at MPI Saarbrucken. The author was supported by the Swiss National Science Foundation grant 200021-120284. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học