Skip to main content
SUPERVISOR
Safieh Mahmoodi,Gholamreza Omidi
صفیه محمودی (استاد مشاور) غلامرضا امیدی اردلی (استاد راهنما)
 
STUDENT
Fahimeh Rahimi
فهیمه رحیمی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1390

TITLE

Dependent random choice
In this thesis, we present an expanded account of the method, dependent random choice. This method, which is an example of the celebrated Probabilistic Method, can be roughly described as follows. Given a dense graph G , we pick a small subset T of vertices uniformly at random. Then the rich set U is simply t he set of common neighbors of T . Intuitively, it is clear that if some subset of G has only few neighbors , it is unlikely that all the members of the random set T will be chose n among these neighbors. Hence, we do not expect U to contain any such subset. A vast number of problems in Ramsey Theory and Extremal Graph Theory deal with embedding a small or sparse graph in a dense graph. To obtain such an embedding, it is sometimes convenient to ?nd in a dense graph a large vertex subset U which is rich in the sense that all (or almost all) small subsets of U have many common neighbors. The last ten years have brought several striking applications of dependent random choice to Extremal Graph Theory, Ramsey Theory, Additive Combinatorics, and Combinatorial Geometry. In 1998, Gowers used this method to prove the Szemerèdi's theorem on arithmetic progressions, and in 2001, Kostochka and R?dl used dependent random choice to obtain the upper bound for the Ramsey number of degenerate graphs. There are now a growing number of papers, which use this approach. In 2010, Sudakov and Fox wrote a survey about this method, and gave this topic a systematic treatment. They attempted to describe most of the known variants of dependent random choice and illustrated how they can be used to make progress on variety of combinatorial problems. Also they concentrate d on explaining the main ideas of the applications of this method. This thesis is an extension of this survey.
تعداد زیادی از مسائل در نظریه رمزی و نظریه اکسترمالی گراف با مسأله نشاندن یک گراف تنک در یک گراف چگال در ارتباطند. برای به‌دست آوردن چنین نشاندنی ، می‌توان زیرمجموعه بزرگ U از رأس‌ها را در گراف چگال مورد نظر به‌دست آورد به‌طوری‌که تمامی(و یا تقریباً تمامی) زیرمجموعه‌های U دارای تعداد زیادی همسایه مشترک باشند. سپس می‌توان رأس‌‌های گراف تنک مورد نظر را یکی‌یکی به جای رأس‌های U نشاند و گراف تنک را در گراف چگال پیدا کرد. با استفاده از روش انتخاب تصادفی وابسته که نمونه‌ای از روش‌های احتمالاتی است ، ابتدا در گراف چگال G زیرمجموعه کوچک T از رأس‌ها را به صورت تصادفی و یکنواخت انتخاب می‌کنیم. سپس مجموعه U را مجموعه همسایه‌های مشترک T در نظر می‌گیریم. اگر G دارای زیرمجموعه‌ای با تعداد همسایه مشترک کم باشد ، غیرمحتمل است که تمام اعضا این مجموعه در مجموعه T انتخاب شود. درنتیجه انتظار نمی‌رود که U دارای زیرمجموعه‌ای با تعداد همسایه‌های کم باشد. لذا زیرمجموعه مورد نظر U برای G به‌دست می‌آید. تاکنون کاربردهای زیادی از روش انتخاب تصادفی وابسته به‌دست آمده است. در این پایان‌نامه این روش را به‌طور مفصل توضیح و شرح می‌دهیم و کاربردهایی از آن را بیان می‌کنیم. همچنین در این پایان‌نامه عدد رمزی R( , ) را برای هر دو عدد صحیح مثبت n? m? 3 تخمین می‌زنیم که در آن مسیر ?-یکنواخت تایت با n یال می‌باشد.

ارتقاء امنیت وب با وف بومی