graph theorygroup-theorynotation
I have come across the following formula in Graph Theory and am trying to decipher what it means.
$f(x\circ y)=f(x)\circ f(y)$
It is fairly simple but I have received a number of conflicting definitions of the "$\circ$" symbol which is making it hard to interpret. In some cases people where using this to represent contraction, some to represent relation, etc.
The source can be found here in Definition $1.3$.
Spiral around, leaving one half-row unoccupied, then approach the origin from infinity on the left:
The idea is that an ordered pair representing an amount of water one can obtain in each bucket represents a node in a graph. The directed edges of the graph represent which states are obtainable in one move from the current state.
Solving for the least number of steps to obtain precisely $k$ liters is then a shortest path problem. You are searching the graph for the shortest path from the original state to a state that has $k$ as one the members of the ordered pair.
Best Answer
You are dealing with mappings between groups as defined in Def. $1.1$ in the linked document. A group is a set $S$ equipped with an inner operation $\circ\colon S\times S\to S, (a,b)\mapsto a\circ b$ satisfying some axioms (the ones given in your document). One may write $(S,\circ)$ denoting which set we are dealing with and in particular which operation is used. Now consider a different set $T$ with an inner operation $\star$ also satisfying the given axioms, making $(T,\star)$ a group aswell.
One can immediately consider usual set-functions $f\colon S\to T$ assigning to each element $s\in S$ and element $t:=f(s)\in T$. What is defined in Def. $1.3$ is a so-called group homomorphism. This is nothing but a set-function between $S$ and $T$ preserving the structure given by the inner operations $\circ$ and $\star$, respectively. This presevation is given by the axiom $f(a\circ b)=f(a)\star f(b)$ $\forall a,b\in S$; it is equal to first computing $a\circ b$ and then applying the set-function $f$ or first applying the set-function $f$ to both elements and the computing $f(a)\star f(b)$. To put it different, it is not important which way we choose to go in the following diagram(s)
In the given case two groups are considered, $G$ and $G'$, where the operation is denoted by $\circ$ in both cases (this is a quite common abuse of notation, as it was already discussed yesterday for example). $f$ is a set-function $f\colon G\to G'$ such that $f(x\circ_G y)=f(x)\circ_{G'} f(y)$ (for emphasis I denoted $\circ$ accordingly, in constrast to the author's choice). Note, however, authors tend to not specify which operation is referred to leading to the axiom $f(x\circ y)=f(x)\circ f(y)$ $\forall x,y\in G$.