제1회 생새우초밥집 대회: Graph group 📂생새우초밥지

제1회 생새우초밥집 대회: Graph group

2022년을 맞아 생새우초밥집은 독자 여러분들이 참가할 수 있는 정기 이벤트를 열게 되었습니다. 한 분기마다 한 개의 과제를 공개합니다. 이번 대회의 섹션은 순수수학으로, 그래프의 집합에 연산을 주고 그 구조에 대해서 탐구하는 것입니다. 예상 난이도는 학부 2~3학년 수준입니다.

그래프 그룹

$n$ 개의 레이블 된 심플 그래프의 집합을 $\mathbb{G}_{n}$ 과 같이 나타내봅시다. 예로써 $n = 5$ 일 때 그 원소 $G \in \mathbb{G}_{n}$ 는 다음과 같은 형태일 수 있습니다.

여기서 $G , F \in \mathbb{G}_{n}$ 의 이항연산 $\oplus$ 을 다음과 같이 $G$, $F$ 중 하나에만 에지 $(i,j)$ 가 존재하면 $G \oplus F$ 에도 존재하고, 둘 다에 $(i,j)$ 가 존재하면 $G \oplus F$ 에는 존재하지 않는 식으로 정의할 수 있습니다.

한편 어떤 그래프 $G$ 든, 널 그래프 $E \in \mathbb{G}_{n}$ 와 연산 $\oplus$ 를 하면 $G$ 가 됩니다.

또한 자기 자신과의 연산을 취하면 널 그래프, 즉, $G \oplus G = E$ 일 것입니다. 여기까지 봤을 때, 직관적으로는 $\left( \mathbb{G}_{n} , \oplus \right)$ 가 그룹이 됨을 짐작할 수 있습니다. 첫번째 과제는 이것이 실제로 군, 더 나아가 가환군이 되는 것을 보이는 것입니다.

과제

풀이 과제

$\left( \mathbb{G}_{n} , \oplus \right)$ 가 아벨리안 그룹임을 보여라. 다시 말해, $\oplus$ 이

결합법칙과
교환법칙을 만족하며
항등원과
역원이 존재함을

증명하라.

연구 과제

$\left( \mathbb{G}_{n} , \oplus , \otimes \right)$ 가 링이 될 수 있는 연산 $\otimes$ 를 제안하고 실제로 링이 됨을 보여라. 그리고 그 구조에 대해 탐구하라. 예를 들어, 특정 $n$ 에 대해서 아이소멀픽한 다른 링이나 $\mathbb{G}_{n}$ 에서 성립하는 정리들을 찾고 그 각각을 증명하라.

(22.02.26) 필드에서 링으로 조건 완화

상세

평가 기준

풀이 과제는 가능한 간결하고 깔끔한지, 연구 과제는 얼마나 풍부한 성질들을 밝히는지로 평가합니다. 같은 필드를 고안하더라도 더 많은 정리를 찾은 분이 우승합니다.

기간

22년 1월 1일부터 22년 3월 31일까지 제출을 받습니다. 한국 표준시를 기준 이후에 제출된 것은 인정하지 않습니다.

제출

풀이과제와 연구과제 모두 양식은 신경쓰지 않습니다. 종이에 손으로 풀어서 스캔해주셔도 되고, $\TeX$ 으로 작성해서 pdf로 보내도 좋습니다. 영어가 편하면 영어로 작성해도 상관 없습니다.

