Erdős-Ko-Rado 定理的變體：Borg 和 Erdős-Rothschild 問題

Abstract

給定一個整數 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.