Minimum-Weight Edge Discriminator in Hypergraphs

In this paper we introduce the concept of minimum-weight edge-discriminators in hypergraphs, and study its various properties. For a hypergraph $\mathcal H=(\mathcal V, \mathcal E)$,afunction$\lambda: \mathcal V\rightarrow \mathbb Z^{+}\cup{0}$issaidtobeanedge-discriminatoron$\mathcal H$if$\sum_{v\in E_i}{\lambda(v)}>0$,forallhyperedges$E_i\in \mathcal E$,and$\sum_{v\in E_i}{\lambda(v)}\ne \sum_{v\in E_j}{\lambda(v)}$, for every two distinct hyperedges $E_i,E_j\in \mathcal{E}$. An {\it optimal edge-discriminator} on $\mathcal{H}$, to be denoted by ${\lambda }_{\mathcal{H}}$, is an edge-discriminator on $\mathcal{H}$ satisfying $\sum_{v\in \mathcal V}\lambda_\mathcal H (v)=\min_\lambda\sum_{v\in \mathcal V}{\lambda(v)}$, where the minimum is taken over all edge-discriminators on $\mathcal{H}$. We prove that any hypergraph $\mathcal{H}=(\mathcal{V},\mathcal{E})$, with $|\mathcal E|=n$,satisfies$\sum_{v\in \mathcal V} \lambda_\mathcal H(v)\leq n(n+1)/2$, and equality holds if and only if the elements of $\mathcal{E}$ are mutually disjoint. For $r$-uniform hypergraphs $\mathcal{H}=(\mathcal{V},\mathcal{E})$, it follows from results on Sidon sequences that $\sum_{v\in \mathcal V}\lambda_{\mathcal H}(v)\leq |\mathcal V|^{r+1}+o(|\mathcal V|^{r+1})$, and the bound is attained up to a constant factor by the complete $r$-uniform hypergraph. Next, we construct optimal edge-discriminators for some special hypergraphs, which include paths, cycles, and complete $r$-partite hypergraphs. Finally, we show that no optimal edge-discriminator on any hypergraph $\mathcal H=(\mathcal V, \mathcal E)$,with$|\mathcal E|=n (\geq 3)$,satisfies$\sum_{v\in \mathcal V} \lambda_\mathcal H (v)=n(n+1)/2-1$, which, in turn, raises many other interesting combinatorial questions.