1st Shrimp Sushi Restaurant Competition: Graph group 📂JOF

1st Shrimp Sushi Restaurant Competition: Graph group

In celebration of 2022, Fresh Shrimp Sushi Shop is holding a periodic event where readers can participate. We will release one challenge each quarter. The section for this competition is Pure Mathematics, where we explore the structure of sets of graphs given certain operations. The expected difficulty level is for undergraduate students in their 2nd to 3rd year.

Graph Group

Let’s denote a set of $n$ labeled simple graphs as $\mathbb{G}_{n}$. For instance, when $n = 5$, an element $G \in \mathbb{G}_{n}$ could take the following form:

Here, the binary operation $G , F \in \mathbb{G}_{n}$ can be defined as follows: if an edge $(i,j)$ exists in either $G$ or $F$ but not both, then it exists in $G \oplus F$ as well. If the edge $(i,j)$ exists in both, it does not exist in $G \oplus F$.

Furthermore, for any graph $G$, applying the operation $\oplus$ with a null graph $E \in \mathbb{G}_{n}$ yields $G$.

Also, applying the operation with itself gives the null graph, i.e., $G \oplus G = E$. From this, one might intuitively guess that $\left( \mathbb{G}_{n} , \oplus \right)$ forms a group. The first task is to prove that this is actually a group and moreover, an Abelian group.

Assignment

Problem-Solving Task

Prove that $\left( \mathbb{G}_{n} , \oplus \right)$ is an Abelian group. In other words, prove that $\oplus$ satisfies

the associative law,
the commutative law,
has an identity element, and
has inverse elements.

Research Task

Propose an operation $\otimes$ such that $\left( \mathbb{G}_{n} , \oplus , \otimes \right)$ becomes a ring and prove that it forms a ring. Explore its structure. For example, find other rings that are isomorphic to specific $n$ and prove the theorems that hold in $\mathbb{G}_{n}$.

(22.02.26) Condition relaxed from field to ring.

Details

Evaluation Criteria

The problem-solving task will be evaluated on how concise and clear the solution is. The research task will be evaluated on how many rich properties are revealed. Even if the same fields are devised, the participant who finds more theorems will win.

Duration

Submissions are accepted from January 1, 2022, to March 31, 2022. Submissions after this deadline (based on Korean Standard Time) will not be considered.

Submission

The format for solving and research tasks is not strict. You can scan handwritten solutions or write them in $\TeX$ and send them as a pdf. It’s also fine to write in English if that’s more comfortable.

