A graph-theoretic approach to Wilf's conjecture (Q2182002)

A numerical semigroup \(S\) is a cofinite additive submonoid of \(\mathbb{N}\). A long-standing open problem in additive combinatorics, known as \textit{Wilf's conjecture} [\textit{H. S. Wilf}, Am. Math. Mon. 85, 562--565 (1978; Zbl 0387.10009)], relates three invariants of numerical semigroups. The Frobenius number is \(f(S) = \max( \mathbb{Z} \setminus S)\), the embedding dimension \(\nu(S)\) is the number of minimal generators of \(S\), and the number of ``small elements'' of \(S\) is \(n(S) = \mathrm{Card}(S \cap [0,f(S)])\). Wilf's conjecture states that \[ f(S) < \nu(S) n(S). \] In this paper, the author proves Wilf's conjecture for numerical semigroups whose embedding dimension is large with respect to the multiplicity \(m(S) = \min ( S \setminus \{0\})\), in the sense that \(m(S) \leq 3 \nu(S)\), improving the case \(m(S) \leq 2 \nu(S)\) verified in [\textit{A. Sammartano}, Semigroup Forum 85, No. 3, 439--447 (2012; Zbl 1263.20058)]. Computer evidence suggests that an overwhelming proportion of numerical semigroups satisfy the inequality \(m(S) \leq 3 \nu(S)\). As the title suggests, the main approach used in the paper involves graph theory in an essential way. Specifically, a graph \(G(S)\) is attached to each numerical semigroup \(S\), as follows. The Apéry set of \(S\) is \(Ap(S) = \{ x \in S : x-m(S) \notin S\}\). The graph \(G(S)\) has an edge \(\{x,y\}\) whenever \(0 \ne x,y \in Ap(S)\) and \(x+y \in Ap(S)\) as well. (The graph may have loops, but no repeated edges.) The Apéry set \(Ap(S)\), and hence the graph \(G(S)\), encode crucial information about \(S\), including the invariants \(f(S), \nu(S), n(S)\). By exploring the several possible structures of \(G(S)\) in a case-by-case analysis, the author is able to estimate the invariants of \(S\) and prove the main result whenever \(m(S) \leq 3\nu(S)\) and Wilf's conjecture was not already known to hold for \(S\).