% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
% Please remove all other commands that change parameters such as
% margins or pagesizes.
% only use standard LaTeX packages
% only include packages that you actually need
% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}
\usepackage{pkgfile}
\usepackage{algorithm2e}
\newcommand{\bbV}{{\mathcal V}}
\newcommand{\bbE}{{\sE}}
% we recommend the graphicx package for importing figures
\usepackage{graphicx}
% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins
% declare theorem-like environments
\theoremstyle{plain}
%\newtheorem{theorem}{Theorem}
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{corollary}[theorem]{Corollary}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{fact}[theorem]{Fact}
\newtheorem{obs}[thm]{Observation}
%\newtheorem{claim}[theorem]{Claim}
%
%\theoremstyle{definition}
\newtheorem{definition}[thm]{Definition}
%\newtheorem{example}[theorem]{Example}
%\newtheorem{conjecture}[theorem]{Conjecture}
%\newtheorem{open}[theorem]{Open Problem}
%\newtheorem{problem}[theorem]{Problem}
%\newtheorem{question}[theorem]{Question}
%
%\theoremstyle{remark}
%\newtheorem{remark}[theorem]{Remark}
%\newtheorem{note}[theorem]{Note}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% if needed include a line break (\\) at an appropriate place in the title
\title{\bf Minimum-Weight Edge Discriminator in Hypergraphs}
% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address
\author{Bhaswar B. Bhattacharya\\
\small Department of Statistics\\[-0.8ex]
\small Stanford University, California, U.S.A.\\
\small\tt bhaswar@stanford.edu\\
\and
Sayantan Das\\
\small Department of Biostatistics\\[-0.8ex]
%\small School of Public Health,\\[-0.8ex]
\small University of Michigan, Ann Arbor, U.S.A.\\
\small\tt sayantan@umich.edu\\
\and
Shirshendu Ganguly\\
\small Department of Mathematics\\[-0.8ex]
\small University of Washington, Seattle, U.S.A.\\
\small\tt sganguly@math.washington.edu
}
% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}
\date{\dateline{July 7, 2013}{}\\
\small Mathematics Subject Classifications: 05C65, 05C78, 05C38, 90C27}
\begin{document}
\maketitle
% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..." or "we show that...". Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.
\begin{abstract}
In this paper we introduce the notion of minimum-weight edge-discriminators in hypergraphs, and study their various properties. For a hypergraph $\mathcal H=(\mathcal V, \sE)$, a function $\lambda: \mathcal V\rightarrow \mathbb Z^{+}\cup\{0\}$ is said to be an {\it edge-discriminator} on $\mathcal H$ if $\sum_{v\in E_i}{\lambda(v)}>0$, for all hyperedges $E_i\in \sE$, 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 \sE$. 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, \sE)$, with $|\sE|=m$, satisfies $\sum_{v\in \mathcal V} \lambda_\mathcal H(v)\leq m(m+1)/2$, and the equality holds if and only if the elements of $\sE$ are mutually disjoint. For $r$-uniform hypergraphs $\mathcal H=(\mathcal V, \sE)$, it follows from earlier 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. Finally, we show that no optimal edge-discriminator on any hypergraph $\mathcal H=(\mathcal V, \sE)$, with $|\sE|=m~(\geq 3)$, satisfies $\sum_{v\in \mathcal V} \lambda_\mathcal H (v)=m(m+1)/2-1$. This shows that all integer values between $m$ and $m(m+1)/2$ cannot be the weight of an optimal edge-discriminator of a hypergraph, and this raises many other interesting combinatorial questions.
% keywords are optional
\bigskip\noindent \textbf{Keywords:} Edge discrimination, Graph labeling, Hypergraphs, Irregular networks.
\end{abstract}
\section{Introduction}
A {\it hypergraph} is a pair $\mathcal H=(\mathcal V, \sE)$ where $\mathcal V$ is a finite set and $\sE$ is a collection of subsets of $\mathcal V$. The elements of $\mathcal V$ are called {\it vertices} and the elements of $\sE$ are called {\it hyperedges}. A vertex labeling of a hypergraph is a function from the vertex set $\mathcal V$ to the set of non-negative integers. In this paper, we introduce the notion of edge-discriminating vertex labelings in hypergraphs. A vertex labeling $\lambda: \mathcal V\rightarrow \mathbb Z^{+}\cup\{0\}$ is said to be an {\it edge-discriminator} on $\mathcal H$ if $\sum_{v\in E_i}{\lambda(v)}>0$, for all hyperedges $E_i\in \sE$, 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 \sE$. For any edge-discriminator $\lambda$ on $\mathcal H$, the value of the sum $\sum_{v\in \mathcal V}\lambda(v)$ will be called the {\it weight} of the edge-discriminator and shall be denoted by $\omega_\lambda(\mathcal V)$. An edge-discriminator $\lambda_\mathcal H$ on $\mathcal H$ is said to be an {\it optimal edge-discriminator} if it has the least weight, that is, if $\omega_{\lambda_\mathcal H}(\mathcal V)=\min_\lambda\omega_\lambda(\mathcal V)$, where the minimum is taken over all edge-discriminators on $\mathcal H$. Henceforth, the weight of an optimal edge-discriminator on $\mathcal H$, that is, $\omega_{\lambda_\mathcal H}(\mathcal V)$, will be denoted by $\omega_0(\mathcal H)$.
%In this paper we prove several properties of hypergraph edge-discriminators and explicitly compute optimal edge-discriminators in some special types of hypergraphs.
\subsection{Related Works}
Graph labeling is an assignment of integers to the vertices or edges, or both, of a graph which satisfy certain conditions. Refer to the survey of Gallian \cite{graphlabelingsurvey} for a comprehensive view into the huge literature in graph labeling. Hypergraph vertex labelings where the sum of the labels of the vertices along the edges are mutually distinct, has been studied in the literature in many different contexts. One of them is the notion of anti-magic labeling of graphs. For a graph $G=(V, E)$ an {\it edge-antimagic vertex labeling} $l:V\rightarrow \mathbb Z^+$ is an injective function such that the quantities $l(x)+l(y)$ are mutually distinct, whenever $(x, y)$ is an edge in $G$. Edge-antimagic vertex labeling was studied by Wood \cite{wood}. Later, Bollob\'as and Pikhurko \cite{bollobaspikhurko} defined the {\it sum magic number} of a graph $G=(V(G), E(G))$, denoted by $\mathcal S(G)$, as the smallest value of the largest vertex label in an edge-antimagic vertex labeling. They proved that $\mathcal S(K_n)=(1+o(1))n^2$ and $\mathcal S(n, m)< (1-c)n^2$ whenever $m \leq c n^2$, where $\mathcal S(n, m)=\max\{\mathcal S(G): |V(G)|=n, |E(G)|=m\}$.
%They also studied the behavior of the sum magic number for random graphs.
Note that, unlike in the case of edge-discriminators, edge anti-magic vertex labeling of a graph is an injective function. Moreover, the sum magic number minimizes the maximum label, and not the the sum of the labels as required in the optimal edge-discriminator.
Another relevant topic is the notion of irregular networks. A {\it network} is a simple graph where each edge is assigned a positive integer weight. The {\it degree} of a vertex in a network is the sum of the weights of its incident edges. A network is {\it irregular} if all the vertices have distinct degrees. The strength of a network is the maximum weight assigned to any edge. The irregularity strength of a graph $G$ is the minimum strength among all irregular networks on $G$, and is denoted by $s(G)$. The notion of irregularity strength was first introduced by Chartrand et al. \cite{chartrand}, where it was shown that for any given graph $G$, $$s(G)\geq \lambda(G) = \max_{i\leq j}\frac{(n_i + n_{i+1} + \ldots + n_{j}) + i - 1}{j},$$
where $n_i$ denotes the number of vertices of degree $i$. If $G$ contains a $K_2$ or multiple isolated vertices, the irregularity strength $s(G)=\infty$. Nierhoff \cite{rhoff} proved a tight bound $s(G)\leq n-1$, for graphs $G$ with $|V(G)|=n~(>3)$ and $s(G) < \infty$. Faudree and Lehel \cite{faudreelehel} proved bounds on the irregularity strength of $d$-regular graphs. Upper bounds on the irregularity strength for general graphs, in terms of the minimum degree, were first given by Frieze et al. \cite{frieze}, and later by Przyby\l o \cite{przybylo,przybylosiam} and Kalkowski et al. \cite{pfender}. However, computing the irregularity strength of a graph exactly is difficult in general. It is known only for some very special graphs and in almost all of these cases, it is found to be within an additive constant of $\lambda(G)$. It was conjectured by Lehel \cite{lehel}, that $s(G)$ is within an additive constant of $\lambda(G)$ for connected graphs. This has been verified for some special families of graphs like, complete graphs \cite{chartrand}, cycles, most complete bipartite graphs, Turan graphs \cite{irregular}, wheels, hypercubes, and grids \cite{ebert}. The notion of irregularity strength was extended to hypergraphs by Gy\'arf\'as et al. \cite{jcmcc}.
%The dual problem was studied for 1-designs by Blokhuis and Sz\H onyi \cite{blokhuis}.
Edge-discriminators on hypergraphs and irregular networks are dual concepts. For a hypergraph $\mathcal H=(\mathcal V, \sE)$, the {\it dual hypergraph} is defined as $\mathcal D(\mathcal H)=(\mathcal W, \mathcal F)$, where $\mathcal W=\sE$ and $\mathcal F=\{\sE(v)|v\in \mathcal V\}$, where $\sE(v)$ is the set of all edges in $\sE$ which are incident on $v\in \mathcal V$. Note that if $\kappa: \sE\rightarrow \mathbb Z^+$ is an irregular edge assignment for $\mathcal H$, then $\kappa$ transforms to an edge-discriminator $\lambda: \mathcal W\rightarrow \mathbb Z^+$ on $\mathcal D(\mathcal H)$ as follows: For every vertex $v\in \mathcal W$, let $e_v\in \sE$ be the corresponding hyperedge in $\mathcal H$ and define $\lambda(v)=\kappa(e_v)$. However, the most important difference between irregularity strength of a hypergraph and the optimal edge-discriminator in the dual hypergraph is the optimization criterion. In the case of irregularity strength the maximum label is minimized, whereas we minimize the sum of the labels in the optimal edge-discriminator. Another difference is that in an irregular network, the value assigned to an edge is always positive, which means that the edge-discriminator in the corresponding hypergraph assigns a positive weight to every vertex, which is not required by an edge-discriminator.
Another related problem involves the power set hypergraph. The {\it power set hypergraph} on a set $\mathcal V$, with $|\mathcal V|=n$, is the hypergraph $(\mathcal V, 2^\mathcal V)$, where $2^\mathcal V$ denotes the set of all non-empty subsets of $\mathcal V$. Note that any edge-discriminator on the power set hypergraph is a set of positive integers such that all its non-empty subsets have distinct sums. A set of positive numbers satisfying this property is called {\it sum-distinct}. A sum-distinct set of $m$ elements with the minimum total sum is the optimal edge-discriminator on the power set hypergraph, which can be easily computed to be $2^{|\mathcal V|}-1$. In 1931 Erd\H{o}s asked for estimates of smallest possible value of the largest element in a sum-distinct set of $n$ elements, which we denote by $w(n)$. Erd\H{o}s offered \$500 for verifying whether $w(n)=\Omega(2^n)$, and Guy \cite{guy} made the stronger conjecture that $w(n) > 2^{n-3}$. In 1955 Erd\H{o}s and Moser proved that $w(n) \geq 2^n/(4\sqrt n)$ \cite{erdos_sum_distinct}. The constant was later improved by Elkies \cite{elkies}, which was further improved by Aliev \cite{aliev}. A set consisting of the first $n$ powers of 2 has distinct subset sums, and has maximal element $2^{n-1} $, which implies that $w(n) \leq 2^{n-1} $. Conway and Guy \cite{conwayguy} found a construction which gave an interesting upper bound on $w(n)$. This was later improved by Lunnon \cite{lunnon} and then by Bohman \cite{bohman}, who showed that $w(n) < 0.22002 \cdot 2^n$ for sufficiently large $n$.
\subsection{Our Results}
In this paper we study edge-discriminators on hypergraphs such that the sum of the labels of the vertices is minimized. We begin by proving a general upper bound on the weight of an edge-discriminator, which holds for any hypergraph. The bound is relatively simple to obtain, but it is tight.
\begin{thm}
For any hypergraph $\mathcal H=(\mathcal V, \sE)$, with $|\sE|=m$, $\omega_0(\mathcal H)\leq m(m+1)/2$, and the equality holds if and only if the elements of $\sE$ are mutually disjoint.
\label{thm:hypergraphmain}
\end{thm}
Next, we show that the edge-discrimination problem for $r$-uniform hypergraphs is related to Sidon sequences from additive number theory. A {\it Sidon sequence} is a sequence of natural numbers $A = \{a_1, a_2, \ldots \}$ such that all the pairwise sums $a_i + a_j$ $(i \leq j)$ are different \cite{erdosturansidon}. The $B_h$-{\it sets} are generalizations of Sidon-sequences in which all $h$-element sums are mutually distinct \cite{sidonsurvey}. Using the connection between edge-discriminators and $B_h$ sets, we obtain another bound on the weight of the optimal edge-discriminator for $r$-uniform hypergraphs in terms of the number of vertices.
\begin{ppn}For any $r$-uniform hypergraph $\mathcal H=(\bbV, \bbE)$, with $|\mathcal V|=n$, $\omega_0(\mathcal H)\leq n^{r+1}+o(n^{r+1})$, and the bound is attained up to a constant factor by the optimal edge-discriminator of the complete $r$-uniform hypergraph on $\mathcal V$.
\label{thm:r+1}
\end{ppn}
Obtaining nontrivial lower bounds on the weight of the optimal edge-discriminator for general hypergraphs seems to be difficult. It is easy to show that $\sum_{v\in \mathcal V} \lambda_\mathcal H (v)\geq \max\{m, \delta(\delta+1)/2\}$, where $|\sE|=m$ and $\delta$ is the size of the maximum matching in $\mathcal H$. Moreover, there is a hypergraph, which attains this lower bound. However, like the irregularity strength, finding the optimal edge-discriminator is generally difficult for most hypergraphs. For examples where the optimal edge-discriminators can be explicitly computed refer to Bhattacharya et al. \cite{bbbsdsg}.
In Theorem \ref{thm:hypergraphmain} we show that the weight of an optimal edge-discriminator for a hypergraph with $m$ hyperedges is at most $m(m+1)/2$. Moreover, the weight of any edge-discriminator is at least $m$. This motivates us to ask the following question: Given any integer $w\in [m, m(m+1)/2]$, whether there exists a hypergraph $\mathcal H$ with $m$ hyperedges such that $w$ is the weight of the optimal edge-discriminator on $\mathcal H$. We provide a negative answer, by proving the following theorem:
\begin{thm}There exists no hypergraph $\mathcal H=(\mathcal V, \sE)$ with $|\sE|=m~(\geq 3)$, such that the weight of the optimal edge-discriminator on $\mathcal H$ is $m(m+1)/2-1$.
\label{thm:no_function}
\end{thm}
The above result indicates that the problem of attainability of weights is an interesting combinatorial problem which might have surprising consequences. We discuss the attainability problem in more detail later on.
The rest of the paper is organized as follows: The proof of Theoerem \ref{thm:hypergraphmain} where we give a general upper bound on the weight of an optimal edge-discriminator is given in Section \ref{sec:upperbound}. In Section \ref{sec:sidon} we outline the connection between Sidon sequences and edge-discriminators in uniform hypergraphs. A short discussion on lower bounds is given in Section \ref{sec:lowerbound}. The problem of non-attainable weights and the proof of Theorem \ref{thm:no_function} are in Section \ref{sec:nonattainable}. In Section \ref{sec:application} we discuss edge-discriminators in geometric hypergraphs and its potential application to digital image indexing. Finally, in Section \ref{sec:conclusions} we summarize our work and give directions for future research.
\section{Constructing Edge-Discriminators in General Hypergraphs}
\label{sec:upperbound}
In this section, we give an algorithm for constructing an edge-discriminator for a general hypergraph. We begin by introducing some definitions and notations. For any set $S$, denote by $|S|$ the cardinality of $S$. Consider a hypergraph $\mathcal H=(\mathcal V, \sE)$, with $|\mathcal V|=n$ and $\sE=\{ E_1, E_2, \ldots, E_m\}$, where $|\bbE|=m$ and $E_i \subseteq \mathcal V$ for $i\in [m]:=\{1, 2, \ldots, m\}$. An {\it ordering} on $\mathcal V$ is a bijective function $\nu: [n] \rightarrow \bbV$. We shall write $\nu_i:=\nu(i)$, for $i \in [n]$. Thus, with respect to the ordering $\nu$, the vertices in $\bbV$ will be indexed as $\{\nu_1, \nu_2, \ldots, \nu_n\}$. For two vertices $\nu_i, \nu_j \in \mathcal V$, we say $\nu_i$ {\it is less than} $\nu_j$ with respect to $\nu$, if $i < j$. The {\it maximal vertex} of $\mathcal W\subset \mathcal V$ is the vertex $\nu_k\in \mathcal W$ such that for all vertices $\nu_i \in \mathcal W\backslash\{\nu_k\}$, we have $i0$ for all $E_i\in \sE$, as $\omega_\lambda(\emptyset)=0$. Therefore, at the end of the updating procedure, the function $\lambda$ is an edge-discriminator on $\mathcal H=(\mathcal V, \sE)$.
Next, observe that $|\mathcal A(\nu_k)|$ is at most the number of pairs of edges in $\mathcal F$ which has $\nu_k$ as a differentiating vertex. As $\nu(E_i, \emptyset)=\nu(E_i)$, it immediately follows that
$|\mathcal A(\nu_k)|\leq \chi(\nu_k)+\pi(\nu_k)$, where $\chi(\nu_k)$ denotes the number of pairs of edges in $\bbE$ for which $\nu_k$ is a differentiating vertex, and $\pi(\nu_k)$ is the number of edges in $\bbE$ for which $\nu_k$ is the maximal vertex. This implies that
\begin{eqnarray}
\sum_{v\in \mathcal V}\lambda(v)=\sum_{k=1}^{|\mathcal \bbV|} \lambda(\nu_{k}) &\leq&\sum_{k=1}^{n}\chi(\nu_{k}) + \sum_{k=1}^{n} \pi(\nu_{k})\nonumber \\
&=& \frac{m(m-1)}{2}+m=\frac{m(m+1)}{2},
\label{eqn:mainII}
\end{eqnarray}
which completes the proof of the first part of Theorem \ref{thm:hypergraphmain}.
\subsubsection{General Algorithm for Constructing Edge-Discriminators}
Before completing the proof of Theorem \ref{thm:hypergraphmain}, we slightly generalize our procedure for constructing an edge-discriminator. This will be needed to complete the proof of
Theorem \ref{thm:hypergraphmain}. Moreover, it gives better insight into the structure of the discriminating functions, and ultimately leads to an improved upper bound on the weight of the optimal edge-discriminator.
The general algorithm is very similar to the algorithm in the proof of Theorem \ref{thm:hypergraphmain}, but instead of starting with the zero function, we start with any arbitrary integer-valued function $\kappa$, and execute the same procedure to get an edge-discriminator. Typically, depending on the structure of the hypergraph one can choose the initial function to obtain sharper bounds. More formally, the {\it Construction Algorithm} takes a hypergraph $\mathcal H=(\mathcal V, \sE)$, an ordering $\nu$ on $\mathcal V$, and any function $\kappa: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$, and returns an edge-discriminator $\lambda_{\kappa, \nu}: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{algorithm}[h]
\caption{{\it Construction Algorithm}: Edge-Discriminator Construction Algorithm.}
\hrule
%\SetLine
\KwIn{A hypergraph $\mathcal H=(\mathcal V, \sE)$, an ordering $\nu$ on $\mathcal V$, and any function $\kappa: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$.}
\KwOut{An edge-discriminator $\lambda_{\kappa, \nu}: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$.}
Initialize $\lambda_{\kappa, \nu}(v)=\kappa(v)$, for all $v\in \mathcal V$.\\
%Set $\lambda_{\kappa, \nu}(\nu_{i_1})=1$, and $\lambda_{\kappa, \nu}(v)=0$ for all $v\in \mathcal V\backslash \{\nu_{i_1}\}$\;
%Set $k=1$\;
\While{$1< k\leq n$}{
Denote $\mathcal B(\nu_k)=\{|\omega_{\lambda_{\kappa, \nu}}(\underline{E}_{ij})-\omega_{\lambda_{\kappa, \nu}}(\overline{E}_{ij})|:\nu( E_i, E_j)=\nu_k, E_i, E_j \in \sE\}$, $\mathcal C(\nu_k)=\{\omega_{\lambda_{\kappa, \nu}}(E_{i}):\nu( E_i, \emptyset)=\nu_k, E_i \in \sE\}$, and $\mathcal A(\nu_k)=\mathcal B(\nu_k)\cup\mathcal C(\nu_k)$\;
\eIf{$|\mathcal A(\nu_k)|\ne 0$}{
\If{$\kappa(\nu_k)=0$}
{Define $\lambda_{\kappa, \nu}(\nu_{k})=\inf\{\mathbb Z^+\cup\{0\}\backslash\mathcal A(\nu_k)\}$,
}
\If{$\kappa(\nu_k)> 0$}
{
Define $\lambda_{\kappa, \nu}(\nu_{k})=\kappa(\nu_k)+\inf\{\mathbb Z^+\cup\{0\}\backslash\mathcal B(\nu_k)\}$.
}
}
{Define $\lambda_{\kappa, \nu}(\nu_{k})=\kappa(\nu_{k})$,
}
$k\leftarrow k+1$.
}
Return the function $\lambda_{\kappa, \nu}: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$.
\hrule
\label{algo:aldo_ed_discrimination}
\end{algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Note that the algorithm assigns non-zero values only to the vertices in $\mathcal R_{\nu}$ sequentially. Assigning the values in this way has the following two properties.
%\begin{description}
%\item[] For a given edge $ E_i\in \sE$, once the value of $\lambda$ is assigned at the vertex $\nu( E_i)$, the weight of that edge becomes fixed, and subsequent assignments of values to the vertices of $\mathcal V$ does not affect the weight of the edge $ E_i$.
%\item[] If there are more than one hyperedges sharing the same maximal vertex, the algorithm makes the weights of these edges distinct by properly assigning values of $\lambda$ to the corresponding differentiating vertices.
%\end{description}
\begin{lem}
Given any hypergraph $\mathcal H=(\mathcal V, \sE)$, an ordering $\nu$ on $\mathcal V$, and any function $\kappa: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$, the {\em Construction Algorithm} produces
an edge-discriminator $\lambda_{\kappa, \nu}: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$ on $\mathcal H$ such that $\omega_{\lambda_{\kappa, \nu}}(\mathcal V)\leq \frac{m(m+1)}{2}-\sum_{k=1}^n\pi(\nu_k)\pmb1\{\kappa(\nu_k)>0\}+\sum_{k=1}^n\kappa(\nu_k)$.
\label{lm:algogeneral}
\end{lem}
\begin{proof} The proof that $\lambda_{\kappa, \nu}$ is an edge-discriminator is very similar to the proof of Theorem \ref{thm:hypergraphmain}. For $\kappa(\nu_k)=0$, we compare all pair of hyperedges $E_i, E_j \in \mathcal F$, such that $\nu( E_i, E_j)=\nu_k$. As all the vertices which are greater than $\nu_k$ are common to both or belong to neither of the edges $E_i$ and $E_j$, according to the construction $\omega_\lambda(\underline{E}_{ij})-\omega_\lambda(\overline{E}_{ij})$ cannot change once $\lambda(\nu_k)$ is assigned. Hence, by the choice of $\lambda(\nu_k)$, $\omega_\lambda(E_i)\ne \omega_\lambda(E_j)$, from the $k$-th step onwards and therefore eventually, for any pair of edges such that $\nu( E_i, E_j)=\nu_k$ and $\kappa(\nu_k)=0$.
When $\kappa(\nu_k)>0$, we define $\lambda_{\kappa, \nu}(\nu_{k})=\kappa(\nu_k)+\inf\{\mathbb Z^+\cup\{0\}\backslash\mathcal B(\nu_k)\}$. This choice of $\lambda(\nu_k)$ differentiates any pair of edges $E_x, E_y \in \sE$, with $\nu(E_x, E_y)=\nu_k$. Note that here we ignore the pairs $(E_z, \emptyset)$, where $\nu(E_z, \emptyset)=\nu_k$. However, as $\kappa(\nu_k)>0$, $\omega_{\lambda_{\kappa, \nu}}(E_z)>0$, for any edge $E_z$ such that $\nu(E_z, \emptyset)=\nu_k$. Hence, any pair of edges has distinct weights in this case as well.
Now, from the algorithm we can bound the weight of $\lambda_{\kappa, \nu}$ as follows:
\begin{eqnarray}
\sum_{k=1}^{n} \lambda_{\kappa, \nu}(\nu_{k}) &\leq&\sum_{k=1}^n |\mathcal A(\nu_k)|\pmb 1\{\kappa(\nu_k)=0\}+\sum_{k=1}^n |\mathcal B(\nu_k)|\pmb 1\{\kappa(\nu_k)>0\}
+\sum_{k=1}^n\kappa(\nu_k)\nonumber \\
&\leq&\sum_{k=1}^n |\mathcal B(\nu_k)|+\sum_{k=1}^n |\mathcal C(\nu_k)|\pmb 1\{\kappa(\nu_k)=0\}
+\sum_{k=1}^n\kappa(\nu_k)\nonumber \\
&\leq&\sum_{k=1}^n \chi(\nu_k)+\sum_{k=1}^n \pi(\nu_k)\pmb 1\{\kappa(\nu_k)=0\}
+\sum_{k=1}^n\kappa(\nu_k)\nonumber \\
&=&\frac{m(m-1)}{2}+\sum_{k=1}^n \pi(\nu_k)-\sum_{k=1}^n \pi(\nu_k)\pmb 1\{\kappa(\nu_k)>0\}
+\sum_{k=1}^n\kappa(\nu_k)\nonumber \\
&=&\frac{m(m+1)}{2}-\sum_{k=1}^n \pi(\nu_k)\pmb 1\{\kappa(\nu_k)>0\}+\sum_{k=1}^n\kappa(\nu_k).\nonumber
\label{eqn:mainII}
\end{eqnarray}
\end{proof}
We will use the above lemma in completing the proof of Theorem \ref{thm:hypergraphmain} and also in the proof of Theorem \ref{thm:no_function}.
\subsubsection{Completing the Proof of Theorem \ref{thm:hypergraphmain}}
%Before proving the second part of the result we make a simple observation about the updating procedure. The above procedure gives us an edge discriminator irrespective of the initial $\lambda$ as long as it is non-negative. However by default we start with the zero function.
To complete the proof of Theorem \ref{thm:hypergraphmain} we need to show that given any hypergraph
$\mathcal H=(\mathcal V, \bbE)$, which contains two egdes $ E_x, E_y\in \bbE$ such that $ E_x\cap E_y\ne\emptyset$, it is possible to construct an edge-discriminating function $\lambda$ on $\mathcal V$ such that
$\sum_{v\in \mathcal V}\lambda(v)< m(m+1)/2$.
Let $|\mathcal V|=n$ and $v_o\in E_x\cap E_y$. Consider an ordering $\widetilde{\nu}: [n] \rightarrow \bbV$ such that $\widetilde\nu_n=\widetilde{\nu}(n)=v_o$. Then $v_o$ is the maximal vertex of both the edges $ E_x$ and $ E_y$, that is, $\pi(\widetilde\nu_n)\geq 2$. We start with the function $\kappa=\delta_{v_o}$ which takes the value $1$ at $v_o$ and $0$ everywhere else. Then from Lemma \ref{lm:algogeneral}, we know that there exists an edge-discriminator $\lambda_{\kappa, \widetilde{\nu}}$ such that $\sum_{v\in \mathcal V}\lambda_{\kappa, \widetilde{\nu}}(v)\leq m(m+1)/2-1$, which proves the tightness of the upper bound and completes the proof of Theorem \ref{thm:hypergraphmain}.
\subsubsection{Consequences of Lemma \ref{lm:algogeneral}}
In this section we discuss an immediate corollary of Lemma \ref{lm:algogeneral} which gives a slightly better upper bound on the weight of an edge-discriminator than in Theorem \ref{thm:hypergraphmain}.
To this end, we need the following definition. For a hypergraph $\mathcal H=(\mathcal V, \sE)$, a set $S\subseteq \mathcal V$ is called a hitting set of $\mathcal H$ if, for all edges $E\in \sE$, $S\cap E\ne \emptyset$. A hitting set of the smallest size is called the {\em minimum hitting set} of $\mathcal H$. Hitting sets are also known as {\em vertex covers} or {\em transversals}.
\begin{cor}
For any hypergraph $\mathcal H=(\mathcal V, \sE)$, $\omega_0(\mathcal H)\leq \frac{m(m-1)}{2}+\mathcal N(\mathcal H)$, where $\mathcal N(\mathcal H)$ is the size of the minimum hitting set of $\mathcal H$.\label{corollary:upperimproved}
\end{cor}
\begin{proof}
For a fixed ordering $\nu$, denote by $N(\nu)$ the set of vertices $v\in \mathcal V$ with $\pi(v) >0$. Observe that $\min_\nu |N(\nu)|=\mathcal N(\mathcal H)$.
Now, consider any ordering $\nu$ on $\mathcal V$. Define $\kappa(v)=\pmb1\{\pi(v)>0\}$. Lemma \ref{lm:algogeneral} then implies that there exists an edge-discriminator $\lambda_{\kappa, \nu}$ such that $\sum_{v\in \mathcal V}\lambda_{\kappa, \nu}(v)\leq m(m-1)/2+|N(\nu)|$. The result follows by taking minimum over all orderings on $\mathcal V$.
\end{proof}
\begin{remark} Note that the bound in Corollary \ref{corollary:upperimproved} is slightly better than the general upper bound proved in Theorem \ref{thm:hypergraphmain}. Moreover, it is easy to see that this bound is attained by the optimal edge-discriminator of the star-graph $T_m$ on $m+1$ vertices and $m$ edges. This follows from the fact that the central vertex of $T_m$ is the minimum hitting set for $T_m$, and so $\mathcal N(\mathcal H)=1$.
\label{rm:nuattain}
\end{remark}
\section{Edge Discriminators in $r$-Uniform Hypergraphs}
\label{sec:sidon}
A $r$-uniform hypergraph is a hypergraph $\mathcal H=(\bbV, \bbE)$, where all the hyperedges in $\bbE$ have cardinality $r$. If $\bbE$ consists of the set of all $r$-element subsets of $\bbV$ then the hypergraph $\mathcal H=(\bbV, \bbE)$ is called the {\it complete $r$-uniform hypergraph} on $\bbV$, and is denoted by $\mathcal K^r_n$.
Consider a $r$-uniform hypergraph on $n$-vertices and let $\mathcal V=\{v_1, v_2, \ldots, v_n\}$. We can obtain an edge discriminator $\lambda: \bbV\rightarrow \mathbb Z^{+}\cup \{0\}$ if the sequence $\{\lambda(v_1), \lambda(v_2), \ldots, \lambda(v_n)\}$, has the property that the sum of the elements in each its $r$-element subset is distinct. This property of the sequence $\lambda(v_1), \lambda(v_2), \ldots, \lambda(v_n)$ is closely related to the notion of Sidon sequences from additive number theory.
\subsection{Sidon Sequences and Generalizations}
A {\it Sidon sequence} is a finite or infinite sequence of natural numbers $A = \{a_1, a_2, \ldots \}$ such that all the pairwise sums $a_i + a_j$ $(i \leq j)$ are different. This problem was introduced by Sidon in 1932, during his investigations in Fourier analysis. A celebrated combinatorial problem asks for estimates of the maximum number of elements $s(N)$ from $\{1, 2, \ldots, N\}$ which form a Sidon sequence. This was posed by Erd\H{o}s and Tur\' an \cite{erdosturansidon}, and they proved that $s(N)\leq N^{1/2}+O(N^{1/4})$, which is the best possible upper bound except for the estimate of the error-term. The upper bound was refined by Lindstr\"om \cite{lindstrom} to $s(N)\leq N^{1/2}+N^{1/4}+1$ and further improved by Cilleruello \cite{cilleruellojcta}. A conjecture of Erd\H{o}s, with a \$500 prize, says that $s(N)=N^{1/2}+O(1)$.
Sidon-sequences can be generalized by considering sequences in which all $h$-element sums are mutually distinct. This leads to the following definition:
\begin{definition}
For a positive integer $h \geq 2$, a finite or infinite sequence of positive integers $A=\{a_1, a_2, \ldots\}$ is called a $B_h$-set if for every
positive integer $c$, the equation
$$c = a_1 + a_2 + \ldots + a_h, ~~~ a_1 \leq a_2 \leq \ldots, \leq a_h, ~~~ a_i \in A,$$
has, at most, one solution. Let $F_h(N)$ denote the cardinality of the largest $B_h$ set that can be selected
from the set $\{1, 2, \ldots, N\}$.
\end{definition}
Bose and Chowla \cite{bosechowla} proved that $F_h(N)\geq N^{1/h} + o(N^{1/h})$.
An easy counting argument shows $F_h(N) \leq (hh!N)^{1/h}$. This upper bound has gone through many improvements and refinements. The general upper bound has the form $F_h(N)\leq c(h)N^{1/h}+o(N^{1/h})$, where $c(h)$ is a constant depending on $h$. For specific values of $c(h)$ refer to Cilleruello \cite{cilleruello_upper}, Cilleruello and Jimenez \cite{cilleruellomathematik}, Jia \cite{jiasidon}, and the references therein. Other related results and problems on Sidon sequences and $B_h$-sets can be found in the surveys \cite{sequences_book,sidonsurvey}.
\subsection{Proof of Proposition \ref{thm:r+1}}
In this section we use the notion of $B_h$-sets to obtain new bounds on the weight of an edge-discriminator in $r$-uniform hypergraphs. Consider a $r$-uniform hypergraph $\mathcal H=(\mathcal V, \sE)$, with $\mathcal V=\{v_1, v_2, \ldots, v_n\}$. Note that a function $\lambda: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$ such that $\{\lambda(v_1), \lambda(v_2), \ldots, \lambda(v_n)\}$ is a $B_r$-set, is an edge-discriminator for $\mathcal H$. Let $G_h(n)$ be the minimum of the maximum element taken over all $B_h$-sets of length $m$. In other words, $G_h(n)$ is the inverse function of $F_h(n)$, and a lower bound for $F_h(n)$ corresponds to an upper bound for $G_h(n)$. Now, as $G_r(n)\leq n^{r}+o(n^r)$, we have
$$\omega_\lambda(\mathcal H)=\sum_{i=1}^n\lambda(v_i)\leq n\cdot\max_{1\leq i \leq n}\lambda(v_i)\leq n^{r+1}+o(n^{r+1}).$$
In case of the complete $r$-uniform hypergraph $\mathcal K^r_n=(\mathcal V, \sE)$, $|\bbE|={{n\choose{r}}}$ and every vertex $v\in \mathcal V$ belongs to ${{n-1}\choose{r-1}}$ hyperedges.
This implies that any edge-discriminator $\lambda: \mathcal V\rightarrow \mathbb Z^+\cup\{0\}$ on $\mathcal K_n^r$ satisfies
$$\sum_{E\in \sE}\omega_\lambda(E)=\sum_{E\in \sE}\sum_{v\in E}\lambda(v)={n-1\choose{r-1}}\sum_{v\in \mathcal V}\lambda(v).$$
As $\omega_\lambda(E)$ is distinct for all $E\in \bbE$, $\sum_{E\in \sE}\omega_\lambda(E) \geq |\sE|(|\sE|+1)/2$. Therefore,
$$\omega_\lambda(\mathcal K^r_n)=\sum_{v\in \mathcal V}\lambda(v)=\frac{1}{{n-1\choose{r-1}}}\sum_{E\in \sE}\omega_\lambda(E) \geq \frac{{{n\choose{r}}}\left({{n\choose{r}}}+1\right)}{2{{n-1\choose{r-1}}}}
=\frac{\frac{n}{r}\left({{n\choose{r}}}+1\right)}{2}\geq c n^{r+1},$$
for $n$ large enough and some constant $c$. This proves that the weight of the optimal edge-discriminator of $\mathcal K^r_n$ is within a constant factor of the upper bound, and completes the proof of Proposition \ref{thm:r+1}.
\begin{remark}The upper bound on the weight of an edge-discriminator for a $r$-uniform hypergraph obtained in Proposition \ref{thm:r+1} is often better than the general $|\sE|(|\sE|+1)/2=O(|\sE|^2)$ upper bound proved in Theorem \ref{thm:hypergraphmain}. In particular, when $|\sE|\geq c|\mathcal V|^{\frac{r+1}{2}}$, then Proposition \ref{thm:r+1} provides a better bound on the weight of an edge-discriminator. For example, if the $r$-uniform hypergraph is dense then Proposition \ref{thm:r+1} gives a sharper upper bound. On the other hand, if we have a sparse $r$-uniform hypergraph, then Theorem \ref{thm:hypergraphmain} gives a better bound.
\end{remark}
%In fact, we will prove later that the optimal-edge discriminator on paths and cycles attains the $|\sE|(|\sE+1|)/2$ upper bound up to a constant factor.
\section{Lower Bound}
\label{sec:lowerbound}
In this section we prove a simple lower bound on the weight of an edge discriminator on $\mathcal H$. Given a hypergraph $\mathcal H=(\mathcal V, \sE)$, a subset $\sE'\subseteq \sE$ is said to be a {\it matching} if the elements in $\sE'$ are mutually disjoint. A {\it maximum matching} of $\mathcal H$ is the largest size matching in $\mathcal H$.
\begin{ppn}For any edge-discriminator $\lambda$ on a hypergraph $\mathcal H=(\mathcal V, \sE)$, with $|\sE|=m$, $\omega_\lambda(\mathcal V)\geq \max\{m, \frac{\delta(\delta+1)}{2}\}$, where $\delta$ is the size of the maximum matching of $\mathcal H$. Moreover, there is a hypergraph with $m$ edges which attains this bound.
\label{ppn:lower_bound}
\end{ppn}
\begin{proof}Observe that the weights $\omega_\lambda(E_1), \omega_\lambda( E_2), \ldots, \omega_\lambda( E_m)$ are all positive and distinct. This implies that
\begin{equation}
\omega_\lambda(\mathcal V)\geq \max_{ E_i\in \bbE}{\omega_\lambda( E_i)}\geq m.
\label{eq:lowerbound_I}
\end{equation}
Next, suppose that $ \sE'=\{ E_{i_1}, E_{i_2}, \ldots, E_{i_{\delta}}\}$ is a matching of $\mathcal H$. Since the hyperedges $ E_{i_1}, E_{i_2}, \ldots, E_{i_{\delta}}$ are mutually disjoint and the corresponding weights $\omega_\lambda( E_{i_1}),$ $\omega_\lambda( E_{i_2}), \ldots, \omega_\lambda( E_{i_{\delta}})$ are distinct,
\begin{equation}
\omega_\lambda(\mathcal V)\geq \sum_{j=1}^{\delta}\omega_\lambda( E_{i_j})\geq \frac{\delta(\delta+1)}{2}.
\label{eq:lowerbound_II}
\end{equation}
Finally, consider the hypergraph $\mathcal H_1=(\bbV_1, \bbE_1)$, with $\bbV_1=[n]$ and $\bbE_1=\{E_1, $ $ E_2, \ldots, E_m\}$, where $E_i=[i]$. Then it is easy to see that the function $\lambda_1:\mathcal V_1 \rightarrow \mathbb Z^+\cup \{0\}$ defined by $\lambda_1(i)=1$, for all $i \in [m]$, is the optimal edge-discrimiator for $\mathcal H_1$ and
$\omega_0(\mathcal H_1)=\omega_{\lambda_1}(\mathcal V)=m$ attains the lower bound.
\end{proof}
\begin{remark}
A hypergraph is called $d$-{\it regular} if every vertex is in $d$ hyperedges. Let $\mathcal H=(\mathcal V, \sE)$ be a $d$-regular hypergraph with $|\sE|=m$. Then any edge discriminator $\lambda$ on $\mathcal H$ satisfies $\omega_\lambda(\mathcal V)=\sum_{v\in \mathcal V}\lambda(v)=\frac{1}{d}\sum_{E\in \sE}\omega_\lambda(E)\geq \frac{m(m+1)}{2d}=O(m^2/d)$. If $d=O(1)$, that is, the hypergraph is sparse, this lower bound has the same order of magnitude as the $O(m^2)$ upper bound proved in Theorem \ref{thm:hypergraphmain}.
\end{remark}
\section{Non-Attainable Optimal Weights: Proof of Theorem \ref{thm:no_function}}
\label{sec:nonattainable}
We have shown that an optimal edge-discriminator on a hypergraph with $m$ hyperedges can have weight at most $m(m+1)/2$ and this is attained when the $m$ hyperedges are mutually disjoint. Moreover, there exists a hypergraph for which the weight of the optimal edge-discriminator is $m$, as demonstrated in Proposition \ref{ppn:lower_bound}. This raises the question that whether all weights between $m$ and $m(m+1)/2$ are attainable. More formally, we are interested in knowing that given any integer $w\in [m, m(m+1)/2]$, whether there exists a hypergraph $\mathcal H(m, w)$ on $m$ edges such that $w$ is the weight of the optimal edge-discriminator on $\mathcal H(m, w)$. We say that $w$ is {\it attainable} if there exists a hypergraph $\mathcal H$ on $m$ edges such that the weight of the optimal edge-discriminator on $\mathcal H$ is $w$. An integer $w \in [m, m(m+1)/2]$ is said to be {\it non-attainable} if it is not attainable. In this section we prove Theorem \ref{thm:no_function} which shows that for all $m\geq 3$, the weight $m(m+1)/2-1$ is non-attainable.
\subsection{Proof of Theorem \ref{thm:no_function}}
For $m=3$, the result can be proved easily by considering the different possible distinct hypergraphs on 3 edges.
Now, fix an integer $m \geq 4$. We prove the theorem by contradiction. Assume that there exists a hypergraph $\mathcal H_O=(\bbV, \bbE)$, with $|\mathcal V|=n$ and $|\sE|=m$, such that $\omega_0(\mathcal H_O)=m(m+1)/2-1$. Fix any ordering $\nu$ on $\bbV$. From the proof of Theorem \ref{thm:hypergraphmain} we get an edge discriminator $\lambda'$ for $\mathcal H_O$, such that $\omega_{\lambda'}(\mathcal V)\geq \frac{m(m+1)}{2}-1$.
We now have the following observation:
\begin{obs}
Under the above assumption, for any fixed ordering $\nu$ on $\bbV$, either one of the following statements must be true:
\begin{description}
\item[{\it (i)}] There exists $j\in[n]$ such that $\pi(\nu_{j})=2$ and $\pi(\nu_k)\le1$ for all $k\in [n]\backslash\{j\}$.
\item[{\it (ii)}] $\pi(\nu_k)\le1$ for all $k\in [n]$.
\end{description}
\label{ob:cases}
\end{obs}
\begin{proof} Suppose we have an ordering $\nu$ such that $\pi(\nu_{j})\ge3$ for some $j$. Without loss of generality, we assume that $j=n$ because otherwise we can work with a new ordering $\nu'$ such that $ \nu_{j}=\nu'_{n}$.
Let $\nu_{n}\in E_x\cap E_y\cap E_z$. We start with the function $\kappa(v)=\delta_{\nu_{n}}$ which takes the value $1$ at $\nu_{n}$ and $0$ everywhere else. From Lemma \ref{lm:algogeneral} we
get an edge-discriminator $\lambda_{\kappa, \nu}$ such that $\sum_{k=1}^{n} \lambda_{\kappa, \nu}(\nu_{k})\leq m(m+1)/2-2$, which contradicts the hypothesis that the optimal edge discriminator has weight $m(m+1)/2-1$.
Now suppose there are two numbers $i$ and $j$ such that both $\pi(\nu_{i})$ and $\pi(\nu_{j})$ are equal to $2$. Then applying the same argument as above and starting with the function $\lambda=\delta_{\nu_{i}}+\delta_{\nu_{j}}$ and using Lemma \ref{lm:algogeneral} we get an edge-discriminator $\lambda_{\kappa, \nu}$ such that $\sum_{k=1}^{n} \lambda_{\kappa, \nu}(\nu_{k})\leq m(m+1)/2-2$, which gives us a contradiction.
\end{proof}
Using the above observation we now formulate the following important lemma:
\begin{lem}
No vertex in $\mathcal V$ can be incident on more than $2$ hyperedges in $\sE$.
\label{lm:less3}
\end{lem}
\begin{proof}If possible, suppose that there exists a vertex $v_o\in \mathcal V$ such that $v_o$ is incident on
$\ell~(\geq 3)$ hyperedges in $\sE$. Define the ordering $\nu':[n]\rightarrow \bbV$, where $|\bbV|=n$, such that $\nu'_n:=\nu'(n)=v_o$. Therefore, $v_o$ must be the maximal vertex of all the $\ell$ hyperedges incident on it, that is, $\pi(\nu'_n)=\ell\geq 3$. This contradicts Observation \ref{ob:cases} and the proof of the lemma follows.
\end{proof}
%We now analyze the two different possibilities of Observation \ref{ob:cases} separately. Fix an ordering $\nu$ on the vertices in $\mathcal V$.
Next, suppose that the second possibility in Observation \ref{ob:cases} holds for some ordering $\nu$, that is, $\pi(\nu_k)=1$ for all $k\in [n]$. Clearly, $\mathcal H_O$ cannot be the hypergraph in which all the $m$ are hyperedges disjoint. Therefore, we may assume that at least a pair of hyperedges intersect. Now, similar to the proof of Lemma \ref{lm:less3}, we can define a new order $\nu'$ on the vertices such that $\nu'_n:=\nu'(n)\geq 2$, and the problem reduces to the first possibility of Observation \ref{ob:cases} with respect to the ordering $\nu'$.
Therefore, it suffices to consider the first possibility in Observation \ref{ob:cases}, that is, there exists $j\in[n]$ such that $\pi(\nu_{j})=2$ and $\pi(\nu_k)=1$ for all $k\in [n]$ and $k\ne j$. Let $F$ and $G$ be the two hyperedges having $\nu(i_j)$ as the maximal vertex. We now have the following lemma:
\begin{lem}
For any two hyperedges $A, B\in\bbE\backslash\{F, G\}$, $A\cap B=\emptyset$.
\label{lm:edges_two}
\end{lem}
\begin{proof}
Suppose there exists $v_o\in \mathcal V$ such that $v_o\in A\cap B$. Now, from Lemma \ref{lm:less3}, $v_o \notin F \cup G$. Similarly, as $\nu_{j}\in F \cap G$ we have $\nu_{j}\notin A \cup B$.
Let us consider a new ordering
$\nu'$ on $\bbV$ such that $\nu'_{n-1}:=\nu'(n-1)=\nu_{j}$ and $\nu'_n:=\nu'(n)=v_o$. Therefore, $\nu'(A)=\nu'(B)=v_o$, and so $\pi(\nu'_n)\geq 2$. Moreover, as $v_o\notin F\cup G$ and $\nu_{j}\in F\cap G$, $\nu'(F)=\nu'(G)=\nu_{j}$. This means that $\pi(\nu'_{n-1})\geq 2$. This contradicts Observation \ref{ob:cases} and the result follows.
\end{proof}
The above lemma helps us to deduce a necessary configuration of the hypergraph $\mathcal H_O$. This can be visualized by Figure \ref{fig:structure_diagram} and is summarized in the following lemma, the proof of which is immediate from Lemma \ref{lm:less3} and Lemma \ref{lm:edges_two}.
\begin{lem}The set of hyperedges in $\sE\backslash \{F, G\}$ can be partitioned into two disjoint sets $\mathcal F_A=\{A_1, A_2, \ldots, A_s\}$ and $\mathcal F_B=\{B_1, B_2, \ldots, B_t\}$, with $s+t=m-2$, such that:
\begin{description}
\item[{\it (i)}]$A_i\cap A_j=\emptyset$ and $A_i\cap (F \cup G)=\emptyset$ for distinct indices $i, j\in [s]$,
\item[{\it (ii)}]$B_i\cap B_j=\emptyset$, $B_i\cap (F \cup G)\ne \emptyset$, and $B_i\cap (F \cap G)=\emptyset$ for distinct indices $i, j\in [t]$.
\end{description}
\end{lem}
Using properties of this special configuration, we now construct an edge-discriminator $\lambda_1$ on $\mathcal H_O$, such that, $\omega_{\lambda_1}(\mathcal H_O)< m(m+1)/2-1$.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[h]
\centering
\begin{minipage}[c]{1.0\textwidth}
\centering
\includegraphics[width=5.25in]
{Structure_Diagram.pdf}\\
%{\small (a)}\\
\end{minipage}%
%\hspace{-0.25in}
\caption{Illustration for the proof of Theorem \ref{thm:no_function}.}
\label{fig:structure_diagram}%\vspace{-0.15in}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{description}
\item[{\it Case} 1]$s=m-2$. Then $|\mathcal F_B|=0$ and $F$ and $G$ are the only two
intersecting hyperedges in $\mathcal H_O$. We define $\lambda_1:\mathcal V\rightarrow \mathbb Z^{+}\cup \{0\}$ as follows:
$$\begin{array}{ll}
\lambda_1(\nu(A_i))=i, & \hbox{for}~i\in [s]; \\
\lambda_1(\nu(F\cap G))=m-1; & \\
\lambda_1(\nu(F\Delta G))=1; & \\
\lambda_1(x)=0, & \hbox{otherwise.}
\end{array}$$
It is clear that $\lambda_1$ is an edge-discriminator on $\mathcal H_O$, and
\begin{eqnarray}
\omega_{\lambda_1}(\mathcal H_O)=\sum_{v\in \mathcal V}{\lambda_1(v)}&=&\sum_{i=1}^{m-2}\omega_{\lambda_1}(A_i)+
\omega_{\lambda_1}(F)+\omega_{\lambda_1}(G)-\omega_{\lambda_1}(F\Delta G)\nonumber\\
&=& \frac{m(m-1)}{2}-1<\frac{m(m+1)}{2}-1. \nonumber
\end{eqnarray}
\item[{\it Case} 2]$s3$,
$$\sum_{v\in \mathcal V}{\lambda_1(v)}\leq\frac{m(m-1)}{2}+2<\frac{m(m+1)}{2}-1.$$
\end{description}
This contradicts our assumption that $\omega_0(\mathcal H_O)=m(m+1)/2-1$ and the proof of Theorem \ref{thm:no_function} follows.
\section{Geometric Set Discrimination and Potential Applications}
\label{sec:application}
In this section we show how hypergraph edge-discriminators can be used to differentiate a collection of regions in $\mathbb R^d$. Consider a finite collection of regions $\mathcal R=\{R_1, R_2, \ldots, R_m\}$ in $\mathbb R^d$, where a {\it region} is a subset of $\mathbb R^d$. Given any $m$-tuple $(\epsilon_1, \epsilon_2, \ldots, \epsilon_m)\in \{0, 1\}^m$, define $\mathcal R(\epsilon_1, \epsilon_2, \ldots, \epsilon_m)=\bigcap_{i=1}^m R_i^{\epsilon_i}$, where $R_i^0=R_i$ and $R_i^1=\mathbb R^d\backslash R_i$, for $i\in [m]$. Also for $i \in [m]$, define $E_i=\bigcup_{(\epsilon_1, \epsilon_2, \ldots, \epsilon_m)\in A_i}\mathcal R(\epsilon_1, \epsilon_2, \ldots, \epsilon_m)$, where $A_i=\{(\epsilon_1, \epsilon_2, \ldots, \epsilon_m)\in \{0, 1\}^n: \epsilon_i=0\}$. The {\it geometric hypergraph} generated by $\mathcal R$, to be denoted by $\mathcal H(\mathcal R)$, is the hypergraph $(\bbV_{\mathcal R}, \bbE_\mathcal R)$, where $\bbV_{\mathcal R}=\{\mathcal R(\epsilon_1, \epsilon_2, \ldots, \epsilon_m): (\epsilon_1, \epsilon_2, \ldots, \epsilon_m)\in \{0, 1\}^n\}$ and $\sE_\mathcal R=\{E_1, E_2, \ldots, E_m\}$.
%Let $\mathcal R=\{R_1, R_2, \ldots, R_m\}$ be a finite collection of regions in $\mathbb R^d$, such that for all $(\epsilon_1, \epsilon_2, \ldots, \epsilon_m)\in \{0, 1\}^n$, $\mathcal R(\epsilon_1, \epsilon_2, \ldots, \epsilon_m)$ has non-empty interior.
An edge-discriminator for the geometric hypergraph $\mathcal H(\mathcal R)$ is a finite set $M\subset \mathbb R^d$ such that $|R_i\cap M|> 0$, for $i\in [m]$, and $|R_i\cap M|\ne |R_j\cap M|$, for all $i\ne j \in [m]$. The set $M$ is called the {\it geometric discriminator} for $\mathcal R$. The optimal edge-discriminator on $\mathcal H(\mathcal R)$ is the geometric discriminator of the least cardinality, and will be called the {\it optimal geometric discriminator} of $\mathcal R$. The problem of finding the optimal geometric discriminator for a geometric hypergraph, generated by a finite collection of regions in $\mathbb R^d$, will be called the {\it Geometric Set Discrimination Problem}.
Geometric set discrimination seems to be an interesting computational geometry problem, which includes devising efficient algorithms or proving hardness results, particularly when the regions consist of intervals in $\mathbb R^1$, or rectangles or circles in $\mathbb R^2$. These algorithmic questions are left for future research. However, we shall discuss three simple examples of geometric set discrimination which will provide instructive insights into the properties of edge-discriminators and corroborate some of our earlier results.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[h]
\centering
\begin{minipage}[c]{0.33\textwidth}
\centering
\includegraphics[width=0.75in]
{Disjoint_I.pdf}\\
%{\small (a)}\\
\end{minipage}%
%\hspace{-0.25in}
\begin{minipage}[c]{0.33\textwidth}
\centering
\includegraphics[width=1.95in]
{Containment.pdf}\\
%{\small (b)}\\
\end{minipage}
\begin{minipage}[c]{0.33\textwidth}
\centering
\includegraphics[width=1.45in]
{Disjoint_II.pdf}\\
%{\small (b)}\\
\end{minipage}
%\hspace{-0.25in}
\caption{Examples of geometric set discrimination}
\label{fig1}%\vspace{-0.15in}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{description}
\item[{\it Example} 1] We have shown that the upper bound on the weight of an edge-discriminator proved in Theorem \ref{thm:hypergraphmain} is attained if and only if the hypergraph has $m$ disjoint edges. The geometric hypergraph generated by the set $\mathcal S=\{S_1, S_2, \ldots, S_m\}$ of mutually disjoint axis-aligned squares (Figure \ref{fig1}(a))
is such an example. Let $B_i\subset \mathbb R^2$ be any set of distinct $i$ points in the interior of $S_i$. It is trivial to see that the set $B=\{B_1, B_2, \ldots, B_m\}$ is the optimum geometric discriminator of $\mathcal S$ and $\omega_0(\mathcal H_\mathcal S)=\frac{m(m+1)}{2}$.
\item[{\it Example} 2]Consider the set $\mathcal S=\{S_1, S_2, \ldots, S_m\}$ of axis-aligned squares such that $S_i\subset S_{i+1}$ for all $i\geq 1$. Let $B=\{b_1, b_2, \ldots, b_m\}$, where $b_i \in S_i\backslash \bigcup_{j=1}^{i-1}S_j$ (Figure \ref{fig1}(b)). Clearly, $B$ is the optimum edge-discriminator of the geometric hypergraph $\mathcal H_{\mathcal S}$. Since $|B|=m$, the optimum-weight of the edge-discriminator of $\mathcal H_\mathcal S$ attains the lower bound in Proposition \ref{ppn:lower_bound}.
\item[{\it Example} 3]Consider the set $\mathcal S=\{S_1, S_2, \ldots, S_m\}$ of axis-aligned squares, such that $S_i \cap S_j=\emptyset$ for all $i \ne j \in [m-1]$, and $S_i\cap S_m=\emptyset$ for all $i\in [m-2]$, and $S_{m-1}\cap S_m\ne \emptyset$ (see Figure \ref{fig1}(c)). Let $B_i$ be any set of $i$ points in the interior of $S_i$, for $i\in [m-2]$. Let $B_{m-1}$ be any set of $m-1$ points in the interior of $S_{m-1}\cap S_m$ and $b_m$ is any point in the interior of $S_m\backslash S_{m-1}$. It is easy to see that set $B=\{B_1, B_2, \ldots, B_{m-1}, b_m\}$ is the optimum geometric discriminator of $\mathcal S$, with $\omega_0(\mathcal H_\mathcal S)=m(m-1)/2+1$. Note that in this example the $m$ hyperedges are almost disjoint, but the weight of the optimal edge-discriminator is $\frac{m(m-1)}{2}+1=\frac{m(m+1)}{2}-(m-1)$. In fact, this example leads us to conjecture that all integer values in $\mathcal N:=\left[\frac{m(m-1)}{2}+2, \frac{m(m+1)}{2}-1\right]$ are non-attainable. In Theorem \ref{thm:no_function} we only show that $\frac{m(m+1)}{2}-1$ is non-attainable. %It might be possible to generalize the proof of Theorem \ref{thm:no_function} to prove that weights like $m(m+1)/2-a$ are non-attainable, for small constant values of $a$.
\end{description}
Geometric set discrimination problems may find many potential applications to image indexing in a large database \cite{euler_smc,image_indexing}, where the emphasis is specially given on deciding whether a particular image
exists in the database, rather than on finding the similarity matches of the given image. A novel method for archival image indexing using only the number of connected components, the number of holes, or the Euler number of an image was reported by Biswas et al. \cite{image_indexing}. A {\it connected component} of a digital binary image is a subset of maximal size such that any two of its pixels can be joined by a connected sequence of pixels assuming 8-connectivity, lying entirely in the subset. A {\it hole} in a digital image is a region of the background, which is a connected component in 4-connectivity and is completely enclosed by the object. The {\it Euler number} of an image is defined as the number of connected components minus the number of holes in the image. If $C$ and $H$ denote the number of connected components and the number of holes in a digital image, respectively, then its Euler number $E=C-H$ \cite{euler_smc,gonzalez_woods,pratt}. The ordered pair $(C, H)$ is called the {\it Euler pair} of a digital image. It is apparent that two or more images may have the same value of the Euler pair, and hence this feature alone often cannot uniquely characterize an image in a large database. One way to disambiguate the features is to deploy a mask image \cite{image_indexing} as follows: We assume that each image is given as a $(k_1 \times k_2)$ binary pixel matrix. Let us consider $m$ images $I_1, I_2, \ldots, I_m$, each having the same Euler pair. In order to discriminate them, another binary image $M$, called the {\it mask}, is to be constructed such that the Euler pair of the $m$ images $I_1\odot M, I_2\odot M, \ldots, I_m \odot M$ are mutually distinct, where $\odot$ denotes bitwise Boolean operation, like XOR or AND between the corresponding bits of the two pixel matrices.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{figure*}[h]
\centering
\begin{minipage}[c]{1.0\textwidth}
\centering
\includegraphics[width=4.5in]
{Image_Indexing.pdf}\\
%{\small (a)}\\
\end{minipage}%
\caption{Unique image-indexing by geometric-set discrimination.}
\label{fig:image_indexing}
%\vspace{-0.15in}
\end{figure*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
As it turns out, finding a simple mask of a given set of images is a challenging problem. Biswas et al. \cite{image_indexing} provided an iterative heuristic using a few synthetic pseudo-random masks. We now show that finding a mask for a set of images can be modeled as an instance of the hypergraph edge-discrimination for a collection of geometric regions in $\mathbb R^2$. Consider the images $I_1, I_2, \ldots, I_m$, superimposed on each other in the same frame, as subsets of $\mathbb R^2$. Suppose $M$ is a geometric discriminator for this collection of regions. Then the binary image corresponding to $M$ is a mask for the set of images under the bitwise Boolean AND operation. The process is illustrated with four binary images in the Figure \ref{fig:image_indexing}.\footnote{As binary images are actually subsets of the discrete space $\mathbb Z^2$, the mask $M$ should be a subset of $\mathbb Z^2$. As a result, several technical difficulties may arise while trying to obtain a geometric discriminator for a set of binary images containing holes. These problems need to be handled separately and they are not of interest to this paper. Here we discuss the unique indexing problem as a motivating application for the edge-discrimination problem on hypergraphs.} The mask corresponding to the optimal geometric discriminator is the simplest in the sense that the pixel matrix has the least number of ones.
\section{Conclusions}
\label{sec:conclusions}
In this paper we introduce the notion of hypergraph edge-discrimination and study its properties. We show that given any hypergraph $\mathcal H=(\mathcal V, \sE)$, with $|\mathcal V|=n$ and $|\sE|=m$, $\omega_0(\mathcal H)\leq m(m+1)/2$, and the equality holds if and only if the elements of $\sE$ are mutually disjoint. For $r$-uniform hypergraphs, using properties of $B_h$-sets, we prove that $\omega_0(\mathcal H)\leq n^{r+1}+o(n^{r+1})$, and the bound is attained by the complete $r$-uniform hypergraph up to a constant factor.
We also considered the question of attainability of weights: Given any integer $w\in [m, m(m+1)/2]$, whether there exists a hypergraph $\mathcal H(m, w)$ with $m$ hyperedges such that the weight of the optimal edge-discriminator on $\mathcal H(m, w)$ is $w$. We answer this question in the negative by proving that there exists no hypergraph on $m~(\geq 3)$ hyperedges such that the weight of the optimal edge-discriminator is $m(m+1)/2-1$. The problem of characterizing non-attainable weights remains open and might have interesting consequences.
Also, as mentioned in the previous section, another problem for future research is the algorithmic study of the geometric set-discrimination problem.
\subsection*{Acknowledgements} The authors thank the anonymous referees for valuable comments which improved the presentation of the paper.
\begin{thebibliography}{10}
\small
\bibitem{aliev}
I. Aliev, Siegel's lemma and sum-distinct sets, {\it Discrete and Computational Geometry}, Vol. 39 (1-3), 59--66, 2008.
\bibitem{bbbsdsg}
B. B. Bhattacharya, S. Das, S. Ganguly, Minimum-weight edge discriminator in hypergraphs, \arxiv{1210.4668v2}, 2012.
\bibitem{euler_smc}
A. Bishnu, B. B. Bhattacharya, M. Kundu, C. A. Murthy, T. Acharya,
Euler vector for search and retrieval of gray-tone images, {\it IEEE Transactions on Systems,
Man, and Cybernetics}, Vol. 35, 801--811, 2005.
\bibitem{image_indexing}
A. Biswas, P. Bhowmick, B. B. Bhattacharya, Archival image indexing with connectivity features using randomized masks, {\it Applied Soft Computing}, Vol. 8 (4), 1625--1636, 2008.
%\bibitem{blokhuis}
%A. Blokhuis, T. Sz\H onyi, Irregular weighting of 1-designs, {\it Discrete Mathematics}, Vol. 131 (1-3), 33--343, 1994.
\bibitem{bohman}
T. Bohman, A construction for sets of integers with distinct subset sums, {\it Electronic Journal of Combinatorics}
Vol. 5, \#R3, 1--14, 1998.
\bibitem{bollobaspikhurko}
B. Bollob\'as, O. Pikhurko, Integer sets with prescribed pairwise differences being distinct, {\it European Journal of Combinatorics}, Vol. 26 (5), 607--616, 2005.
\bibitem{bosechowla}
R. C. Bose, S. Chowla, Theorems in the additive theory of numbers, {\it Comment. Math.
Helv.}, Vol. 37, 141--147, 1962/1963.
\bibitem{chartrand}
G. Chartrand, M. S. Jacobsen, J. Lehel, O. R. Oellermann, S. Ruiz, F. Saba, Irregular networks, {\it Congressus Numerantium}, Vol. 64, 187--192, 1988.
\bibitem{cilleruellojcta}
J. Cilleruelo, Sidon sets in $\mathbb N^d$, {\it Journal of Combinatorial Theory, Series A}. Vol. 117 (7), 857--871, 2010.
\bibitem{cilleruello_upper}
J. Cilleruelo, New upper bounds for $B_h$ sequences, {\it Advances in Mathematics}, Vol. 159 (1), 2001.
\bibitem{cilleruellomathematik}
J. Cilleruelo, J. Jimenez, $B_h[g]$ sequences, {\it Mathematik}, Vol. 47 (1-2), 2000.
\bibitem{conwayguy}
J. H. Conway, R. K. Guy, Sets of natural numbers with distinct subset sums, {\it Notices, American Mathematical Society} Vol. 15, 345, 1968.
\bibitem{ebert}
G. Ebert, J. Hammenter, F. Lazebnik, A. Woldar, Irregularity strengths
for certain graphs, {\it Congressus Numerantium}, Vol. 71, 39--52, 1990.
%\bibitem{cilleruello_upperlower}
%J. Cilleruelo, I. Ruzsa, C. Trujillo, Upper and lower bounds for finite $B_h[g]$ sequences, {\it Journal of Number Theory}, Vol. 97 (1), 2002.
%\bibitem{cilleruellogeneralized}
%J. Cilleruelo, I. Ruzsa, C. Vinuesa, Generalized Sidon sets, {\it Advances in Mathematics}, Vol. 225 (5), 2010.
\bibitem{elkies}
N. Elkies, An improved lower bound on the greatest element of a sum-distinct
set of fixed order, {\it Journal of Combinatorial Theory, Series A}, Vol. 41, 89--94, 1986.
\bibitem{erdos_sum_distinct}
P. Erd\H{o}s, Problems and results from additive number theory, {\it Colloq. Th\' eorie
des nombres, Bruxells}, 127--137, 1955.
\bibitem{erdosturansidon}
P. Erd\H{o}s, P. Tur\' an, On a problem of Sidon in additive number theory and on some related problems, {\it Journal of the London Mathematical Society}, Vol. 16, 212--215, 1941. Addendum, Vol. 19, 208, 1944.
\bibitem{irregular}
R. J. Faudree, M. S. Jacobson, J. Lehel, R. H. Schelp, Irregular networks, regular graphs and integer
matrices with distinct row and column sums, {\it Discrete Mathematics}, Vol. 76, 223--240, 1989.
\bibitem{faudreelehel}
R. J. Faudree, J. Lehel, Bound on the irregularity strength of regular graphs, {\it Colloq. Math. Soc. J\'anos Bolyai}, 52, Combinatorics, Eger. North Holland, Amsterdam, 247--256, 1987.
\bibitem{frieze}
A. Frieze, R. Gould., M. Karo\'nski, F. Pfender, On graph irregulaity strength, {\it Journal of Graph Theory}, Vol. 41, 120--137, 2002.
\bibitem{graphlabelingsurvey}
J. A. Gallian, A dynamic survey of graph labeling, {\it Electronic Journal of Combinatorics}, 17, \#DS6, 2010.
\bibitem{gonzalez_woods}
R. C. Gonzalez and R. E. Woods, {\it Digital Image Processing}, Addison-Wesley, California, USA, 1993.
\bibitem{guy}
R. K. Guy, Sets of integers whose subsets have distinct sums, {\it Theory and
Practice of Combinatorics, edited by A. Rosa, G. Sabidussi, and J. Turgeon, Annals of Discrete
Mathematics}, Vol. 12, 141--154, North-Holland, Amsterdam, 1982.
\bibitem{jcmcc}
A. Gy\'arf\'as, M. Jacobson, L. Kinch, J. Lehel, R. Schelp, Irregularity strength of uniform hypergraphs,
{\it J. Comb. Methods Comb. Comput.}, Vol. 11, 161--172, 1992.
\bibitem{sequences_book}
H. Halberstam, K. F. Roth, {\it Sequences}, Springer-Verlag, New York, 1983.
\bibitem{jiasidon}
X. D. Jia, On finite Sidon sequences, {\it Journal of Number Theory}, Vol. 49, 246--249, 1994.
\bibitem{pfender}
M. Kalkowski, M. Karonski, F. Pfender, A new upper bound for the irregularity strength of graphs, {\it SIAM Journal on Discrete Mathematics}, Vol. 25(3), 1319--1321, 2011.
\bibitem{lehel}
J. Lehel, Facts and quests on degree irregular assignments, {\it 6th International
Conference on Graph Theory, Combinatorics, and Applications}, (Kalamazoo,
MI, 1988), Wiley-Interscience Publications, Vol. 2, 765--782, 1991.
%\bibitem{lehelprojectiveplane}
%J. Lehel, T. Sz\H onyi, Irregular weighting of a finite projective plane, {\it Ars Combinatorica}, 29C,
%160--167, 1990.
\bibitem{lindstrom}
B. Lindstr\"om, An inequality for $B_2$-sequences, {\it Journal of Combinatorial Theory}, Vol. 6, 211--212, 1969.
\bibitem{lunnon}
W. F. Lunnon, Integers sets with distinct subset sums, {\it Mathematics of Computation}, Vol. 50, 297--320, 1988.
\bibitem{rhoff}
T. Nierhoff, A tight bound on the irregularity strength of graphs, {\it SIAM Journal on Discrete Mathematics}, Vol. 13, 313--323, 2000.
\bibitem{sidonsurvey}
K. O'Bryant, A complete annotated bibliography of work related to Sidon sequences, {\it Electronic Journal of Combinatorics}, 11, 2004.
\bibitem{pratt}
W. Pratt, {\it Digital Image Processing}, John Wiley and Sons, 1978.
\bibitem{przybylo}
J. Przyby\l o, Irregularity strength of regular graphs, {\it Electronic Journal of Combinatorics}, Vol. 15, (1), \#R82
10, 2008.
\bibitem{przybylosiam}
J. Przyby\l o, Linear bound for on the irregularity strength and the total vertex
irregularity strength of graphs, {\it SIAM Journal on Discrete Mathematics}, Vol. 23 (1), 511--516, 2009.
\bibitem{singer}
J. Singer, A theorem in finite projective geometry and some applications to number theory, {\it Transactions of the
American Mathematical Society}, Vol. 43, 377--385, 1938.
\bibitem{wood}
D. R. Wood, On vertex-magic and edge-magic total injections of graphs, {\it Australasian Journal of Combinatorics}, Vol. 26, 49--63, 2002.
\end{thebibliography}
\end{document}