A graph-theoretic approach to Wilf's conjecture

DOI10.37236/9106MaRDI QIDQ2182002zbMATH OpenOpenAlexWikidataFDO

Authors Shalom Eliahou

Publication date 20 May 2020

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1909.03699

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Frobenius numbernumerical semigroup

Mathematics Subject Classification ID

Graph theory (05C99) Linear Diophantine equations (11D04) Commutative semigroups (20M14)

Abstract: Let S $subseteq$ N be a numerical semigroup with multiplicity m = min(S {0}) and conductor c = max(N 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 longstand-ing 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.

Review text

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\).

Recommendations

• Wilf's conjecture for numerical semigroups
• Wilf's conjecture and Macaulay's theorem
• Numerical semigroups with large embedding dimension satisfy Wilf's conjecture.
• On numerical semigroups with at most 12 left elements
• On a special case of Wilf’s conjecture

Cites work

• A Circle-Of-Lights Algorithm for the "Money-Changing Problem"
• Counting numerical semigroups by genus and some cases of a question of Wilf.
• Exploring the tree of numerical semigroups.
• Fibonacci-like behavior of the number of numerical semigroups of a given genus.
• Gapsets and numerical semigroups
• scientific article; zbMATH DE number 6506585 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• Near-misses in Wilf's conjecture
• Numerical semigroups with large embedding dimension satisfy Wilf's conjecture.
• Numerical semigroups.
• On a conjecture by Wilf about the Frobenius number
• On a question of Eliahou and a conjecture of Wilf
• On numerical semigroups
• The proportion of Weierstrass semigroups
• Wilf's conjecture and Macaulay's theorem
• Wilf's conjecture in fixed multiplicity

Cited in

(20)

• Wilf's conjecture and Macaulay's theorem
• The tree of good semigroups in \(\mathbb{N}^2\) and a generalization of the Wilf conjecture
• Gapsets and numerical semigroups
• A new face iterator for polyhedra and for more general finite locally branched lattices
• A generalization of Wilf's conjecture for generalized numerical semigroups
• Fine-Wilf graphs and the generalized Fine-Wilf theorem
• Wilf's conjecture in fixed multiplicity
• Wilf's conjecture for numerical semigroups
• On numerical semigroups with at most 12 left elements
• On some numerical semigroup transforms
• Wilf's conjecture for numerical semigroups with large second generator
• Semigroups with fixed multiplicity and embedding dimension
• Bounds for invariants of numerical semigroups and Wilf's conjecture
• Families of numerical semigroups and a special case of the Huneke-Wiegand conjecture
• The expected embedding dimension, type and weight of a numerical semigroup
• A verification of Wilf's conjecture up to genus 100
• On a family of numerical semigroups
• Divsets, numerical semigroups and Wilf’s conjecture
• Numerical monoids with concentration two
• A finiteness theorem for W-graphs

Describes a project that uses

Uses Software

• nsgtree
• numericalsgps
• NumericMonoid

This page was built for publication: A graph-theoretic approach to Wilf's conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182002)