관련링크 http://www.todayhumor.co.kr/board/view.php?table=humordata&no=1948593

X라는 유한집합을 가정합시다. 이번 글에서는 설명의 편의를 위해 예시로 X={1,2,3}라 합시다.

X의 멱집합을 Y라고 표기합시다. 멱집합은 X의 부분집합들의 집합으로, 이 경우 Y = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}가 됩니다. （∅는 공집합을 의미）

p를 0 이상 1 이하의 수로 골라줍니다. 예를 들어 p = 1/3이라고 합시다.

X의 부분집합 A를 가정합시다. 예를 들어 A = {1,2}로 둡시다.

집합 A의 크기를 |A|라고 표기합시다.

A의 여집합은 A에 포함되지 않은 원소들의 집합입니다. A의 여집합은 X\A로 표기하며, 그것의 크기는 |X\A|라고 표기합니다.

위 예제의 경우, A에는 2개의 원소 뿐이므로 |A|는 2이고, A의 여집합은 {3}이므로 |X\A|는 1가 됩니다.

A의 측량이라는 것을 정의합시다. A의 측량은 m（A）라 표기하고, 이를 다음과 같이 정의합시다.

m（A） = p^|A|（1-p）^|X\A|

위의 경우를 예로 들면 p = 1/3, |A| = 2, |X\A| = 1이므로, A의 측량은 m（A） = （1/3）^2（1-1/3）^1 = （1/3）^2 * （2/3）^1 = 2/27이 됩니다.

이제 X의 멱집합 Y의 부분집합 F를 가정합시다. 예컨대 F = {{1,2}, {1,2,3}}이라고 합시다.

F의 측량을 F의 각 원소들의 측량의 합이라고 정의합시다.

위의 예제의 경우 F는 {1,2}이라는 집합과 {1,2,3}이라는 집합들로 이뤄져 있습니다. 이를 각각 A와 B라고 둡시다. 그렇다면 F의 측량은 A의 측량 + B의 측량, 즉 m（F） = m（A） + m（B）입니다.

m（A）는 위에서 이미 구했듯, 2/27이고, m（B）는 직접 계산해보면 1/27이 됩니다. 즉 m（F）는 둘의 합인 3/27 = 1/9가 되는군요.

지금까지의 정의를 요약하자면... 0과 1사이의 숫자 p를 정의함으로서

1） X의 부분집합의 측량을 정의할 수 있었다.

2） X의 부분집합들로 이뤄진 집합 F의 측량을 정의할 수 있었다.

여기에 덧붙여 F가 다음의 성질을 만족한다고 가정합시다.

1） 만약 C가 F의 원소이고, C가 D에 포함되어 있다면, D 역시 F의 원소여야 한다.

2） F는 공집합이거나 전체 집합 Y여선 안된다.

위의 조건들을 만족하면 F를 모노톤 패밀리라고 부르도록 합시다.

우리가 앞서 선보인 예제 F는 위의 조건을 만족합니다. F에는 두개의 원소, {1,2}와 {1,2,3}뿐이었으므로, 공집합도, Y도 아닙니다. 즉 두번째 조건을 만족합니다.

첫번째 조건은 어떨까요? 먼저 C에 {1,2}를 대입해봅시다. X = {1,2,3}의 부분집합 중 C를 포함하고 있는 부분집합은 {1,2}와 {1,2,3} 뿐이며, 이들은 F의 원소입니다. C에 {1,2,3}을 대입한다면, C는 곧 X이므로, 그것을 포함하고 있는 부분집합은 곧 X 자기 자신밖에 없습니다. 그리고 이들은 모두 F의 원소로 이미 포함되어 있지요. 즉 우리가 정의한 F는 첫번째 조건 또한 만족합니다.

첫번째 조건을 만족하지 않는 F의 예로는 {{1}, {1,2,3}}이 있습니다. {1,2}는 {1}을 포함하는 X의 부분집합인데 이 F에는 {1,2}가 원소로 없기 때문이지요.

F가 모노톤 패밀리라고 가정합시다. 이 경우 F의 문턱값은 F의 측량이 정확히 1/2이 되도록 하는 p값입니다. 앞서, 우리는 p가 1/3이라면 F의 측량이 1/9가 된다는 사실을 보였습니다. F의 측량이 1/2이 되도록 하려면 p 값을 다시 조정하는 수 밖에 없습니다. F에는 A={1,2}와 B={1,2,3}라는 원소만을 포함하고 있습니다. p값을 x라고 두고, F의 측량을 계산하면

