Ramsey 수치에 대한 건설적인 하한
Ramsey의 정리는 다음과 같이 말합니다.
주어진 $s, t\in \mathbb{N}$, 있습니다 $n\in \mathbb{N}$ 모든 그래프에 대해 $n$ 정점, 그것은 $s$-clique 또는 그 보완 물에는 $t$-도당.
가장 작은 $n$ 진술을 만족하는 것은 다음과 같이 표시됩니다. $R(s, t)$.
나는 "The Probabilistic Method in Combinatorics, Lectures by Niranjan Balachandran" 에서 다음 진술을 발견했습니다.
Nagy가 발견 한 R (s, s)에 대한 건설적인 하한은 다음과 같습니다. $$R(s, s)\ge \binom{s}{3}$$ (명백하게 그의 구성은 다음과 같습니다. $S$, 모든 컬렉션을 설정 $3$-요소 하위 집합 $S$ 교차점이 홀수 인 경우 하위 집합을 연결하여 그래프로 만듭니다.)
나는이 그래프와 그 보완에 포함되지 않는다는 것을 증명할 수 없었습니다. $s$-파벌. 이 문제에 대한 도움을 주시면 감사하겠습니다.
답변
해 보자 $S = \{1, 2, \dots, s\}$. 실제로 보여줄 수있는 것은 Nagy의 그래프가
- 최대 크기의 파벌 $\max\{7, \frac{s-1}{2}\}$, 및
- 최대 크기의 독립 세트 $s-1$ 이하 $s \not\equiv 0 \pmod 4$, 최대 $s$ 언제 $s \equiv 0 \pmod 4$.
이것은 $R(s,s) \ge \binom s3$ 모든 $s$, 그러나 그것은 $R(s,s) > \binom s3$, 심지어 그 $R(\frac{s}{2}, s) > \binom s3$, 무한히 많은 값 $s$.
먼저 가장 큰 파벌을 찾아 봅시다. 두 가지 경우가 있습니다.
- 파벌 포함 $4$ 동일한 요소에서 교차하는 정점 $S$: 말, $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$, 및 $\{1,8,9\}$. 그런 다음 다른 모든 정점에는$1$: 그렇지 않으면 각각의 요소가 있어야합니다. $\{2,3\}$, $\{4,5\}$, $\{6,7\}$, 및 $\{8,9\}$, 불가능합니다. 그러한 파벌은 기껏해야$\frac{s-1}{2}$ 정점.
- 파벌에는 최대 $3$ 동일한 요소에서 교차하는 정점 $S$. 말하다$\{1,2,3\}$꼭지점 중 하나입니다. 그런 다음 기껏해야$2$ 각각을 포함하는 다른 정점 $1$, $2$, 또는 $3$, 그래서 파벌은 최대 $7$ 정점.
다음으로 가장 큰 독립 집합을 찾아 보겠습니다. 여기에서 독립 세트의 두 정점이$2$ 요소 및 독립 세트 공유의 세 번째 정점 $2$ 요소 중 하나와 요소를 공유하려면 하나 이상의 요소를 공유해야합니다 (따라서 $2$요소). 따라서 독립 세트는 클러스터로 구성되어야합니다. 여기서 클러스터의 두 정점은$2$ 요소 및 클러스터 공유 외부의 두 정점 $0$.
다시 한 번, 클러스터는 두 가지 다른 모양을 가질 수 있습니다.
- 클러스터에 $3$ 모두 같은 것을 공유하는 정점 $2$ 요소 : 말, $\{1,2,3\}$, $\{1,2,4\}$,과 $\{1,2,5\}$. 다음 중 하나만 포함 된 클러스터의 다른 정점$\{1,2\}$ 각각을 포함해야 $3$, $4$, 및 $5$, 불가능합니다. 따라서 클러스터는$k$ 형태의 정점 $\{1,2,x\}$, "사용" $k+2$ 요소 $S$.
- 클러스터에 최대 $2$ 공유하는 정점 $2$집단. 그렇다면$\{1,2,3\}$ 클러스터의 정점이고, 클러스터의 서로 정점은 다음 중 두 개를 포함해야합니다. $\{1,2,3\}$이지만 각 종류는 최대 하나만있을 수 있습니다. $4$정점 총. 이것들은 최소한 다 써야합니다$4$ 요소 $S$와 같은 $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.
우리는 클러스터가 $k$ 요소 $S$ 최대 포함 가능 $k$ 따라서 전체 클러스터는 최대 $S$정점. 그러나 이것은 모든 클러스터가 두 번째 유형이고 모든 요소를 포함하는 경우에만 가능합니다.$S$, 필요한 $s \equiv 0 \pmod 4$.