第1回生エビ寿司店大会：グラフグループ 📂生エビ寿司誌

第1回生エビ寿司店大会：グラフグループ

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}に掲載する権利を得、編集者が内容の整理を手伝ってくれる。また、2022年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$ の結合法則を示す際に単に数式展開で正面突破したことを高く評価したい。数学には必ずしも数式が必要なわけではなく、数式が多いほど優れたわけではないが、多くの場合、数学者は曖昧さを含む自然言語よりも正確な数式を好み、私もそうである。

特記事項としては、6人の中で唯一英語で提出されたことだ。
- 私の学部時代を思い出させるエピソードがある。学部4年生の科目としてグラフ理論が開講されたが、知っている通り、グラフ理論という科目自体が数式で書き下すよりも言葉が多く、英訳するのが難しく感じる。だから中間試験を受けてみると、ある学生たちが数学的には理解している内容を英語で書くのに困難を覚え、「韓国語での解答提出を許可してほしい」と教授に提案した。そしてその教授の返答は「そもそも英語で書けとは言っていない」だった（笑）。皆ある程度経験のある学生たちなので、英語で書いて当然と考えていたのだ。
- だからといって期末試験で韓国語で書いた学生が増えたかどうかはわからない。意外と韓国語で書いても、めちゃくちゃ簡単になるわけではない。通常、英語で学んだものは英語で書くのが楽だ。英語で学んだものを韓国語で書くというのは意外と難しい。
このエピソードとは関係なく、研究課題を発表する際に英語で書いても問題はなく、むしろ分野によっては英語を推奨することもある。しかし、新鮮エビ寿司店を訪れるすべての方々が数学を専攻しているわけではないため、簡単な韓国語の要約/抄録があると、アクセスしやすくなるだろう。

研究結果

合計2人が提出した。どちらも新しいグラフの積 $\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さんである。

全体的にボリュームが大きく、成果物を読む上で必要な定義や補遺が充実しており、読みやすかった。
一つながらも参考文献があり、レポートと論文の中間にある高品質な成果物だと思う。

2022年04月01日の基準為替レートで10ドルの賞金を支払う。現在の軍人身分だと聞いているので、メールで口座番号を送ってもらえれば確認次第入金する。

後記

全般的な難易度から提出方式まで…運営の未熟さが多く、問題もおかしかった気がする。次からは学部低学年/中高生も参加できるように、より簡単で軽いテーマを準備する。具体的な反省点は次のとおり:

まずグラフの積 $\otimes$ が多様化しにくかった気がする。そもそも論理積という意味において $\oplus$ を用いた意図があったが、振り返ってみればテーマ自体が創意工夫を多く試行するのに適していなかった。
運営側でも研究発表をする必要があるようだ。大まかにはどのような成果物を希望しているかというガイドラインがあまりにもなかったので、研究を始めるのに躊躇した人が多かったのではないかと思う。