Skip navigation

DSpace

機構典藏 DSpace 系統致力於保存各式數位資料(如:文字、圖片、PDF)並使其易於取用。

點此認識 DSpace
DSpace logo
English
中文
  • 瀏覽論文
    • 校院系所
    • 出版年
    • 作者
    • 標題
    • 關鍵字
  • 搜尋 TDR
  • 授權 Q&A
    • 我的頁面
    • 接受 E-mail 通知
    • 編輯個人資料
  1. NTU Theses and Dissertations Repository
  2. 理學院
  3. 數學系
請用此 Handle URI 來引用此文件: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/96530
標題: Erdős-Ko-Rado 定理的變體:Borg 和 Erdős-Rothschild 問題
Variations of the Erdős-Ko-Rado theorem: Borg and Erdős-Rothschild Problem
作者: 林楷庭
Kai-Ting Lin
指導教授: 戴尚年
Shagnik Das
關鍵字: Erdős–Ko–Rado 定理,標記集合,交叉集合族,Erdős–Rothschild 定理,集合著色,
Erdős–Ko–Rado,signed sets,intersecting family,Erdős–Rothschild,set colouring,
出版年 : 2025
學位: 碩士
摘要: 給定一個整數 t,如果一個集合族中的任意兩個集合的交集大小至少為 t,則稱該集合族為 t 交叉的(t-intersecting ),當 t = 1 時,則簡稱為交叉的(intersecting)。

考慮 {1, 2, ..., n} 的所有大小為 k 的集合所形成的集合族。跟據Erdős–Ko–Rado 定理,如果 n 小於等於 2k,那麼在該集合族所有的交叉的集合子族中,平凡的集合族(即包含一個單點的所有集合所形成的集合族)的大小會達到最大值。在本文中,我們介紹了關於該定理的兩類相關推廣問題。

第一類是討論 r 標記集合(r-signed sets )上的問題。給定整數 r,一個 r 標記集合由一個集合 F 和一個定義在其上,取值為 1 至 r 的函數組成。我們將探討 Borg 提出的兩個相關猜想,並解釋其與 Chvátal 和 Kleitman 猜想的關係。

第二部分當中,我們引入了另一個擴展該問題的方向,也就是將Erdős–Rothschild 問題的核心想法引入交叉集合族中。在這一問題裡,需要最大化的目標從集合族的大小變為集合族的 3 著色(3-coloring)數量,且要求每個種顏色的集合族都是 t 交叉的。
Given an integer t, a set family is called t-intersecting if any two sets in it have an intersection of size at least t and is abbreviated as intersecting if t = 1.

Let ([n]k) denote all subsets of {1, 2, . . . , n} with size k. The Erdős–Ko–Rado theorem says that if n is at least 2k, then the size of an intersecting family in ([n]k) is maximized by the trivial one, which means an intersecting family consisting of a common element. There are many different ways of generalizing the theorem, and we introduce two related problems in this thesis.

The first is to consider the question on the r-signed sets, which is a pair of a set F and a function on it with values ranging from 1 to r, where r is a given integer. We will discuss two related conjectures proposed by Borg and explain the relation with Chvátal’s and Kleitman’s Conjectures.

In the second part, we introduce another variant problem extended with the idea of the Erdős–Rothschild problem. In this question, the target that should be maximized is changed from the size of a set family to the number of 3colorings of a set family such that each monochromatic part is t-intersecting.
URI: http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/96530
DOI: 10.6342/NTU202500207
全文授權: 同意授權(全球公開)
電子全文公開日期: 2025-02-20
顯示於系所單位:數學系

文件中的檔案:
檔案 大小格式 
ntu-113-1.pdf373.6 kBAdobe PDF檢視/開啟
顯示文件完整紀錄


系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。

社群連結
聯絡資訊
10617臺北市大安區羅斯福路四段1號
No.1 Sec.4, Roosevelt Rd., Taipei, Taiwan, R.O.C. 106
Tel: (02)33662353
Email: ntuetds@ntu.edu.tw
意見箱
相關連結
館藏目錄
國內圖書館整合查詢 MetaCat
臺大學術典藏 NTU Scholars
臺大圖書館數位典藏館
本站聲明
© NTU Library All Rights Reserved