| 【中文题名】 | 一致超图的Ramsey性质与代数性质 |
| 【英文题名】 | Ramsey Property and Algebraic Property of Hypergraph |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-4-20 |
| 【中关键词】 | 一致超图,Ramsey性质,代数性质,局部引理,谱半径, |
| 【英关键词】 | Uniform Hypergraph,Ramsey Property,Algebraic Property,Local Lemma,Spectral Radius, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论的应用> |
| 【论文摘要】 | 作为一般图得推广,超图特别是一致超图能够更好得刻画现实生活中的问题。本文着重讨论了一致超图的Ramsey性质与代数性质。首先利用现代图论研究中普遍采用的概率方法和Lovász局部引理,我们分别得到了关于一致超图独立数的下界以及对称与非对称的双色Ramsey数下界估计,同时还得到了多色Ramsey数的下界。本文的另一主要内容是关于一致超图谱半径的讨论。利用Perron-Frobenius定理我们通过讨论一致超图邻接矩阵的行和来研究图的谱半径,同时还引入一个与超图邻接矩阵相似的矩阵,通过研究相似矩阵特征根来分析原来矩阵的特征根,也得到了较好的结果。 |
| 【论文题纲】 |
|
摘要 |
9-10 |
|
Abstract |
10-11 |
|
第一章 预备知识 |
11-26 |
|
§1 基本概念与符号说明 |
11-12 |
|
§2 一致超图的基本概念 |
12-13 |
|
§3 图论中的概率方法 |
13-20 |
|
§3.1 概率论中的基本知识 |
13-15 |
|
§3.2 两个重要的不等式 |
15-17 |
|
§3.3 Stirling公式 |
17-18 |
|
§3.4 两个常见的分布 |
18-20 |
|
§4 随机图的基本模型 |
20-22 |
|
§5 Lovász局部引理 |
22-26 |
|
第二章 一致超图的Ramsey性质 |
26-43 |
|
§6 引言 |
26-28 |
|
§7 一致超图的Ramsey数下界的渐进估计 |
28-35 |
|
§8 一致超图的独立数 |
35-37 |
|
§9 一致超图Ramsey数的推广 |
37-39 |
|
§10 一致超图在通讯中的运用及其与Ramsey数的联系 |
39-43 |
|
§10.1 通讯频道的特征图 |
39-40 |
|
§10.2 多重利用的通讯频道与超图的积 |
40-41 |
|
§10.3 Ramsey数与Shannon容量 |
41-43 |
|
第三章 一致超图的代数性质 |
43-56 |
|
§11 有关代数图论的基本知识 |
43-44 |
|
§12 一致超图特征多项式的性质 |
44-51 |
|
§13 一致超图谱半径的上界估计 |
51-56 |
|
结束语 |
56-58 |
|
致谢 |
58-59 |
|
参考文献 |
59-63 |
|
| 【DOI】 | LunWen.ID:2.2008.11610 |
