헤일스-주에트 정리
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
헤일스-주에트 정리는 주어진 양의 정수 n과 c에 대해, n개의 문자를 가진 알파벳으로 구성된 길이 H의 단어 집합 WnH를 c개의 부분으로 분할할 때, 전체 조합적 선을 포함하는 부분이 적어도 하나 존재하도록 하는 양의 정수 H가 n과 c에 따라 존재한다는 정리이다. 이 정리는 하이퍼큐브의 조합적 선과 관련된 문제로, 반 데르 와르덴 정리를 일반화하며, 밀도 버전과 고차원 조합 큐브에 대한 그레이엄-로스차일드 정리로 일반화된다.
더 읽어볼만한 페이지
- 이산수학 정리 - 애로의 불가능성 정리
애로의 불가능성 정리는 3개 이상의 선택지에서 약한 파레토, 무관한 대안으로부터의 독립성, 비독재성을 모두 만족하는 사회 후생 함수는 존재하지 않음을 증명한 정리이다. - 이산수학 정리 - 비둘기집 원리
비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 간단한 원리이며, 귀류법으로 증명되고, 소프트볼 팀 구성, 해시 테이블 충돌 등 다양한 분야에 응용된다. - 램지 이론 - 램지의 정리
램지의 정리는 주어진 조건을 만족하는 램지 수가 존재한다는 정리로, 그래프 이론으로 해석되며, 특정 크기의 동색 클릭이 존재함을 보장하고, 램지 이론의 시초로 여겨진다. - 램지 이론 - 비둘기집 원리
비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 간단한 원리이며, 귀류법으로 증명되고, 소프트볼 팀 구성, 해시 테이블 충돌 등 다양한 분야에 응용된다.
| 헤일스-주에트 정리 | |
|---|---|
| 헤일스-주에트 정리 | |
| 분야 | 조합론 |
| 하위 분야 | 램지 이론 |
| 같이 보기 | |
| 관련 항목 | 램지 이론 |
2. 형식적 정의
헤일스-주에트 정리는 램지 이론의 중요한 결과 중 하나로, 고차원 하이퍼큐브의 점들을 유한 개의 색으로 칠할 때, 특정 구조(조합적 선)가 반드시 단색으로 나타남을 보장한다.
형식적으로 정의하면 다음과 같다. ''n''개의 문자로 이루어진 알파벳 {1, 2, ..., ''n''}을 사용하여 만들 수 있는 길이 ''H''의 모든 단어(수열)의 집합을 ''W''''H''''n''이라고 하자. 이 집합은 ''n''''H''개의 원소를 가지며, 기하학적으로 ''H''차원 하이퍼큐브로 볼 수 있다.
헤일스-주에트 정리는 임의의 양의 정수 ''n'' (알파벳 크기)과 ''c'' (색깔의 수)에 대해, 충분히 큰 양의 정수 ''H'' (차원)가 존재하여 다음 성질을 만족한다고 말한다: ''W''''H''''n''의 원소들을 ''c''개의 색깔로 어떻게 칠하든 (즉, ''W''''H''''n''을 ''c''개의 부분집합으로 어떻게 분할하든), 반드시 모든 원소가 같은 색깔로 칠해진 조합적 선이 적어도 하나 존재한다.[1] 이 최소의 ''H'' 값을 ''HJ''(''n'', ''c'')로 표기하기도 한다. 조합적 선의 구체적인 정의는 #조합적 선 섹션에서 다룬다.
2. 1. 조합적 선
''W''''H''''n''을 ''n''개의 문자를 가진 알파벳으로 구성된 길이 ''H''의 단어 집합이라고 하자. 즉, {1, 2, ..., ''n''}의 원소로 이루어진 길이 ''H''인 수열들의 집합이다. 이 집합은 일종의 하이퍼큐브를 형성한다.
''W''''H''''n''에 대한 변수 단어 ''w''(''x'')는 길이가 ''H''인 단어이지만, 최소한 하나의 위치에 일반 문자 대신 특수한 기호 ''x''를 포함한다. 이 변수 단어 ''w''(''x'')에서 특수 기호 ''x''가 나타나는 모든 위치에 1, 2, ..., ''n''을 순서대로 대입하여 얻어지는 ''n''개의 단어들, 즉 ''w''(1), ''w''(2), ..., ''w''(''n'')은 공간 ''W''''H''''n''에서 조합적 선을 형성한다. 조합적 선은 하이퍼큐브에서의 행, 열, 그리고 특정 대각선들에 해당한다고 볼 수 있다.
헤일스-주에트 정리는 임의의 양의 정수 ''n''과 ''c''가 주어졌을 때, 충분히 큰 양의 정수 ''H'' (''n''과 ''c''에 따라 결정됨)가 존재하여, ''W''''H''''n''의 원소들을 ''c''개의 부분집합으로 어떻게 나누더라도 (색칠하더라도), 그중 적어도 하나의 부분집합은 반드시 온전한 조합적 선 하나를 포함하게 된다는 것을 말한다.
예를 들어, ''n'' = 3, ''H'' = 2, ''c'' = 2인 경우를 생각해보자. 이때 하이퍼큐브 ''W''23는 3x3 격자로 표현할 수 있으며, 이는 일반적인 틱택토 게임판과 같다. 총 9개의 위치(단어)가 있다.
| 11 | 12 | 13 |
| 21 | 22 | 23 |
| 31 | 32 | 33 |
이제 위에서 논의한 ''n'' = 3, ''c'' = 2, ''H'' = 8인 특수한 경우에 대해 헤일스-주에트 정리를 증명한다. 증명의 기본 아이디어는 이 문제를 헤일스-주에트 정리의 더 간단한 버전(이 특정 경우에는 ''n'' = 2, ''c'' = 2, ''H'' = 2 및 ''n'' = 2, ''c'' = 6, ''H'' = 6인 경우)으로 축소하는 것이다. 수학적 귀납법을 사용하여 유사한 방식으로 헤일스-주에트 정리의 일반적인 경우를 증명할 수 있다.
이 격자에서 대표적인 조합적 선의 예시는 변수 단어 `2x`에서 만들어지는 선 {21, 22, 23}이다. 또 다른 예시는 변수 단어 `xx`에서 만들어지는 대각선 {11, 22, 33}이다. (틱택토 게임에서는 {13, 22, 31}도 유효한 승리 선이지만, 이는 여기서 정의한 조합적 선에는 해당하지 않는다.)
이 특정 경우(''H'' = 2), 헤일스-주에트 정리는 아직 적용되지 않는다. 예를 들어, 9개의 위치를 {11, 22, 23, 31}과 {12, 13, 21, 32, 33}의 두 집합으로 나누면, 두 집합 모두 완전한 조합적 선을 포함하지 않는다. (이는 틱택토 게임에서 무승부가 가능한 상황에 해당한다.)
하지만 만약 ''H''를 8로 늘리면 (즉, 8차원 공간에 38 = 6561개의 위치가 있는 격자), 헤일스-주에트 정리에 따라 이 격자를 두 개의 집합("O"와 "X")으로 어떻게 나누든, 둘 중 하나는 반드시 조합적 선을 포함하게 된다. 즉, 이 변형된 틱택토 게임에서는 무승부가 불가능하다.
3. 증명 (특수한 경우)
초입방체 ''W''38의 각 요소는 {1, 2, 3} 중 하나의 값을 갖는 8개의 좌표로 이루어진 점, 즉 길이 8의 문자열이다. 예를 들어 '13211321'은 이 초입방체의 한 점이다. 이 초입방체의 모든 점이 "O" 또는 "X" 두 가지 색깔 중 하나로 칠해져 있다고 가정하자. 귀류법을 사용하여, 어떤 조합선도 단색("O"만 또는 "X"만)이 아니라고 가정한다.
이제 문자열의 처음 여섯 좌표를 고정하고 마지막 두 좌표만 변경하는 경우를 생각해보자. 이는 일반적인 틱택토 보드와 유사한 구조를 만든다. 예를 들어, "abcdef??" 형태의 점들은 이러한 2차원 '보드'를 형성한다. 각 보드 "abcdef??"에 대해, 세 점 "abcdef11", "abcdef12", "abcdef22"를 고려하자. 이 세 점은 각각 "O" 또는 "X"로 칠해져야 하므로, 비둘기집 원리에 의해 적어도 두 점은 같은 색깔을 갖는다. 우리의 가정(단색 조합선이 없다)에 따라, 만약 두 점이 같은 색이면, 그 두 점을 포함하는 특정 조합선의 세 번째 점은 반드시 반대 색이어야 한다. 구체적으로 다음 관계가 성립한다:
따라서, 각 6차원 초입방체 ''W''36의 점 "abcdef"에 대해, 다음 여섯 가지 경우 중 적어도 하나가 성립한다.
# abcdef11과 abcdef12는 "O"이다. 따라서 abcdef13은 "X"이다.
# abcdef11과 abcdef22는 "O"이다. 따라서 abcdef33은 "X"이다.
# abcdef12와 abcdef22는 "O"이다. 따라서 abcdef32은 "X"이다.
# abcdef11과 abcdef12는 "X"이다. 따라서 abcdef13은 "O"이다.
# abcdef11과 abcdef22는 "X"이다. 따라서 abcdef33은 "O"이다.
# abcdef12와 abcdef22는 "X"이다. 따라서 abcdef32은 "O"이다.
이제 ''W''36의 점들을 위 여섯 가지 유형(클래스)으로 분류할 수 있다. (만약 한 점이 여러 유형에 해당하면, 목록에서 가장 먼저 나오는 유형으로 임의로 배정한다.)
다음으로 ''W''36 내에서 특별한 7개의 점을 고려한다: 111111, 111112, 111122, 111222, 112222, 122222, 222222. 비둘기집 원리에 의해, 이 7개의 점 중 적어도 두 개는 위에서 정의한 여섯 클래스 중 같은 클래스에 속해야 한다.
예를 들어, 111112와 112222가 둘 다 클래스 (5)에 속한다고 가정해보자. 클래스 (5)의 정의에 따라 다음이 성립한다.
이제 점 11333233의 색깔을 생각해보자. 이 점은 "O" 또는 "X"여야 한다.
어떤 경우든 모순이 발생한다. 이는 ''W''36의 7개 점 중 어떤 두 점이 같은 클래스에 속하든 유사한 방식으로 모순을 유도할 수 있다. 따라서 초기 가정, 즉 단색 조합선이 존재하지 않는다는 가정이 거짓임에 틀림없다. 결론적으로, "O" 또는 "X"로만 구성된 조합선이 적어도 하나는 반드시 존재해야 한다.
위의 논증은 다소 비효율적이었다. 실제로 동일한 정리는 ''H'' = 4에 대해서도 성립한다.[2] 위의 논증을 ''n''과 ''c''의 일반적인 값으로 확장하면 ''H''는 매우 빠르게 증가한다. ''c'' = 2인 경우(두 플레이어 틱택토에 해당)에도 위 논증에서 얻어지는 ''H''의 하계는 아커만 함수와 유사한 속도로 매우 빠르게 증가한다. 첫 번째 원시 재귀적 상계는 사하론 쉘라에 의해 증명되었으며,[3] 이는 현재까지 알려진 헤일스-주에트 수 ''H''(''n'', ''c'')에 대한 가장 좋은 일반적인 상계이다.
4. 다른 정리와의 관계
헤일스-주에트 정리는 여러 중요한 조합론 정리들과 깊은 관련을 맺고 있다. 특히, 반 데르 와르덴 정리를 일반화하며, 이는 헤일스-주에트 정리의 조합 선(combinatorial line) 개념이 특정 조건 하에서 등차수열을 포함하기 때문에 본질적으로 더 강력한 내용을 담고 있다고 평가받는다.
반 데르 와르덴 정리가 세메레디 정리라는 더 강력한 '밀도 버전'을 가지는 것처럼, 헤일스-주에트 정리 역시 유사한 밀도 버전을 가진다. 이 밀도 헤일스-주에트 정리는 특정 밀도를 가진 하이퍼큐브 ''W''''n''''H''의 부분 집합 내에 반드시 전체 조합 선이 존재함을 보인다. 이 밀도 버전에 대한 증명은 에르고딕 이론[4]이나 폴리매스 프로젝트[5][6][8] 등을 통해 이루어졌다.
더 나아가, 헤일스-주에트 정리는 고차원 조합 큐브에 대한 그레이엄-로스차일드 정리로 일반화될 수 있다.
4. 1. 반 데르 바에르던 정리
헤일스-주에트 정리는 반 데르 와르덴 정리를 일반화한다. 이는 헤일스-주에트 정리에서 다루는 조합 선(combinatorial line)이 십진법 표기에서 등차수열을 형성하기 때문이다. 예를 들어, 각 자리 숫자가 1, 2, 3 중 하나인 8자리 숫자들의 집합 ''A''를 두 가지 색으로 칠하면, 반드시 같은 색을 가진 길이가 3인 등차수열이 존재한다. 이처럼 헤일스-주에트 정리는 반 데르 와르덴 정리보다 본질적으로 더 강력한 정리로 평가받는다.반 데르 와르덴 정리가 세메레디 정리라는 더 강력한 '밀도 버전'을 가지는 것처럼, 헤일스-주에트 정리 역시 밀도 버전을 갖는다. 이 강화된 밀도 헤일스-주에트 정리는 전체 하이퍼큐브 ''W''''n''''H''를 여러 색으로 칠하는 대신, 주어진 밀도 0 < δ < 1을 갖는 하이퍼큐브 ''W''''n''''H''의 임의의 부분 집합 ''A''를 고려한다. 이 정리는 ''H''가 ''n''과 δ에 따라 충분히 크면, 집합 ''A''는 반드시 전체 조합 선을 포함해야 한다고 명시한다.
밀도 헤일스-주에트 정리는 원래 퍼스텐버그(Hillel Furstenberg)와 카츠넬슨(Yitzhak Katznelson)이 에르고딕 이론을 사용하여 증명했다.[4] 2009년에는 폴리매스 프로젝트가 코너 정리(Corners theorem) 증명의 아이디어를 바탕으로 새로운 증명을 개발했으며,[5][6] 이후 도도스(Pandelis Dodos), 카넬로풀로스(Vassilis Kanellopoulos), 타이로스(Konstantinos Tyros)가 이 증명을 단순화했다.[8]
헤일스-주에트 정리는 고차원 조합 큐브(combinatorial cube)에 대한 그레이엄-로스차일드 정리로 일반화된다.
4. 2. 세메레디 정리
반 데르 와르덴 정리가 세메레디 정리라는 더 강력한 '밀도 버전'을 가지는 것처럼, 헤일스-주에트 정리 역시 밀도 버전을 갖는다. 밀도 헤일스-주에트 정리는 전체 하이퍼큐브 ''W''''n''''H''를 여러 색으로 칠하는 대신, 주어진 밀도(0 < δ < 1)를 가진 하이퍼큐브 ''W''''n''''H''의 임의의 부분 집합 ''A''를 다룬다. 이 정리는 ''H''가 ''n''과 δ에 따라 충분히 크다면, 집합 ''A''는 반드시 하나의 완전한 조합 선을 포함해야 함을 명시한다.밀도 헤일스-주에트 정리는 퍼스텐버그와 카츠넬슨이 에르고딕 이론을 사용하여 처음 증명하였다.[4] 이후 2009년, 폴리매스 프로젝트는 코너 정리 증명의 아이디어를 활용하여 밀도 헤일스-주에트 정리의 새로운 조합론적 증명을 제시했다.[5][6] 도도스, 카넬로풀로스, 타이로스는 이 폴리매스 증명을 더 단순화한 버전을 발표했다.[8]
참조
[1]
논문
Regularity and positional games
[2]
논문
The first nontrivial Hales-Jewett number is four
http://nhindman.us/r[...]
[3]
논문
Primitive recursive bounds for van der Waerden numbers
[4]
논문
A density version of the Hales–Jewett theorem
[5]
논문
A new proof of the density Hales–Jewett theorem
[6]
간행물
An irregular mind
János Bolyai Mathematical Society
[7]
논문
Sets of lattice points that form no squares
[8]
논문
A simple proof of the density Hales–Jewett theorem
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com