Skip to main content
SUPERVISOR
Gholamreza Omidi,Ghaffar Raeisi
غلامرضا امیدی اردلی (استاد راهنما) غفار رئیسی وانانی (استاد مشاور)
 
STUDENT
Zahra Rahimi
زهرا رحیمی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Doctor of Philosophy (PhD)
YEAR
1392
For given graphs G?,G?,...,Gt, the multi color Ramsey number R(G?,G?,...,Gt) is the smallest positive integer n such that if the edges of the complete graph Kn are partitioned into t disjoint color ?n??, i.e.,when n is odd and large enough,every ?-coloring of the edges of the complete graph on ?n?? vertices, K_(?n??), contains a monochromatic Cn. Hear we prove a Ramsey-type problem with the similar result. Consider a graph G on N = ?n?? vertices,where n is sufficiently large odd integer and let ?(G) gt; ?N/?. We show asymptotically that every ?-coloring of the edges of G, contains a monochromatic Cn. More pricisely, we show that for every ? gt; ? there exists n? such that for every odd n ? n? and every graph G on (? amp;#??;?)n vertices with ?(G) ? (?/? amp;#??;?)n, each colouring of the edges of G with three colours leads to a monochromatic cycle of length n. For the proof we show that in every ?-coloring of the edges of G there exists a color which contains a matching saturating at least n vertices contained in a component in this color which is non-bipartite. Then using Szemerédi’s regularity lemma we will show how existence of Cn follows from existence of this m
فرضکن?د H_k ،...،H_? ،H_? گراف های ساده ای باشند. عدد رمزی (R(H_?,H_?,...,H_k، کوچک ترین عدد صحیح n تعر?ف م? شود به طوریکه در هر رنگ آم?زی دلخواه از?ال های گراف کامل K_n با k رنگ، ز?رگراف القا?? تول?د شده توسط ?ال‌های به رنگ i-ام، شامل گرافی یکریخت با H_i باشد. تع??ن مقدار دق?ق اعداد رمزی بس?ار دشوار است و نتا?ج به دست آمده در ا?ن زم?نه محدود هستند. در ا?ن رساله، برای اعداد صح?ح n_c،...،n_? و t_s ،...،t_? ،t_?، عدد رمزی ستاره‌ها و تطابق‌ها را به طور دق?ق مشخص می‌کنیم. ا?ن مقدار تعم?م? از نتا?ج? است که کوکا?نه و ?ر?مر، برای عدد رمزی تطابق ها و ج?ارفاش و شارکوزی برایعدد رمزی ?ک ستاره و دو تطابق به دست آوردند. ع?وه بر آن به بررس? نتا?ج و کاربردها?? از عدد رمزی ستاره ها و تطابق ها م? پرداز?م. شلپ ا?ده ی جا?گز?ن کردن گراف چگال به جای گراف کامل، در تعر?ف اعداد رمزی، برای عدد رمزی دو مس?ر رامطرح کرد. حدس وی در سال ???? ، توسط ج?ارفاش و شارکوزی به صورت مجانب? و با کمک لم منظم? سمردی اثبات شد. بنو?دز و همکارانش،حدس شلپ را به سه دور فرد تعم?م دادند وحدس زدند که برای عدد فرد و به اندازه ی کاف? بزرگ تک رنگ است. در ا?ن رساله تعمیم حدس شلپ را بصورت مجانبی اثبات می کنیم. در واقع نشانم? ده?مبرای هر ? gt; ?، عدد n_? ای وجود دارد به طوری که برای هر عدد فرد ?_n ? n هرگاه G گرافی با ? amp;#??; ?)n و با مینیمم درجه‌ی حداقل ?(G) ? (?/? amp;#??;?)n باشد آنگاه در هر رنگ آم?زی از ?ال های G، با سه رنگ، دور تک رنگ? به طول n وجود دارد. در پا?ان دو حدس، ?ک? در مورد دورهای زوج تک رنگ در گراف های چگال? که ?ال های آن ها به طور دلخواه با سه رنگ، رنگ شده اند و د?گری در مورد مس?رهای زوج تک رنگ در گراف های چگال? که ?ال های آن ها به طور دلخواه با سه رنگ، رنگ شده اند را ب?ان م? کن?م و نشان م? ده?م شرا?ط در نظر گرفته شده در ا?ن دو حدس، بهتر?ن شرا?ط ممکن هستند.

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