학술
기타
The singleton hypergraph is extremal for the Isolation Lemma
arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.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.
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
관련 뉴스
관련 뉴스 제보는 로그인 후 가능합니다.