A Graph-Theoretic Approach to Wilf's Conjecture

Abstract

Let $S \subseteq \mathbb{N}$ be a numerical semigroup with multiplicity $m = \min(S \setminus \{0\})$ and conductor $c=\max(\mathbb{N} \setminus S)+1$. Let $P$ be the set of primitive elements of $S$, and let $L$ be the set of elements of $S$ which are smaller than $c$. A longstanding open question by Wilf in 1978 asks whether the inequality $|P||L| \ge c$ always holds. Among many partial results, Wilf's conjecture has been shown to hold in case $|P| \ge m/2$ by Sammartano in 2012. Using graph theory in an essential way, we extend the verification of Wilf's conjecture to the case $|P| \ge m/3$. This case covers more than $99.999\%$ of numerical semigroups of genus $g \le 45$.