### Definitions

We remark that the following definitions given here, are either identical, or basically the same as the corresponding definitions used by Soicher in SOMA update

Definition: Let k≥0 and n≥1 be integers. A SOMA, or more specifically a SOMA(k,n), is an n × n array A, whose entries are k-subsets of a kn-set Ω (the symbol-set), such that every symbol of Ω occurs exactly once in each row and exactly once in each column of A, and every 2-subset of Ω is contained in most one entry of A.

A SOMA(k,n) can also be regarded as set of permutations, as we shall now see.

Let B be a set of permutations of {1,2,...,n}
Definition: We call a subset B a SOMA(k,n) if, and only if,

• for any i,j∈{1,2,...,n} , there exists exactly k elements of B that map i to j, and
• for any distinct a, b ∈ B, there exists at most one i∈{1,2,...,n} such that ia=ib.
Note that B is a kn-set of permutations.

## The structure of SOMAs

Let B be a SOMA(k,n).
Definition: A subset C of B is called a subSOMA ( or more specifically a subSOMA(k',n) ) of B if, and only if, C itself is a SOMA(k',n) for some integer k'.
Defintion: A decomposition of B is a partition {B1,...,Bm} of B, such that each Bi is a subSOMA(ki,n) of B, for some integer ki . We then call the sequence (k1,..,km) a type of B.

It is clear that {B} is one decomposition of the SOMA B, and if this is the only decomposition then we say that B indecomposable; otherwise B is said to be decomposable.

Defintion: An unrefinable decomposition of B is a decomposition {B1,...,Bm} of B, such that each Bi is an indecomposable subSOMA(ki ,n) of B, for some integer ki . We then call the sequence (k1,..,km) a unrefinable decompostion type (ud-type) of B.

## Graphs corresponding to SOMAs

Given a SOMA(k,n) B, we construct the graph Φ(B) with vertex-set the union of B, the cartesian product of {1,2,..,n} × {1,2,..,n}, the set {("row", i) :1≤ i ≤ n} and the set {("column", i) : 1 ≤ i ≤ n}. We define the undirected edges of Φ(B) as follows. An element a ∈ B is only adjacent to the ordered pairs (i, j) such that ia=j. In addition, an ordered pair (i, j) is adjacent to the vertices  ("row", i) and ("column", j). Furthermore, ("row", i) is adjacent to ("row", j) for all i≠j, and ( "column", i) is adjacent to ("column", j) for all i≠j.

We remark that two SOMA(k,n)s A and B are isomorphic if, and only if, the graphs Φ(A) and Φ(B) are isomorphic (as graphs).