توصيفگر ها :
مساله رمزي , اعداد رمزي , ابرگراف هاي برج , ابرگراف هاي كامل-برج , اعداد رمزي ابرگراف هاي كامل-برج
چكيده فارسي :
در علم تركيبيات قضيه ي رمزي بيان مي كند كه براي هر ابرگراف -rيكنواخت Hعدد طبيعي Nچنان موجود است كه در
هر -cرنگ آميزي دلخواه از ابريال هاي ابرگراف KNrيك كپي تك رنگ از ابرگراف Hيافت شود. كوچكترين عدد طبيعي
Nبا اين خاصيت را عدد رمزي ابرگراف Hگوييم و آن را با ) Rc(Hنشان مي دهيم. در اين پايان نامه عدد رمزي خانواده اي
از ابرگراف ها با عنوان ابرگراف هاي كامل-برج را بررسي مي كنيم. براي گراف دلخواه Gابرگراف Hرا ابرگراف -Gبرج
گوييم هرگاه نگاشت يك به يك و پوشاي ) ϕ : E(G) ! E(Hوجود داشته باشد به طوري كه براي هر ) e 2 E(Gداشته
باشيم ) e ⊆ ϕ(e؛ كه آن را با BGنمايش مي دهيم. خانواده اي از ابرگراف هاي -rيكنواخت كه كپي هايي از ابرگراف هاي
-Gبرج گراف Gهستند را با BrGنشان مي دهيم.
يافتن عدد رمزي برخي گراف ها و ابرگراف هاي مختلف پيچيده است و مقدار دقيق برخي هنوز ناشناخته است؛ اما كران هاي
متفاوتي براي عدد رمزي آن ها ارائه شده است. مهم ترين نتيجه ي ما در اين پايان نامه بحث روي خطي بودن عدد رمزي
ابرگراف هاي كامل-برج نسبت به تعداد رئوسشان مي باشد.
رده بندي موضوعي: 05D10
واژگان كليدي: مسأله رمزي، اعداد رمزي، ابرگراف هاي برج، ابرگراف هاي كامل-برج، اعداد رمزي ابرگراف هاي برج.
چكيده انگليسي :
In Combinatorial Science, Ramsey theorem states that for every r-uniform hypergraph H, there exists a natural number N such that in every c-coloring of hyperedges in hypergraph Knr, we can find a monochromatic H. The smallest
such N is called Ramsey number of H and denote by Rc(H).
In this thesis, we study the Ramsey number of a family of hypergraphs that is called complete-Berge hypergraphs.
For an arbitary graph G, we call the hypergraph H, the Berge-G hypergraph when there exist a bijective map
ϕ : E(G) ! E(H) that for every e2E(G), e⊆ ϕ(e). We show this hypergraph by BG. The family of r-regular
hypergraphs that are the copies of BG are showed by BrG.
Finding the Ramsey number of some different graphs and hypergraphs is difficult and the exact amount of some is
unknown, but different bounds for it are presented. The most important result in this thesis is discussing on linearity
of Ramsey number of complete-Berge hypergraphs than the number of their vertices. In 2018, Salia and his partners proved that for every 2-edge coloring of BrKn, the Ramsey number of these hypergraphs is linear. Also in
2019, Axenovich and Gyarfas focus on Ramsey number of small hypergraphs with an arbitary c-edge coloring and
found some linear bounds for Rc(BrKn). Finally in 2019, Gerbner, Methuku, Omidi and Vizer studied the Ramsey
number of complete-Berge hypergraphs and showed that the Ramsey number of these hypergraphs is linear than the
number of their vertices. The following results were summarized:
1-if r > 2c and n is large enough, then Rc(Brkn) = n.
2-if r = 2c and n is large enough, then
R(BrG1; : : : ; BrGc) = {nn o:w: + 1 if one of the Gis is not good and the remaining Gis are Kn;
3-if r < 2c in this case,
77
(i) if 2 < r then 1 + c⌊n - 2
c - 1
⌋ ≤ Rc(BrKn).
(ii) if c < r then R(BrKn1; … ; BrKnc) ≤ ∑c i=1 ni.
(iii) if c + 1 < r and n >
r - c - 1
c
((2r) + r - 1)، then Rc(BrKn) ≤ c
r - c - 1
n.
(iv) if r = 2c - 1 and n >
2c - 3
2c - 1
((2r) + r - 1)، then Rc(BrKn) ≤ (2c - 1) n
c - 3