m（F） = x^2（1-x）^1 + x^3（1-x）^0이 됩니다. 이 값이 1/2이 되도록 하는 0과 1 사이의 x값은 계산해보면 1/√2가 됩니다. 즉 우리가 상정한 예제에선 F의 문턱값은 1/√2이군요. 이 문턱값을 t（F）라고 표기합시다.

여기서 Y의 부분집합 G를 가정합니다. （G는 X의 멱집합인 Y의 부분집합이므로, G의 원소들은 각각 X의 부분집합입니다.） 이 경우 는 G의 원소들을 포함하고 있는 X의 부분집합들로 이뤄진 집합이라고 합시다.

예컨대 G = {{1,2},{1,3}}이라고 한다면...

{1,2}를 포함하고 있는 X의 부분집합은 {1,2}와 {1,2,3}

{1,3}을 포함하고 있는 X의 부분집합은 {1,3}과 {1,2,3}

그러므로 는 {{1,2}, {1,3}, {1,2,3}}입니다.

만약 F라는 모노톤 패밀리가 주어졌을 때, Y의 부분집합 G가 있어, F가 에 포함되어 있다면, G를 F의 커버라고 부릅니다.

G가 F의 커버일 때, G의 각각의 원소들 S에 대해서 p^|S|들의 합이 1/2 이하라면, F를 p-small 이라고 부릅시다.

예컨대 p = 1/3, X = {1,2,3}, G = {{1,2},{1,3}}, F = {{1,2}, {1,2,3}}이라고 합시다. 먼저 = {{1,2}, {1,3}, {1,2,3}}이므로 F를 포함하고 있습니다. 즉 G는 F의 커버입니다. 또한 G는 {1,2}와 {1,3}이라는 원소가 2개인 집합 2개로 이뤄져 있습니다. G의 원소들 S에 대해서 p^|S|의 합은...

（1/3）^2 + （1/3）^2가 되는데 이 값은 2/9로 1/2보다 작습니다. 그러므로 이 경우, F는 1/3-small이라고 부를 수 있습니다.

q（F）는 기대-문턱값이라는 값으로 F가 p-small이라는 조건을 만족하게 만드는 가장 큰 p값을 말합니다. （이 값은 계산이 복잡해 넘기겠습니다. F의 모든 커버들을 구한 뒤, p = x라고 두고, 각 커버들의 측량을 모두 구한 뒤, 그 값이 1/2이하가 되도록 x값을 찾아야해서 계산이 좀 복잡합니다.）

정말 마지막으로 l（F）는 F의 원소들 중 가장 크기가 큰 원소의 크기로 합니다. F는 크기가 2인 집합 {1,2}와 크기가 3인 집합 {1,2,3}을 포함하고 있으므로 l（F）는 3이 됩니다.

한국인 수학자 박진영씨가 후이 투안 팜과 같이 협력해 해결한 문제인 칸-칼라이 추측은 다음과 같습니다.

칸-칼라이 추측: 유한집합 X와 모노톤 패밀리 F가 무엇이든 상관없이 다음의 부등식을 만족하는 상수 K는 존재하는가?

t（F） ≤ K q（F） log（l（F））

（t（F）는 F의 문턱값, q（F）는 F의 기대-문턱값, log는 자연로그, l（F）는 F의 원소 중 가장 크기가 큰 집합의 크기）

그리고 박진영씨와 동료 수학자 후이투안팜씨는 그러한 상수 K가 존재함을 고작 6페이지의 짧은 논문을 통해 증명했습니다.

=======================================================================================

굉장히 글이 길어졌는데, 아무래도 계속해서 예제를 보이며, 각각의 값을 설명하려다보니 그렇게 된 것 같습니다.

칸-칼라이 추측을 이해하는데 필요한 재료들이 많아서 복잡해 보이지만, 사실 문제 자체는 쉬운 편의 추측에 속합니다. 칸-칼라이 추측의 가장 기본 재료는 우리에게 친숙한 집합이란 녀석이라서요. （사실 다른 추측들은 첫 문장을 이해하는데 필요한 개념을 소개하는데도 수페이지 필요합니다.）

물론 문제를 이해하는 것과 문제를 푸는 것은 또 완전히 다른 세상의 이야기지요. 저도 문제는 얼추 이해할 수 있었는데, 이걸 풀라고 하면 어디서부터 시작해야할지 도통 감을 못 잡을 것 같습니다. 아마 평생 고민해도 진전이 없을 것 같네요.

제 전공 분야와 다소 다른 분야의 수학이다보니, 어쩌면 디테일한 지점에서 틀렸을 수도 있습니다. 이산수학 전문가분들 지적해주시면 감사합니다.

수학민수야 고맙다!