Skip to main content
SUPERVISOR
Gholamreza Omidi,Behnaz Omoomi
غلامرضا امیدی اردلی (استاد راهنما) بهناز عمومی (استاد مشاور)
 
STUDENT
Leila Maherani
لیلا ماهرانی برزانی

FACULTY - DEPARTMENT

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

TITLE

Diagonal Ramsey Numbers of Graphs and Hypergraphs
In this thesis, we study the diagonal Ramsey numbers of particular the edges of the complete graph K n with distinct colors { 1 , 2 , ..., k } , there is a monochro- matic copy of G i in color i , for some 1 ? i ? k . A problem on Ramsey numbers of general graphs was posed in 1983 by Erd?os. Erd?os conjectured that there is a constant c such ? that r ( G ) ? 2 c m for every graph G with m edges and no isolated vertices. In 2011, Sudakove proved this conjecture. Here we present the Sudukov’s result and then give an extension of his result. Determining Ramsey number of sparse graphs is also an interesting roblem in graph Ramsey theory. We say that a family of graphs G is a Ramsey linear family if there is a constant c = c ( G ) 0 such that r ( G ) ? cn for every graph G ? G of order n . urr and Erd?os conjectured: 1. The family of graphs having maximum degree at most ? is Ramsey linear. 2. The family of d -degenerate graphs is Ramsey linear. The first conjecture was proved y Chvatal et al. in 1983 but the econd one is still open. For an k -uniform hypergraph H , the Ramsey umber r k ( H ) is defined as similar to this umber for graphs. Kostochka and R¨odl gave a counterexample howing that family of k -uniform and d -degenerate hypergraph is not Ramsey linear. agle et al. and Cooley et al., using the zemer´edi’s regularity lemma, how that the family of k - uniform hypergraphs with bounded maximum degreee is Ramsey linear. In 2009, Conlon, Fox and Sudakov used a probabilistic argument known as dependent random choice to give another proof for the above fact. Here we present the results obtained by Conlon et al. The multicolor Ramsey number r ( P n 1 , ..., P n t ) is not known for t ? 3. Here we deter- mine the Ramsey number r ( P 3 , P n , P m ) for all m ? n .
تسا n ?ع?بط ددع ن? رتکچوک ، G و H هاوخلد فارگ ود ?ارب r ( H, G ) ? زمر ددع ،زمرق و ?بآ گنر ود اب n ? هبترم زا لماک فارگ ?لا? ? ز?مآ گنر-? ره رد هک ? ر وط هب ? زمر ددع ار r ( G, G ) .تفا? زمرق گنر زا G فارگر? ز ا? ?بآ گنر زا H فارگر? ز ناوتب .م?هد ?م ش?امن r ( G ) اب و م??وگ ?م G فارگ ? زمر ددع راصتخا هب ا? G فارگ ? رطق ? زمر دادعا ن?مخت ا? و ن??عت ،اه فارگ ? زمر ? ه? رظن رد ز?گنارب شلاچ ?اه هلاسم زا ?ک? اب هطبار رد رب و شودرا فو رعم سدح ود هب ناوت ?م هن?مز ن?ا رد .تسا اه فارگ ? رطق .درک هراشا کنت ?اه فارگ ? رطق ? زمر دادعا ? زمر ددع و راد نارک مم? زکام ? هجرد اب ?اه فارگ ? زمر ددع هک دندز سدح رب و شودرا مل کمک هب شناراکمه و لاتاوچ .تسا ?طخ ناش هبترم هب تبسن ،هد?هابت- d ?اه فارگ زا .دندرک تابثا راد نارک مم? زکام ? هجرد اب ?اه فارگ ?ارب ار سدح ن?ا ،?درمز ?مظنم فلتخم دارفا ،دوبن ?بولطم نارک شناراکمه و لاتاوچ طسوت هدمآ تسد هب نارک هک اج نآو سکاف ،نلنک طسوت نونکات نارک ن? رتهب و دنر وآ تسد هب ? رتهب ?اه هج?تن دندرک ?عس .تسا هدشن تابثا ز ونه هد?هابت- d ?اه فارگ ?ارب ?اب سدح .تسا هدمآ تسد هب وکادوس .تسا هدمآ تسد هب اه فارگ زا ??اه س?ک ?ارب نآ ?تسرد هچرگا اب طابترا رد رگ?د بلاج ? هلاسم ز?ن صخشم لا? دادعت اب ?اه فارگ ? زمر ددع ? هعلاطم هطبار رد .دش حرطم شودرا زا ر? ز سدح اب هک تسا اه فارگ ? رطق ? زمر دادعا ? هعلاطم هک ? ر وط هب دراد دوجو c ? تباث هک دز سدح شودرا ،?لا?- m ?اه فارگ ? زمر ددع اب ? ?اه فارگ ?ارب سدح ن?ا . r ( G ) ? ? c m ،اهنت سأر نودب و لا? m اب G فارگ ره ?ارب طسوت هاوخلد فارگ ره ?ارب و ???? لاس رد وکادوس و چ?ولو? رک ،نولا طسوت ?شخبود هک هتسباو ?فداصت باختنا شو ر زا شناراکمه و نولا .دش تابثا ???? لاس رد وکادوس ?اه فارگ صاوخ زا شتابثا رد وکادوس و دنا هدرک هدافتساتسا ?ت?امتحا ?اه شو ر رب ?نتبم .تسا هدرک هدافتسا کنت رت هد?چ?پ راتخاس تلع هب .دوش ?م ف? رعت اه فارگ هباشم ز?ن هاوخلد فارگربا ود ? زمر ددع رتمک را?سب اه فارگربا ? زمر دادعا ?ارب هدمآ تسد هب ج?اتن ،اه فارگ هب تبسن اه فارگربا - k ?اه فارگربا ? زمر ددع ? هعلاطم هب راب ن?لوا لدار و اکچاتساک .دشاب ?م اه فارگ زا هد?هابت- d و تخاونک?- k ?اه فارگربا ? زمر ددع و راد نارک مم? زکام ? هجرد اب تخاونک? تخاونک?- k ?اه فارگربا ?ارب هدش رکذ ?اه سدح ?تسردان ا? ?تسرد در وم رد .دنتخادرپ ?اه فارگربا دندرک تباث ???? لاس رد لدار و اکچاتساک .تسا هدمآ تسد هب ?ج?اتن ز?ن ناش هبترم هب تبسن اه نآ ? زمر ددع هک ? ر وط هب دنراد دوجو ?ا هد?هابت- d و تخاونک?-? ره ? زمر ددع هک دندرک تباث رگ?د دارفا و نلنک ،لگ?ن ،?لوک ن?نچ مه .تس?ن ?طخ زا ?خرب .تسا ?طخ شا هبترم هب تبسن ،راد نارک مم? زکام ? هجرد اب تخاونک?- k فارگربا .دنشاب ?م هتسباو ?فداصت باختنا کمک هب ?خرب و ?درمز ?مظنم مل کمک هب اه تابثا ن?ا و م?نک ?م ه?ارا ?لا?- m ?اه فارگ ? زمر ددع ?ارب ار وکادوس ? هج?تن ،همان نا?اپ ن?ا رد و نلنک ? هج?تن ن?نچ مه .م?شاب هتشاد نآ م?معت ?و ر ?ا هعلاطم م?نک ?م ?عس همادا رد دهاوخ ه?ارا راد نارک مم? زکام ? هجرد اب ?اه فارگربا ? زمر ددع اب هطبار رد شناراکمه سأر هس اهر?سم زا ?ک? هک ?تلاح رد ار اهر?سم ?گنر-? ? زمر ددع ،همان نا?اپ ن?ا رد .دش .م?نک ?م صخشم لماک ر وط هب ،دشاب هتشاد

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