Skip to main content
SUPERVISOR
Gholamreza Omidi,Maryam Shahsiah
غلامرضا امیدی اردلی (استاد راهنما) مریم شاه سیاه (استاد مشاور)
 
STUDENT
Meysam Miralaei
میثم میرعلایی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Doctor of Philosophy (PhD)
YEAR
1392

TITLE

Size Ramsey number of graphs
For given graphs H_1,…,H_t the multicolor size Ramsey number r ?(H_1,…,H_t) is the smallest integer m such that there exists a graph G on m edges such that in every t-edge coloring of G there is a monochromatic copy of H_i of color i for some 1?i?t. ) by Erd?s, Faudree, Rousseau and Schelp. Since then, the size Ramsey numbers of graphs have been studied with particular focus on the case of trees, bounded degree graphs and sparse graphs. Moreover, size Ramsey number of a sparse graph versus a dense graph has its special importance. Determining the exact value of r ?(K_(1,k) ,K_n) is one of the most studied directions in this area. In 1983, Faudree and Sheehan posed a conjecture that was an extension of a conjecture of Erd?s and determined the exact value of r ?(K_(1,k) ,K_n ). In the first part of this thesis, we study this conjecture and prove an important case of this conjecture. Moreover, we generalize our results on r ?(K_(1,k) ,K_n) for multi copies of stars versus multi copies of cliques. It is worth noting that determining the exact value of size Ramsey numbers for even a simple graph like a path P_n seems quite difficult. In 1983, answering a question posed by Erd?s, Beck proved that for sufficiently large n, we have r ?(P_n ,P_n )? 900n. Since then the study of the size Ramsey number of bounded degree graphs has been at the center of attention. Beck asked whether r ?(G ,G) grows linearly in the number of vertices for graphs of bounded degree. In fact, for the graph (n^(2-1/d #43;o(1) ) ). In the second part of this thesis, we give an alternative proof for the linearity of r ?(P_n,P_n) and answer the conjecture of Colon and Nenadov for grid graphs.
فرض کنید H_t ،… ،H_1 گراف‌هایی دلخواه هستند. عدد رمزی یالی چند رنگی گراف‌های H_t ،… ،H_1 که با نماد r ?(H_1 ,…,H_t ) نمایش می دهیم، کوچک ترین عدد طبیعی m است به‌طوری‌که یک گراف m یالی مانند G وجود دارد که در هر رنگ‌آمیزی از یال‌های گرافG با t رنگ مختلف، یک زیر گراف تک رنگ و یک ریخت با گراف H_i با رنگ i به ازای حداقل یک 1?i?t یافت شود. با استناد به قضیه‌ی کلاسیک رمزی در سال 1930، عدد رمزی یالیr ?(H_1 ,…,H_t ) به ازای گراف‌های دلخواهH_t ،… ،H_1 وجود دارد. عدد رمزی یالی گراف‌ها نخستین بار در سال 1978 در حالتی که تعداد رنگ‌ها برابر با دو است (یعنی t=2)، توسط اردوش، فیودری، روسی و شلپ مورد مطالعه قرار گرفت. از آن زمان تا کنون عدد رمزی یالی گراف‌ها با تمرکز ویژه‌ای بر روی درخت‌ها و گراف‌های با ماکزیمم درجه‌ی کراندار مورد مطالعه قرار گفته است. همچنین تعیین عدد رمزی یالی یک گراف نسبتا پریال و یک گراف کم یال نیز از اهمیت ویژه‌ای برخوردار بوده است. یکی از مهم‌ترین مسأله‌ها در این زمینه تعیین مقدار دقیق عدد رمزی یالی گراف کامل و گراف ستاره است. در سال 1983، فیودری و شیهان حدسی را مطرح کردند که تعمیمی از یک حدس اردوش بوده و مقدار دقیق r ?(K_(1,k) ,K_n) را تعیین می‌کند. یکی از موضوعات مورد مطالعه در این رساله، بررسی حدس مطرح شده توسط فیودری و شیهان است و حالت مهمی از این حدس را حل می‌کنیم. همچنین نتایج به‌دست آمده بر روی r ?(K_(1,k) ,K_n) را برای هر تعداد دلخوه گراف کامل و هر تعداد دلخواه گراف ستاره گسترش می‌دهیم. در ابتدا تعیین عدد رمزی یالی گراف‌ها حتی برای گراف‌های بسیار کم یال مانند مسیرها کار دشواری به نظر می‌رسید. از این‌رو اردوش با طرح پرسشی مسأله‌ی تعیین مرتبه‌ی بزرگی عدد رمزی یالی مسیرها را مطرح کرد. در سال 1983، بِک به این پرسش پاسخ داد و نشان داد که اگر n به اندازه‌ی کافی بزرگ باشد، آنگاه .r ?(P_n ,P_n)? 900n از آن زمان تا کنون مطالعه‌ی عدد رمزی یالی گراف‌های با ماکزیمم درجه‌ی کراندار توجه ویژه‌ای را از سوی پژوهشگران به خود اختصاص داده است. اگر چه عدد رمزی یالی برای خانواده‌های مختلفی از گراف‌های با ماکزییم درجه‌ی کراندار همچون مسیرها، دورها و درخت‌های با ماکزیمم درجه‌ی کراندار، بر حسب تعداد رأس‌های آنها خطی است اما رودل و زمردی نشان داده‌اند که اگر G گرافی nرأسی با ماکزیمم درجه‌ی کراندار باشد، آنگاه مقدار r ?(G ,G)لزوما بر حسب nخطی نیست. کونلن و ننادوو تلاش کردند با افزودن شرایط دیگری به گراف‌های با ماکزیمم درجه‌ی کراندار (همچون شرط تباهیدگی) مرتبه‌ی بزرگی عدد رمزی یالی گراف‌های نسبتا کم یال را تعیین کنند. در همین راستا آنها این پرسش را مطرح کردند که اگر H گرافی d-تباهیده، از مرتبه‌ی n و با ماکزیمم درجه‌ی ? باشد، آن‌گاه r ?(H,H)=O(n^(2-1/d #43;o(1) ) ). در این رساله ابتدا خطی بودن عدد رمزی یالی مسیرها (پرسش مطرح شده توسط اردوش) را مجددا نشان می‌دهیم و سپس پرسش مطرح شده توسط کونلن و ننادوو را برای دسته‌ی خاصی از گراف‌های با ماکزیمم درجه‌ی کراندار و تباهیده یعنی گراف‌های شبکه، پاسخ می‌دهیم.

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