The singleton hypergraph is extremal for the Isolation Lemma

Abstract

Let $H$ be an inclusion-free hypergraph on $n$ vertices. A weight assignment $w:[n]\to [d]$ is isolating if there is a unique edge $e$ whose weight $w(e)={\sum }_{i\in e}w(i)$ is minimum. We show that the number of isolating weight assignments is at least $$n\sum _{j=0}^{d-1}{j}^{n-1},$$ a bound which is attained with equality by the hypergraph consisting of the $n$ singleton edges. This proves the conjecture stated in Faber & Harris (2018). We also prove the bound for a more general class of edge-weight objectives, including arbitrary edge offsets.