چكيده فارسي :
چكيده
براي دو مجموعه داده شده G_1 و G_2 از گراف‌ها، عدد رمزي تعميم يافته R(G_1,G_2) كوچكترين عدد صحيح N است به طوري كه براي هر گراف G روي N راس، يا G داراي عضوي از G_1 است يا مكمل G داراي يك عضوي از G_2 است. واضح است كه R(G_1,G_2)=R(G_2,G_1). هنگامي كه |G_1 |=|G_2 |=1 باشد، عدد رمزي تعميم يافته R(G_1,G_2) به عدد رمزي معمولي R(G_1,G_2) براي دو گراف داده شده G_1 و G_2 كاهش مي‌يابد. به راحتي مي‌توان ديد كه براي هر G_1∈G_1 و G_2∈G_2، رابطه R(G_1,G_2)≤R(G_1,G_2) برقرار است. در اين پايان‌نامه، روي R(C_1,C_2)، تمركز مي‌كنيم كه هر C_i مجموعه‌اي از دورها است.
براي دو خانواده داده شده C_1 و C_2 از دورها، عدد رمزي تعميم يافته جفت (C_1,C_2) نشان داده شده با R(C_1,C_2)، برابر با كوچكترين عدد صحيح N تعريف مي‌شود، به طوري كه براي هر گراف G بر روي N راس، يا G شامل يك دور از C_1 يا مكمل G شامل يك دور از C_2 باشد.
در سراسر اين پايان‌نامه، (C_1,C_2) يك جفت خانواده غير تهي از دورها را نشان مي‌دهد، كه مي‌خواهيم اعداد رمزي تعميم يافته R(C_1,C_2) را محاسبه كنيم. تمام گراف‌هاي اين تحقيق متناهي، ساده و بدون جهت هستند. علاوه بر اين، (G_1,G_2) يك جفت گراف غير تهي و (G_1,G_2) يك جفت خانواده غير تهي از گراف‌هاي غير تهي را نشان مي‌دهد.
بنابراين، نتايجي را ارائه مي‌كنيم كه شامل تمام مقادير دقيق قبلي شناخته شده اعداد رمزي تعميم‌يافته براي دو خانواده دور است. وقتي |C_1 |=|C_2 |=1، اعداد رمزي معمولي R(C_1,C_2) به طور مستقل توسط فادريFaudree و شلپ Schelp [?] و رستاRosta [?] تعيين شدند. يك اثبات جديد، ساده تر، اما هنوز كاملاً فني و مفصل، توسط كاروليKárolyi و رستا [?] ارائه شده است.
رده‌بندي موضوعي: 55C05، 10D05
واژگان كليدي: اعداد رمزي، خانواده‌اي از دورها، همه دوري ضعيف
چكيده انگليسي :
The Ramsey numbers of two sets of cycles
Zahra Bahrami Manesh
z.bahramimanesh@math.iut.ac.ir
September 18, 2024
Master of Science Thesis (in Farsi)
Departement of Mathematical Sciences
Isfahan University of Technology, Isfahan 84156-8311, Iran
__________
Supervisor: Dr. Ramin Javadi
Supervisor: Dr. Gholamreza Omidi
Advisor: Dr. Hamed Lorvand
2000 MSC: 05C55, 05D10
Keywords: ramsey number, sets of cycles, weakly pancyclic
__________
Abstract:
This M.Sc. thesis is based on the following papers
• Wang, Longqin, and Yaojun Chen. "The Ramsey numbers of two sets of cycles." Journal of Graph Theory 96.1 (2021): 129-136.
• Hansson, Mikael. "Generalised Ramsey numbers for two sets of cycles." Discrete Applied Mathematics 238 (2018): 86-94.
One of the important issues in graph theory is the study of the Ramsey numbers of graphs. The problem of calculating Ramsey numbers is one of the hard problems in Graph theory. Ramsey numbers have several generalizations. In this thesis we study different types of Ramsey numbers on graphs.
For two given families G_1 and G_2 of graphs, the Ramsey number R(G_1,G_2) is the smallest integer N such that for any graph G on N vertices, either G has a subgraph from G_1 or G ̅ has a subgraph from G_2. Clearly, R(G_1,G_2)=R(G_2,G_1). If |G_1 |=|G_2 |=1, then R(G_1,G_2) is the ordinary Ramsey number R(G_1,G_2) for two given graphs G_1 and G_2. It is easy to see that R(G_1,G_2)≤R(G_1,G_2) for any G_1∈G_1 and G_2∈G_2.
All graphs are finite, simple, and undirected. Furthermore, (G_1,G_2) and (G_1,G_2) denote a pair of non-empty graphs and a pair of non-empty families of non-empty graphs, respectively. In this thesis, we focus on R(G_1,G_2) for each G_i being a set of cycles.
For two given sets C_1 and C_2 of cycles, the Ramsey number R(C_1,C_2) is the smallest integer N such that for any graph G on N vertices, either G contains a cycle from C_1 or G ̅ contains a cycle from C_2.
When |C_1 |=|C_2 |=1, the (ordinary) Ramsey numbers R(C_1,C_2) were determined independently by Rosta (1973) and by Faudree and Schelp (1974). A new proof, simpler but still quite technical and detailed, was given by Károlyi and Rosta (2001).
R(C_n,C_m)= {
For the Ramsey number R(C_1,C_2), Erdős, Faudree, Roussuau and Schelp (1976) calculated R(C_1,C_2) for C_1 and C_2 being all odd cycles of lengths no more than n and m, respectively. Recently, Hansson (2018) determined R(C_1,C_2) for the cases when C_1 or C_2 contains a cycle of length at most 6, or l_1 and l_2 are even, and posed the following conjecture for R(C_1,C_2) in the general situation.
Conjecture. Let C_1 and C_2 be two sets of cycles with min{l_1,l_2}≥5 . Then
R(C_1,C_2)=max{min{2l_1-1,l_1+〖l'〗_2/2-1},min{2l_2-1,l_2+〖l'〗_1/2-1}}.
After a series of partial results, the above conjeture was settlled completely by wang and chen in 2021.
First we present some results which, include all previously known exact values of generalised Ramsey numbers for two sets of cycles.
