2
$\begingroup$

A hypergraph $H=(V,E)$ is sane if $V$ is finite, $E \neq \emptyset$, and $\emptyset \notin E$, and $e\not\subseteq e'$ whenever $e\neq e' \in E$. Moreover, we call $H$ summable if there is a map $f:V\to \mathbb{Z}_{\geq 0}$ such that for all $e, e' \in E$ we have $$\sum_{v\in e}f(v) = \sum_{w\in e'}f(w) > 0.$$ (The $>0$ requirement is there to exclude $f$ being the constant $0$-map.)

Question. Is every sane hypergraph summable?

$\endgroup$

1 Answer 1

2
$\begingroup$

No, not every sane hypergraph is summable. To see this, let $G$ be a star with five leaves $\ell_1, \dots, \ell_5$ all adjacent to a vertex $u$. Then turn $G$ into a sane hypergraph $H$ by adding the hyperedges $\{\ell_1,\ell_2\}$ and $\{\ell_3, \ell_4, \ell_5\}$. Towards a contradiction, suppose that $f: V(H) \to \mathbb{Z}_{\geq 0}$ is a function which shows that $H$ is summable. Since $\{u,\ell_i\}$ is an edge of $H$ for all $i \in [5]$, we must have $f(\ell_i)=f(\ell_j)$ for all $i,j \in [5]$. But now the hyperedges $\{\ell_1, \ell_2\}$ and $\{\ell_3, \ell_4, \ell_5\}$ have different sums.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .