생새우초밥집

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

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

그래프 그룹

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

graphG.png

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

20211228_171211.png

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

20211229_112032.png

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

과제

풀이 과제

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

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

증명하라.

연구 과제

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

상세

평가 기준

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

기간

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

제출

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

보상

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

정보

댓글