MMSS 10일차 (8/1 Tue)

• 유향 그래프에 대해서 배웠다. 각 간선에 대해 방향성을 부여할 때 이러한 그래프를 유향 그래프라고 하며, 그 중에서도 유향 cycle이 없도록 무향 그래프의 간선에 방향을 부여해 유향 그래프를 만들 수 있다. 이때의 간선 방향 정보를 Acyclic orientation이라고 한다.
  • 이때, 그래프 채색에 관한 경우의 수를 구하는 chromatic polynomial에 -1을 대입(chromatic polynomial은 그래프의 vertex를 칠하는 데 사용할 색의 개수를 유일한 변수로 사용한다. 따라서 0이나 음수를 대입하는 것은 ‘옳지 못하다’)하면 부호를 무시했을 때 해당 그래프의 서로 다른 acyclic orientation의 개수를 구할 수 있다!
  • Homework의 도전문제로 이 사실을 증명하는 문제가 나왔는데, 아무도 엄밀하게 이 사실을 증명해내지 못한 것 같다. 그래프의 임의의 간선에 대해서 이 간선을 삭제하는 것과 간선을 합병(적절한 한국어 용어가 있지 않은 것 같다. 해당 간선과 연결되어 있는 두 정점을 제거하고, 두 정점 중 하나 이상과 adjacent한 모든 정점과 adjacent한 새로운 정점을 만드는 작업이다.)하는 것 두 가지 경우에 대해서, 두 가지 경우에서의 chromatic polynomial으로 원래 그래프를 표현할 수 있다는 사실을 증명한 뒤 그래프의 order에 대해서 수학적 귀납법을 이용하면 증명할 수 있을 것 같은데, 간선을 제거하는 것과 합병하는 것의 그래프가 어떠한 chromatic polynomial을 가지는 지 잘 설명합지 못해서 문제를 증명할 수 없었다.
• 외에 어제 배웠던 그래프의 5가지 성질변수와 그 사이의 관계에 대해 조금 더 자세히 배우고, 이를 이용해 다양한 문제를 해결하였다.
  • 이번에는 4가지의 풀리지 않은 난제에 대해서도 확인해 보았다. 조건을 볼 때는 말이 안 되는 것 같으면서도 그래프 몇 개에 대해 직접 확인해 보면 실제로 반례를 찾을 수 없는 것이 많아서 4개의 난제 모두 매우 그럴듯해 보였다. 다만 이전에 배웠던 conjecture 중에서도 수십 년 이후 매우 많은 수의 정점/간선을 가진 반례 케이스가 나오는 경우를 많이 확인했어서, 실제로 각 conjecture가 증명되거나 반례가 찾아진다면 직접 한 번 확인해보고 싶다.

chromatic polynomial에 -1을 대입할 때 acyclic orientation의 수가 나온다는 사실이 너무 신기한 것 같다. 직관적으로 생각해보면 유항 그래프의 distinct acyclic orientation의 개수와 그래프의 채색 사이에 분명한 관계가 있는 것도 아니고, chromatic polynomial이라는 사용하는 색의 수를 변수로 사용하는 식에 음수를 대입한다는 것도 매우 반감이 드는 일인데(수업할 때도 교수님이 -1을 대입하는 것을 ‘very nasty thing to do’, ‘… feel like doing something forbidden’ 등으로 표현하셨고 모두가 웃었다)그런 둘 사이에 매우 신기한 관계가 있다는 사실이 매우 신기한 것 같다. 이런 식으로 관계가 거의 혹은 전혀 없는 두 가지 경우의 수적인 성질 사이에 관계가 있는 것이 조합론쪽 분야에는 생각보다 많다고 한다. 순수수학을 전공하는 분들을 저런 것을 찾는 맛에 수학 하시나 싶은 생각도 들었다.