Graph associated to an element by set of factorizations

Definition

Let \(S\) be a numerical semigroup and \(s \in S\). It is defined the graph associated to \(s\) as the graph whose vertices are the elements of \(\mathbf{Z}(s)\), the set of factorizations of \(s\), and there is an edge between \(a,b \in \mathbf{Z}(s)\) if \(a \cdot b \ne 0\), where the dot product multiplies component by component. The graph associated to an element \(s \in S\) is denoted by \(\nabla_s\). The connected components of \(\nabla_s\) are determined by the R-classes in \(\mathbf{Z}(s)\).

If the graph \(\nabla_s\) is not connected, it is said that \(s\) is a Betti element.

Examples

\(\circ\) Let \(S = \langle 5, 12, 13 \rangle\) and \(s = 60\). To compute the set of factorizations \(\mathbf{Z}(s)\) of \(s \in S\), note that \((\alpha, \beta, \gamma) \in \mathbf{Z}(s)\) implies \(0 \le \alpha \le 12, 0 \le \beta \le 5\) and \(0 \le \gamma \le 4\). From this, it is deduced that

\[ \mathbf{Z}(60) = \{ (12, 0, 0), (0, 5, 0), (7, 1, 1), (2, 2, 2) \}. \]

The graph associated to \(s = 60\) is as follows.

Examples with GAP

The following example is made with the package NumericalSgps in GAP.

\(\diamond\) Let \(S = \langle 14, 17, 21, 30 \rangle\), in GAP:

gap> S := NumericalSemigroup(14, 17, 21, 30);
<Numerical semigroup with 4 generators>

Given a numerical semigroup \(S\) and an element \(n\) of it, the functions Factorizations and FactorizationsElementWRTNumericalSemigroup return the set of factorizations of \(n\) in terms of the minimal generating set of \(S\), therefore, they return the set of vertices of \(\nabla_n\).

gap> z := Factorizations(S, 215);
[ [ 2, 11, 0, 0 ], [ 9, 4, 1, 0 ], [ 6, 4, 3, 0 ], [ 3, 4, 5, 0 ], [ 0, 4, 7, 0 ],
  [ 12, 1, 0, 1 ], [ 2, 8, 1, 1 ], [ 9, 1, 2, 1 ], [ 6, 1, 4, 1 ], [ 3, 1, 6, 1 ],
  [ 0, 1, 8, 1 ], [ 5, 5, 0, 2 ], [ 2, 5, 2, 2 ], [ 5, 2, 1, 3 ], [ 2, 2, 3, 3 ],
  [ 1, 3, 0, 5 ], [ 1, 0, 1, 6 ] ]
gap> Factorizations(S, 215) = Factorizations(215, S);
true
gap> Factorizations(S, 215) = FactorizationsElementWRTNumericalSemigroup(215, S);
true

Given a set of factorizations of an element \(n \in S\), where \(S\) is a numerical semigroup, the function RClassesOfSetOfFactorizations returns a list with the \(\mathcal{R}-\)classes in \(\mathbf{Z}(n)\), therefore, it returns the connected components of \(\nabla_n\).

gap> RClassesOfSetOfFactorizations(z);
[ [ [ 0, 1, 8, 1 ], [ 0, 4, 7, 0 ], [ 1, 0, 1, 6 ], [ 1, 3, 0, 5 ], [ 2, 2, 3, 3 ],
      [ 2, 5, 2, 2 ], [ 2, 8, 1, 1 ], [ 2, 11, 0, 0 ], [ 3, 1, 6, 1 ],
      [ 3, 4, 5, 0 ], [ 5, 2, 1, 3 ], [ 5, 5, 0, 2 ], [ 6, 1, 4, 1 ], [ 6, 4, 3, 0 ],
      [ 9, 1, 2, 1 ], [ 9, 4, 1, 0 ], [ 12, 1, 0, 1 ] ] ]

In this case, \(\nabla_{215}\) is connected.

\(\diamond\) Let \(S = \langle 15, 18, 22, 32 \rangle\), in GAP:

gap> S := NumericalSemigroup(15, 18, 22, 32);
<Numerical semigroup with 4 generators>

Given a set of factorizations \(f\), the function DotEliahouGraph returns the graph (in dot) of factorizations associated to \(f\). Edges are labelled with distances between nodes they join.

gap> 120 in S;
true
gap> f := Factorizations(S, 120);
[ [ 8, 0, 0, 0 ], [ 2, 5, 0, 0 ], [ 0, 3, 3, 0 ], [ 2, 2, 1, 1 ],
  [ 0, 0, 4, 1 ] ]
gap> h := DotEliahouGraph(f);;
gap> Print(h);
graph  NSGraph{
1 [label=" (8, 0, 0, 0)"];
2 [label=" (2, 5, 0, 0)"];
3 [label=" (0, 3, 3, 0)"];
4 [label=" (2, 2, 1, 1)"];
5 [label=" (0, 0, 4, 1)"];
2 -- 4[label="3" ];
3 -- 4[label="3" ];
3 -- 5[label="3" ];
2 -- 3[label="4" ];
4 -- 5[label="4" ];
1 -- 2[label="6" ];
1 -- 4[label="6" ];
}

The obtained graph is as follows.

References

Assi, Abdallah, Marco D’Anna, and Pedro A. Garcı́a-Sánchez. 2020. Numerical Semigroups and Applications. Vol. 3. RSME Springer Series. Springer, [Cham]. https://doi.org/10.1007/978-3-030-54943-5.

Delgado, M., P. A. Garcia-Sanchez, and J. Morais. 2024. “NumericalSgps, a Package for Numerical Semigroups, Version 1.4.0.” https://gap-packages.github.io/ numericalsgps.