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

FACULTY - DEPARTMENT

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

TITLE

Ramsey numbers and Turan numbers of Berge hypergraphs
LetH be an arbitrary r-uniform hypergraph. The q-color Ramsey number Rr(H; q) is the minimum integer n such that there is a monochromatic copy of H in every q-edge-coloring of Krn , complete r-uniform hypergraph of order n. The existence of such a positive integer is guaranteed by Ramsey’s ex(n;H). For a graph G, we say that a hypergraph H is a Berge-G if there is a bijection ? : E(G) ! E(H) such that e amp;#??; ?(e) for every e ? E(G). Determining the Ramsey numbers of r-uniform t-tight Berge- cycles and the Tur?n numbers of complete ?-uniform Berge-hypergraphs are two problems investigated in this thesis. Gy?rf?s, Lehel, S?rk?zy and Schelp conjectured that for r amp;#??; ? and sufficiently large n, every (r???)-edge coloring of complete hypergraphKrn contains a monochromatic Hamiltonian Berge-cycle. They proved their conjecture for the first case r = ? and a weaker form of conjecture, which indicates that the statement of this conjecture is true for sufficiently large n with ?r??? ? ? colors instead of r??? colors. An asymptotic form of conjecture was proved for every r, using the method of Regularity Lemma, by Gy?rf?s, S?rk?zy and Szemerédi. In this thesis, we show that this conjecture is true for the case r = ?, the first open case. Also we prove a weaker form of conjecture by using r ??? colors instead of r ??? colors. Some new results are also given for the Ramsey numbers of r-uniform t-tight Berge- cycles. Considering the problem of finding the Tur?n numbers of Berge-hypergrahs, in this thesis, we determine the exact value of the Tur?n numbers of complete ?-uniform Berge-hypergraphs and present their extremal construction. کلیدواژه فارسی
فرض کنید $\\mathcal{H}$ یک ابرگراف $r$-یکنواخت است. عدد رمزی $q$-رنگی $\\mathcal{H}$ که آن‌را با نماد $R_r(\\mathcal{H};q)$ نمایش می‌دهیم، کوچک‌ترین عدد طبیعی $n$ است به طوری که در هر رنگ‌‌آمیزی از یال‌های ابرگراف‌ کامل $\\mathcal{K}_n^r$ با $q$ رنگ مختلف، بتوان یک زیرابرگراف تک‌رنگ و یک‌ریخت با $\\mathcal{H}$ یافت. با استناد به قضیه‌ی کلاسیک رمزی در سال ????، عدد رمزی $R_r(\\mathcal{H};q)$ به ازای هر ابرگراف $\\mathcal{H}$ و هر عدد صحیح $q$ وجود دارد. عدد توران $\\mathcal{H}$ که با نماد $ex(n,\\mathcal{H})$ نمایش می‌دهیم، برابر با بیشترین تعداد یال‌های یک ابرگراف از مرتبه‌ی $n$ است که شامل هیچ زیرابرگراف یک‌ریخت با $\\mathcal{H}$ نیست. هر ابرگراف $n$ رأسی با $ex(n,\\mathcal{H})$ یال و فاقد $\\mathcal{H}$ را ابرگراف اکسترمال برای $\\mathcal{H}$ می‌گوییم. برای اولین بار در سال ????، منتل عدد توران و ساختار اکسترمال را برای گراف کامل $K_?$ مشخص کرد. در سال ????، توران نتیجه‌ی منتل را به گراف کامل $K_t$ تعمیم داد.\\\\ تعیین مقدار دقیق اعداد رمزی و اعداد توران در گراف‌ها و ابرگراف‌ها در صدر مسئله‌های ترکیبیات اکسترمال، که زیرشاخه‌ای از ترکیبیات است، قرار دارد. محاسبه‌ی این اعداد در حالت کلی بسیار دشوار است. حتی در حالتی که $\\mathcal{H}$ یک گراف است تعیین این اعداد ساده نیست. تنها برای برخی گراف‌های خاص، عدد رمزی و یا عدد توران به طور دقیق به دست آمده است و برای بعضی گراف‌ها توانسته‌اند کران‌هایی به دست بیاورند که گاهی این کران‌ها با مقادیری که حدس زده شده است اختلاف زیادی دارند. \\\\ فرض کنید $G=(V,E)$ یک گراف دلخواه است. می‌گوییم ابرگراف $\\mathcal{H}$ یک $G$-برج است، هرگاه نگاشت یک به یک و پوشای $\\phi : E(G)\\rightarrow E(\\mathcal{H})$ وجود داشته باشد به طوری که اگر $e\\in E(G)$، آن‌گاه داشته باشیم $e\\subseteq \\phi (e)$. خانواده‌ی تمام ابرگراف‌های $r$-یکنواخت $G$-برج را با $\\mathcal{B}_r(G)$ نشان می‌دهیم. \\\\ یکی از مسأله‌هایی که در این رساله به آن می‌پردازیم، مطالعه‌ی عدد رمزی دورهای $r$-یکنواخت $t$-تایت برج است. در سال ???? جیارفاش، لهل، شارکوزی و شلپ حدس زدند که در هر رنگ‌آمیزی یالی از $\\mathcal{K}_n^r$ با $r-?$ رنگ، یک دور برج هامیلتونی تک‌رنگ یافت می‌شود. آن‌ها این حدس را برای $r=?$ اثبات کردند و هم‌چنین نتایجی برای $r=?$ و در حالت کلی برای $r$ دلخواه به کمک لم منظمی زمردی به دست آوردند. در این رساله این حدس را برای حالت $r=?$، اولین حالت باز، ثابت می‌کنیم. هم‌چنین نتایج به دست آمده روی عدد رمزی دورهای $t$-تایت برج را بهبود می‌دهیم. در این رساله هم‌چنین با معرفی ابرگراف $r$-یکنواخت برج کامل، مقدار دقیق عدد توران خانواده‌ی تمام ابرگراف‌های $?$-یکنواخت $K_n$-برج، $\\mathcal{B}_?(K_n)$، را تعیین کرده و ساختار اکسترمال آن را مشخص می‌کنیم.

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