Problem-Solving Task should be submitted to freshrimpsushi@gmail.com to prevent later participants from copying earlier ones.
Research Task should be published on the personal research board in the community (https://freshrimpsushi.com/community/) to prevent overlapping ideas among participants and to verify the contributions of earlier participants if they are similar.

Rewards

The winner earns the right to be published in Fresh Shrimp Sushi Journal, with editorial assistance to organize the content. A prize of $10, based on the exchange rate as of April 1, 2022, will be awarded.

Results

Middle School Rebellion

It was surprising how Danmyo and Dong Dong, who are middle school students, found Fresh Shrimp Sushi Shop, understood the problem, and submitted solutions. Moreover, they were the fastest to submit.

Danmyo's solution

Dong Dong's solution

General Remarks

The interesting point is the difference in their approaches:

Danmyo viewed operation $\oplus$ as the exclusive OR of each edge.
Dong Dong viewed operation $\oplus$ as the operation of the set of edges.

Of course, whether it’s exclusive OR or a set operation, the associative and commutative laws hold well, so it is equally valid to use these properties to show that it’s an Abelian group. It’s really fascinating that both approaches came up from middle school students not yet familiar with university-level mathematics. And what’s even more interesting…

Spectral vs. Topology

More interestingly, out of the six submissions for the problem-solving task, exactly half used a spectral approach and the other half used a topological approach, including one middle school student in each group and one researcher from each group.

Here are those who approached and expressed the problem spectrally:

Here are those who approached and expressed the problem topologically:

General Remarks

First, let’s look at the solutions of Kim Junyoung and Dorothy Doe.

Kim Junyoung's solution

Dorothy Doe's solution

Kim Junyoung approached the problem using an adjacency matrix, commonly used for labeled graphs. Personally, I assumed that everyone would use adjacency matrices when setting this task.

It was impressive that, beyond solving the problem, there was an attempt at characterizing $\mathbb{G}_{n}$ through observations. This wasn’t officially part of the ‘competition research task’, but it was undoubtedly a new exploration.

Dorothy Doe’s solution is commendable for directly tackling the associative law of $\oplus$ with an algebraic expansion. Although mathematics often demands precision more than verbal ambiguity, it’s usually more understood through exact expressions. I, too, prefer exact expressions over ambiguous natural language.

A notable fact is that she was the only one to submit in English.
- This reminds me of an anecdote from my undergraduate days. A course on graph theory, which generally involves rather verbose explanations rather than purely mathematical expressions, was taught in the 4th-year of undergrad. Some students struggled to write what they understood mathematically in English for the quiz. They requested to be allowed to submit answers in Korean. The professor’s response was, “I never said you had to write it in English” 😂 The students, who were accustomed to writing in English, never considered writing in Korean.
- Whether more students switched to writing in Korean for the final exam remains unknown, as writing in Korean isn’t necessarily much easier. Material read in English is often easier to write about in English. Crafting a text in another language from what you learned is evidently challenging.
Given the above story, writing research tasks in English should pose no problem and may even be recommended depending on the field. However, for better accessibility, a brief Korean summary/abstract could be beneficial given not all visitors to Fresh Shrimp Sushi Shop are necessarily mathematicians.

Research Findings

A total of two participants submitted their research. Both defined the new graph product $\otimes$ using the exclusive OR, which somewhat aligned with the intention implied by introducing $\oplus$ with the notion of graph addition using XOR. In hindsight, this might have been the flaw in this competition, making it virtually a race to submit first due to the inherent limitation of minimal variations possible in defining $\otimes$.

General Remarks

(March 28, 2022) jryoungw’s Research
- Similar to how Kim Junyoung discovered the group isomorphism between $\mathbb{G}_{n}$ and $\mathbb{Z}_{2}^{n(n-1)/2}$, jryoungw identified a ring isomorphism with $\mathbb{Z}_{2}^{n(n-1)/2}$ in Proposition 1.
- Consequently, an exploration into modules and vector spaces was attempted. This natural progression stems from characterizing it as a Boolean ring.
(March 14, 2022) CASTLEDOOR’s Research
- An exploration into the identity element of the ring, naturally the Complete Graph $K_{n}$, was presented.
- Absence of zero divisors rules out the possibility of it being a field.
- Lacking zero divisors also means no exploration into Principal Ideal Domain (PID) is viable; however, yielding to compromise, results were sought within the framework of principal ideal rings (PIR) instead and likewise within Unique Factorization Domain (UFD), complementing results within unique factorization rings (UFR).
- Basicly, CASTLEDOOR mentioned that $\mathbb{G}_{n}$ is a Boolean ring earlier than jryoungw. In Chapter 4 ‘On Direct Sums’, it highlighted another generalization about the direct sum, beyond viewing $\mathbb{G}_{n}$ merely as a vector space.

Winner

The winner of this competition is CASTLEDOOR.

The volume was substantial and the definitions and appendices required for understanding the results were thorough, making it enjoyable to read.
It was almost like a report or a paper with references, striking a balance between the two in terms of quality.

A prize of $10 will be awarded based on the exchange rate as of April 1, 2022. Current military personnel status is taken into account; please send your account number via email, and we will deposit the prize upon verification.

Postscript

Regarding the overall difficulty and submission methods… there seemed to be many operational flaws and the problem itself was somewhat unusual. Next time, we’ll prepare simpler and lighter topics to encourage participation from junior undergraduates and high school students. The specific reflections are as follows:

First, the graph product $\otimes$ seemed unlikely to be varied much. Admittedly, the intention behind using $\oplus$ in the sense of XOR was to guide the competition somewhat, but looking back, the topic itself wasn’t suitable for fostering creativity with diverse attempts.
As an organizing team, we might need to research and present ourselves. Having a rough guideline on what sorts of results we expect might encourage participation and enhance the quality of the research submissions.