二部圖的幾個(gè)Ramsey函數(shù).pdf_第1頁
已閱讀1頁,還剩52頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、1930年,英國數(shù)學(xué)家Frank Ramsey在其論文《On a problem of formallogic》[90]中得到了后來以他的名字命名的Ramsey定理.特別地,如果一個(gè)圖含有足夠多的頂點(diǎn)數(shù),則該圖含有一個(gè)頂點(diǎn)數(shù)為n的團(tuán)或者頂點(diǎn)數(shù)為n的獨(dú)立集.Ramsey定理經(jīng)過許多科學(xué)工作者的擴(kuò)充和推廣,逐步形成了Ramsey理論.作為圖論中一類極值問題,圖的Ramsey理論是當(dāng)代圖論的一個(gè)重要分支.
   本文第一章介紹Rams

2、ey理論的起源、研究意義和研究內(nèi)容.
   第二章介紹星類圖的Ramsey數(shù).我們得到若G是給定的圖滿足x(G)=k≥2且s(G)=s(這里s(G)是G的色剩余,即G的所有x(G)可著色中最小色部的點(diǎn)數(shù)),并且H是給定的階數(shù)為h的圖,則r(K1+G,K1+nH)≤k(hn+s-1)+1對所有充分大的整數(shù)n成立.特別地,如果s是奇數(shù)或者s是偶數(shù)且hn是奇數(shù),則r(K1+Kk(s),K1+nH)=k(hn+s-1)+1.另外,對所有

3、充分大的n,有r(Fs,K1+nH)=2hn+1.
   第三章介紹一類含密集圖的Ramsey數(shù)及其二部形式.第一部分我們分別給出了一個(gè)二部Ramsey數(shù)的階以及一個(gè)二部Ramsey數(shù)的界.我們得到若t≥1是給定的整數(shù),則br(Kt,n,Kn,n)的階是nt+1/(logn)t.另外,若H是給定的具有色部為(A,B)階數(shù)為h的二部圖,且滿足△(B)≤t,則對所有充分大的n,有br(H,Kn,n)≤(hn/logn)t(logn)

4、a(t),其中a(1)=a(2)=1,a(t)=0若t≥3.第二部分我們獲得了brk(C4;Kn,n)的階是n2/log2n對k≥3都成立,且br2(C4;Kn,n)≥c(nloglogn/log2 n)2對充分大的n成立.第三部分我們給出了一個(gè)Ramsey數(shù)的下界,這個(gè)界漸近可達(dá).設(shè)v(F)和e(F)分別表示圖F的階數(shù)和邊數(shù),p(F)=e(F)-1/V(F)-2.我們得到若F是給定的連通圖,Gn是一列階數(shù)為n平均度是dn≥2的圖,則存

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論