مشخصات کتاب

Graph Colouring and the Probabilistic Method

ویرایش:  
نویسندگان: Michael Molloy. Bruce Reed (auth.)  
سری: Algorithms and Combinatorics 23 
ISBN (شابک) : 9783642040153, 9783642040160 
ناشر: Springer Berlin Heidelberg 
سال نشر: 2002 
تعداد صفحات: 320 
زبان: English 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 11 Mb 

در صورت تبدیل فایل کتاب Graph Colouring and the Probabilistic Method به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.

توجه داشته باشید کتاب رنگ آمیزی نمودار و روش احتمالاتی نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.

توضیحاتی در مورد کتاب رنگ آمیزی نمودار و روش احتمالاتی

در طول دهه گذشته، بسیاری از پیشرفت‌های عمده در زمینه رنگ‌آمیزی نمودار از طریق روش احتمالی انجام شده است. این مونوگراف با استفاده از ابزارهایی مانند لمای محلی Lovasz و نابرابری غلظت Talagrand، یک درمان در دسترس و یکپارچه از این نتایج ارائه می دهد. موضوعات تحت پوشش عبارتند از: شواهد کان که حدس های رنگ آمیزی گلدبرگ-سیمور و فهرست مجانبی دارند. دلیلی بر این که برای مقداری ثابت مطلق C، هر نمودار با حداکثر درجه دلتا دارای رنگ کل دلتا + C است. اثبات جوهانسون مبنی بر اینکه یک نمودار آزاد مثلثی دارای رنگ O(Delta over log Delta) است. انواع الگوریتمی لمای محلی که امکان ساخت کارآمد بسیاری از رنگ‌های بهینه و نزدیک به بهینه را می‌دهد. این با مقدمه ای ملایم به روش احتمالاتی آغاز می شود و برای محققان و دانشجویان فارغ التحصیل در نظریه گراف، ریاضیات گسسته، علوم کامپیوتر نظری و احتمال مفید خواهد بود. از بررسی ها: "الف ] ما فکر می کنیم که این تک نگاری خوش نوشته به عنوان مرجع اصلی در مورد این موضوع برای سال های آینده خواهد بود." JAnos BarAt، Acta Scientiarum Mathematicarum 69، 2003 "کتاب خواندنی لذت بخش است؛ تلاشی واضح و موفق برای ارائه شهود پشت شواهد وجود دارد که حتی شواهد دشوار و اخیر نتایج مهم را در دسترس خوانندگان بالقوه قرار می دهد. a] این کتاب به محققان و دانشجویان فارغ التحصیل در تئوری گراف، ترکیب شناسی و علوم کامپیوتر نظری که مایل به داشتن این توانایی هستند، به شدت توصیه می شود. Noga Alon، SIAM Review 45 (2)، 2003 "این مونوگراف یک درمان در دسترس و یکپارچه از پیشرفت های عمده ایجاد شده در رنگ آمیزی نمودار از طریق روش احتمالی ارائه می دهد. این تک نگاری هم برای محققان و هم برای دانشجویان فارغ التحصیل در تئوری گراف، ریاضیات گسسته، علوم کامپیوتر نظری و احتمال مفید خواهد بود." Jozef Fiamcik، Zentralblatt MATH 987 (12)، 2002

توضیحاتی درمورد کتاب به خارجی

Over the past decade, many major advances have been made in the field of graph colouring via the probabilistic method. This monograph provides an accessible and unified treatment of these results, using tools such as the Lovasz Local Lemma and Talagrand's concentration inequality. The topics covered include: Kahn's proofs that the Goldberg-Seymour and List Colouring Conjectures hold asymptotically; a proof that for some absolute constant C, every graph of maximum degree Delta has a Delta+C total colouring; Johansson's proof that a triangle free graph has a O(Delta over log Delta) colouring; algorithmic variants of the Local Lemma which permit the efficient construction of many optimal and near-optimal colourings. This begins with a gentle introduction to the probabilistic method and will be useful to researchers and graduate students in graph theory, discrete mathematics, theoretical computer science and probability. From the reviews: "a ] We think that this well-written monograph will serve as a main reference on the subject for years to come." JAnos BarAt, Acta Scientiarum Mathematicarum 69, 2003 "The book is a pleasure to read; there is a clear, successful attempt to present the intuition behind the proofs, making even the difficult, recent proofs of important results accessible to potential readers. a ] The book is highly recommended to researchers and graduate students in graph theory, combinatorics, and theoretical computer science who wish to have this ability." Noga Alon, SIAM Review 45 (2), 2003 "This monograph provides an accessible and unified treatment of major advances made in graph colouring via the probabilistic method. a ] Many exercises and excellent remarks are presented and discussed. Also very useful is the list of up-to-date references for current research. This monograph will be useful both to researchers and graduate students in graph theory, discrete mathematics, theoretical computer science and probability." Jozef Fiamcik, Zentralblatt MATH 987 (12), 2002

فهرست مطالب

Front Matter....Pages I-XIV
Front Matter....Pages 1-1
Colouring Preliminaries....Pages 3-14
Probabilistic Preliminaries....Pages 15-24
Front Matter....Pages 25-25
The First Moment Method....Pages 27-37
The Lovász Local Lemma....Pages 39-42
The Chernoff Bound....Pages 43-46
Front Matter....Pages 47-47
Hadwiger’s Conjecture....Pages 49-53
A First Glimpse of Total Colouring....Pages 55-59
The Strong Chromatic Number....Pages 61-65
Total Colouring Revisited....Pages 67-75
Front Matter....Pages 77-78
Talagrand’s Inequality and Colouring Sparse Graphs....Pages 79-89
Azuma’s Inequality and a Strengthening of Brooks’ Theorem....Pages 91-103
Front Matter....Pages 105-105
Graphs with Girth at Least Five....Pages 107-124
Triangle-Free Graphs....Pages 125-138
The List Colouring Conjecture....Pages 139-153
Front Matter....Pages 155-156
The Structural Decomposition....Pages 157-168
ω, Δ and χ....Pages 169-184
Near Optimal Total Colouring I: Sparse Graphs....Pages 185-193
Near Optimal Total Colouring II: General Graphs....Pages 195-218
Front Matter....Pages 219-219
Generalizations of the Local Lemma....Pages 221-229
A Closer Look at Talagrand’s Inequality....Pages 231-236
Front Matter....Pages 237-237
Finding Fractional Colourings and Large Stable Sets....Pages 239-246
Hard-Core Distributions on Matchings....Pages 247-264
The Asymptotics of Edge Colouring Multigraphs....Pages 265-283
Front Matter....Pages 285-285
The Method of Conditional Expectations....Pages 287-293
Algorithmic Aspects of the Local Lemma....Pages 295-313
Back Matter....Pages 315-326

نظرات کاربران

کتاب های تصادفی

دانلود کتاب Algèbre linéaire - Réduction des endomorphismes

دانلود کتاب Biology in Time and Space: A Partial Differential Equation Modeling Approach (Pure and Applied Undergraduate Texts)

دانلود کتاب Differential Geometry: A First Course

دانلود کتاب Joseph Schumpeter: innovación y destrucción creativa

دانلود کتاب Creativity in the Sciences: A Workbook Companion to Innovation GenerationI