풀이 과제는 freshrimpsushi@gmail.com로 제출합니다. 후발주자가 선행주자의 답을 보고 베끼지 못하게 하기 위함입니다.
연구 과제는 커뮤니티(https://freshrimpsushi.com/community/)의 개인연구 게시판에 공개합니다. 참가자 간의 아이디어가 겹치지 않게 하고, 비슷하다면 선행주자의 기여를 증명하기 위함입니다.

보상

우승자는 생새우초밥지^{journal of Freshrimpsushi}에 게재할 권리를 얻으며, 편집자들이 내용의 정리를 도와드립니다. 22년 4월 1일 기준환율로 $10의 상금을 지급합니다.

결과

중학생의 반란

단묘님과 Dong Dong님은 무려 중학생이신인데 어떻게 생새우초밥집을 찾아서 어떻게 문제를 이해하고 어떻게 풀이를 내셨는지… 참 놀라웠습니다. 심지어 이 두 분이 제일 빨리 제출했습니다.

단묘님의 풀이

Dong Dong님의 풀이

총평

흥미로운 점은 이 두 분의 방식 차이입니다:

연산 $\oplus$ 을 각 에지들의 배타적 논리합으로 보는 단묘님
연산 $\oplus$ 을 에지의 집합의 연산으로 보는 Dong Dong님

물론 배타적 논리합이든 집합의 연산이든 결합법칙과 교환법칙은 잘 성립하므로, 아벨리안 그룹임을 보이기 위해 이들의 성질을 가져오려 하는 것은 똑같이 타당한 접근법입니다. 그런데 아직 대학교 수준의 수학에 익숙하지 않으실 두 분의 답안에서 두 가지 어프로치 모두가 등장한 게 정말 신기한 일입니다. 그리고 더 재미있는 건…

스펙트럴 vs 토폴로지

더 재미있는 건, 풀이과제를 제출하신 6분이 정확히 절반인 두 학파로 나뉘었으며 각 학파에 중학생이 한 명씩 포함되어 있고 연구과제 제출자가 한 명씩 포함되어 있다는 점입니다.

다음은 스펙트럴로 접근하고 표현하신 분들입니다:

다음은 토폴로지로 접근하고 표현하신 분들입니다:

총평

우선 김준영님과 Dorothy Doe님의 풀이부터 살펴봅시다.

김준영님의 풀이

Dorothy Doe님의 풀이

김준영님은 라벨링된 그래프^{labeld Graph}라면 흔히 쓰이는 인접행렬로 문제에 접근했습니다. 개인적으로는 이 과제를 내면서 당연히 모든 분들이 이렇게 인접행렬을 쓸거라고 생각했습니다.

단순히 문제를 푸는 것 외에도 관찰로써 $\mathbb{G}_{n}$ 의 특성화^{characterization}를 시도하신 점이 인상적이었습니다. 사실 이것도 ‘대회에서 요구하는 연구 과제’가 아니었을 뿐이지 엄연히 새로운 탐구였거든요.

Dorothy Doe님의 풀이는 $\oplus$ 의 결합법칙을 보일 때 그냥 수식 전개로 정면돌파한 점을 높게 사고 싶습니다. 수학에 꼭 수식이 필요하거나 수식이 많을수록 뛰어난 건 아닙니다만 대부분의 수학도는 애매모호함을 포함한 자연어보다 정확한 수식을 선호하고, 저 또한 그렇습니다.

특이사항으로는 여섯 분 중 유일하게 영어로 제출하셨습니다.
- 제 학부생 시절 일화 하나가 생각납니다. 학부 4학년 과목으로 그래프 이론이 개설됐는데, 알다시피 그래프 이론이라는 과목 자체가 수식으로 써내려가는 것보단 구구절절 말이 좀 길고 영작하기가 까다롭습니다. 그래서 중간고사를 쳐보니까 어떤 학생들이 수학적으론 아는 내용을 영어로 적는데에 어려움을 겪었다면서 ‘한국어로 답안 제출을 허용해달라’고 건의를 했죠. 그리고 이에 대한 교수님의 답변은 “애초에 영어로 내라고 한 적이 없다"였습니다 ㅋㅋㅋㅋ 다들 어느정도 짬을 먹은 학생들이다보니 영어를 안 쓴다는 생각 자체를 못 한거에요.
- 그래서 기말고사 땐 한국어로 답안을 쓴 학생이 늘었는지 어땠는지는 잘 모르겠습니다. 이게 생각과는 달리 한국어로 쓴다고 엄청나게 쉬워지진 않거든요. 보통 영어로 읽은 건 영어로 쓰는 게 편합니다. 영어로 배워서 한국어로 글을 지어낸다는 게 보기보다 어려워요.
위 썰이랑 상관 없이, 앞으로도 연구 과제를 발표할 때 영어로 쓰는 건 아무 문제 없고 분야에 따라선 오히려 영어를 권장할 수도 있습니다. 다만 생새우초밥집에 방문하는 모든 분들이 수학과는 아니니까 짧게나마 한국어 요약/초록이 있으면 접근성이 더 좋긴 하겠죠.

연구결과

총 두 분이 제출했습니다. 두 분 모두 새로운 그래프의 곱 $\otimes$ 을 배타적 논리곱으로 정의하셨고 사실 이는 그래프의 덧셈을 $\oplus$ 로 나타낸 것부터 어느정도 이렇게 하라는 출제 의도가 있었습니다. 지금와서 생각해보면 그게 이번 대회의 패착인데, 출제자로써 $\otimes$ 에 대한 고민이 부족했던 탓에 사실상 먼저 제출하는 분이 우승할 수밖에 없는 구조를 만들어버린 것 같습니다.

총평

(22년 03월 28일) jryoungw님의 연구 보러가기
- 김준영님이 $\mathbb{G}_{n}$ 과 $\mathbb{Z}_{2}^{n(n-1)/2}$ 의 그룹 아이소멀피즘을 발견했듯 jryoungw님은 Proposition 1에서 $\mathbb{Z}_{2}^{n(n-1)/2}$ 와의 링 아이소멀피즘을 찾으셨습니다.
- 이에 따라 모듈, 벡터공간으로의 탐구를 시도했습니다. 불리언 링으로써 특성화했으니 자연스러운 흐름입니다.
(22년 03월 14일) CASTLEDOOR님의 연구 보러가기
- 링의 곱셈이 나왔으면 당연히 궁금해야할 단위원에 대한 탐구가 있습니다. 직관적으로 쉽게 짐작할 수 있겠지만, 그 단위원은 컴플리트 그래프 $K_{n}$ 입니다.
- 영인자가 없다고 하니까, 당연히 필드는 될 수 없습니다.
- 영인자가 없으니 주 아이디얼 정역(PID)을 연구할 순 없지만, 정역(ID)를 포기하고 주 아이디얼 환(PIR)로 타협해서 정리를 찾은 점이 인상적이었습니다. 마찬가지로 유일 인수분해 정역(UFD)도 UFR로 타협해서 정리를 남겼습니다.
- 기본적으로 $\mathbb{G}_{n}$ 이 불리언 링이라는 점을 jryoungw님보다 앞서서 언급했습니다. 4장 ‘Direct Sum에 대하여’에서는 $\mathbb{G}_{n}$ 을 꼭 벡터공간으로 보지 않더라도 직합에 대해 일반화할 수 있다는 고찰을 남겼습니다.

우승자

이번 대회의 우승자는 CASTLEDOOR님입니다.

전체적으로 볼륨이 크고 결과물을 읽는데 필요한 정의나 부록이 충실해서 읽기 편했습니다.
한 편이지만 레퍼런스도 있어 레포트와 논문 사이 어딘가에 있는 고퀄리티의 결과물이라고 생각합니다.

22년 04월 01일 기준 기준환율로 10달러의 상금을 지급합니다. 현재 군인신분이신 걸로 아는데, 메일로 계좌번호를 보내주시면 확인하는대로 입금하도록 하겠습니다.

후기

전반적인 난이도부터 제출 방식까지… 뭔가 운영상의 미숙함이 크고 문제도 이상했던 것 같습니다. 다음부터는 학부 저학년/중고등학생 분들도 참가할 수 있도록 쉽고 가벼운 주제를 준비해보겠습니다. 구체적인 반성은 다음과 같습니다:

우선 그래프 곱 $\otimes$ 가 별로 다양하기 힘들었던 것 같아요. 애초에 링크의 XOR라는 의미에서 $\oplus$ 를 썼던 의도가 있긴 했는데, 지나고 보니까 주제부터가 창의적으로 여러가지 시도를 하기에 적합하지 않았던 것 같네요.
운영진에서도 연구 발표를 좀 해야할 것 같아요. 대략적으로라도 어떤 결과물들을 원하는지 그런 가이드라인이 너무 없으니까 선뜻 연구를 시작하기 어려웠던 분이 많지 않았을까 하는 아쉬움이 드네요.