%From vladik@cs.utep.edu Fri Jan 3 13:45:41 1997 %Date: Fri, 3 Jan 97
11:45:34 MST %From: vladik@cs.utep.edu (Vladik Kreinovich) %To:
nevai@math.ohio-state.edu %Subject: Erdos

%Vladik Kreinovich
%Department of Computer Science
%University of Texas at El Paso
%El Paso, TX 79968

\documentstyle{article}
\title{Paul Erd\"os, 1913--1996}
\author{}

\date{}
\begin{document}
\maketitle

\section{Paul Erd\"os}

Paul Erd\"os died on September 20, 1996, at the age of 83. 
Erd\"os was the most prolific of
all mathematicians; he has published more mathematical papers 
than anyone else: more than 1200 papers with more than 300
co-authors. This phenomenon gave rise to the so-called ``Erd\"os number'':
Erd\"os himself had Erd\"os number 0, his co-authors get Erd\"os number
1, co-authors of his co-authors are assigned number 2, etc. 
It is sometimes 
claimed that most mathematicians have Erd\"os number smaller than 10. 

Born in Budapest, Paul Erd\"os spent all his life as a wandering
scholar, constantly in travel. He died in Warsaw, where he 
was attending a minisemester for Combinatorics; after that, 
he was planning to go to Vilnius for the Kubilius Conference. 

Erd\"os's main interest was in combinatorics,
including combinatorics of graphs, number theory, set theory,
geometry, and mathematical analysis. His papers are widely cited and
used. Among many other ideas that Erd\"os has pioneered is
the use of probabilistic methods in combinatorics: in many cases, it is
difficult to explicitly construct an object with a given property,
but it is much easier to prove that the probability of an random
object to have this property is positive. 

Erd\"os impressive productivity and tirelessness in promoting
mathematics made him 
one of the most famous mathematicians in the world: suffice it to say
that his obituary was placed on the front page of the
New Your Times, an honor reserved only for super-celebrities. 

Erd\"os usually formulated his results as pure mathematical theorems,
without emphasizing their possible applications; however, many of his
results founds important applications in various 
areas ranging from voting procedures in social sciences to experiment
design in biology to complexity of computer algorithms. 

In particular, several of his papers are related to (generalized)
interval computations. Two examples:

\section{Erd\"os's Results Related to (Generalized) Interval
Computations: First Example}

Measurements are never absolutely precise; expert estimates also never
lead to precise values. As a result, after each measurement or
estimate, we do not get an exact value of the desired quantity $x$; we get
the {\it set} $X$ of possible values. In the case when we simply
measure this quantity 
and we know the upper bound $\Delta$ on the accuracy of the measuring
instrument, then this set $X$ is an {\it interval} $[\tilde
x-\Delta,\tilde x+\Delta]$, where $\tilde x$ is the measurement
result. In more complicated cases, we may have more complicated sets:
e.g., if we know that $x^2$ belongs to the interval $[1,4]$, then the
set of possible values of $x$ is a union of two intervals 
$[-2,-1]\cup [1,2]$. 

If we knew the exact values of several quantities $x_1,\ldots,x_n$, 
then we would be able to tell which of these values are equal and
which are not, i.e., for each $i$ and $j$, we would know whether $x_i=x_j$
or $x_i\ne x_j$. As a result, in this hypothetic case, we could divide
$n$ quantities into equivalence classes. We can describe
these equivalence classes graphically if we draw $n$ points
corresponding to $n$ quantities, and connect the points that correspond
to equal quantities by edges. Then, we will get a graph that it is a 
union of disconnected complete subgraphs representing equivalence
classes of equal quantities. 

In real life, we do not know the exact values, 
we only know the sets $X_1,\ldots,X_n$ of possible
values. In this case, for each $i$ and $j$, we cannot tell whether the values
of $x_i$ and $x_j$ are equal or not; we can only distinguish between
the cases when it is {\it impossible} for $x_i$ and $x_j$ to be equal
(i.e., when $X_i\cap X_j=\emptyset$), and when it is {\it possible}
for them to be equal (i.e., when $X_i\cap X_j\ne\emptyset$). We can
also describe these conclusions graphically if we take $n$ points and
connect points corresponding to the quantities 
$x_i$ and $x_j$ by an edge iff these quantities $x_i$ and $x_j$ can
have equal values. 

Graphs obtained in this manner for the situations when all sets $X_i$
are intervals are called {\it interval graphs}. Not every graph can be
thus represented by intervals. There is a rich
literature on algorithms for checking whether the given graph is an
interval graph, and for designing simple sequences of intervals
$X_1,\ldots,X_n$ that lead to a given interval graph; 
interval graphs have many
useful applications (see, e.g., \cite{Fishburn85}). 

If we allow sets $X_i$ that are not necessarily intervals, then, as
one can easily see, every finite graph $G=(V,E)$ with set of vertices $V$ and
set of edges $E$ can be represented in this manner:
e.g., we can associate with every vertex $v$ a set $X_v$ consisting of
all the edges that contain $v$; then, $X_v\cap X_w\ne\emptyset$ iff
$v$ and $w$ are connected by an edge. This result is
known since 1945 \cite{Szpilrain45}.

In this proof, we need as many elements in all the sets $X_v$ as there
are edges in the graph; as a result, to represent 
a graph with $n$ vertices, we
need, in the worst case, $n(n+1)/2$ elements. A natural
question is: do we necessarily need that many elements to represent a
given graph? 

In \cite{Erdos66}, Erd\"os has shown that we can use only half of this
number; namely:
\begin{itemize}
\item we can always find a representation with $\lfloor
n^2/4\rfloor$ elements (in $X_1\cup \ldots\cup X_n$), and 
\item for every integer $n>0$, there
exists a graph for which no representation with fewer than $\lfloor
n^2/4\rfloor$ elements is possible.
\end{itemize}

\section{Erd\"os's Results Related to (Generalized) Interval
Computations: Second Example}

Another result of Erd\"os is related to a similar problem: 
\begin{itemize}
\item In the first example, we analyzed the following question: ``if the
measurement result is $\tilde x$, what are the possible actual values
of the measured quantity?''. We assumed that for every $\tilde x$, we
know the set $X$ of possible actual values of the
measured quantity. 

\item Due to
uncertainty, if we measure the same quantity twice, we may get
different results. It is therefore natural to ask a different
question: if we know the result $\tilde x$ of a certain measurement,
what other values can we get if we measure the same quantity once
again? Let us denote this set of values by $P(\tilde x)$. 
\end{itemize}
In this second example, we will assume that we know, for each
possible measurement result $\tilde x$ (i.e., for each real number), this set
$P(\tilde x)$. 
It is natural to assume that this set $P(\tilde x)$ is bounded (otherwise, if
the error can be as large as possible, what good are the
measurements?). 

We want to ask the same question as in the first example: if we
have different measurement results, when can we conclude that these
results come from measuring different actual values? 
If we have two measurement results $\tilde x$ and ${\tilde x}'$, 
and we know that ${\tilde x}'$
was measured after $\tilde x$, then the definition of the set
$P(\tilde x)$ leads to
the following simple answer to this question:
\begin{itemize}
\item if ${\tilde x}'\in P(\tilde x)$, then ${\tilde x}'$ and $\tilde
x$ can be the results of
measuring the same quantity;
\item if ${\tilde x}'\not\in P(\tilde x)$, then $\tilde x$ and
${\tilde x}'$ come from measuring
different quantities.
\end{itemize}
If we do not know in what order the measurements were made, then 
in order to guarantee that $\tilde x$ and ${\tilde x}'$ come from 
measuring different quantities we have to assume that both ${\tilde
x}'\not\in
P(\tilde x)$ and $\tilde x\not\in P({\tilde x}')$. 

If the set $P(\tilde x)$ is simply an interval $[\tilde
x-\Delta,\tilde x+\Delta]$, then,
of course, the conditions $\tilde x\in P({\tilde x}')$ and ${\tilde
x}'\in P(\tilde x)$ mean the same
thing: that $|{\tilde x}'-\tilde x|\le\Delta$. 
However, this is not necessarily always
so: In real life, it is possible that the properties of 
a measuring instrument change with time (e.g., there may be a minor
drift of its characteristics), and therefore, the relation ${\tilde x}'\in
P(\tilde x)$ may be asymmetric.

For this situation, Erd\"os formulated, in \cite{Erdos60,Erdos61}, the
following problem: 
\begin{itemize}
\item If the relation ${\tilde x}'\in P(\tilde x)$ 
is symmetric, and if all sets
$P(\tilde x)$ are bounded, then one can easily prove that for every $n$,
there exist $n$ real numbers (membership results) 
$\tilde x_1,\ldots,\tilde x_n$ that represent $n$
different actual values, i.e., for which $\tilde x_i\not\in
P(\tilde x_j)$ for all $i\ne j$. 

\item However, for asymmetrics relation ${\tilde x}'\in P(\tilde x)$, 
this is not necessarily true. 

\end{itemize}
When is it true?
The answer provided in \cite{Erdos60,Erdos61} is: If the (Lebesgue)
{\it measure} of all sets $P(\tilde x)$ is bounded by a constant $M$, then
for every $n$, it is possible to have $n$ measurement results $\tilde
x_1,\ldots,\tilde x_n$ that imply that
no two actual values are equal. 

\section{There are Probably Many More}

Erd\"os's legacy is huge, and probably there are more examples of
interval-related results; even papers that are not
directly related to verified computing may have influenced (or will
influence) other papers that are of importance to us. 

\begin{thebibliography}{99}

\bibitem{Erdos61}P. Erd\"os, ``Some unsolved problem'', {\it Magyar
Tud. Akad. Mat. Kut. Int. K\"ozl.}, 1961, pp. 221--254; partially
reprinted in \cite{Erdos73}, pp. 15--22.

\bibitem{Erdos73}P. Erd\"os, {\it The art of counting. Selected
writings} (ed. by J. Spencer), MIT Press, Cambridge, MA, 1973. 

\bibitem{Erdos66}P. Erd\"os, A. W. Goodman, and L. P\'osa, ``The
representation of graph by set intersection'', {\it Canad. Math. J.}, 
1966, Vol. 18, pp. 106--112; reprinted in \cite{Erdos73}, pp. 87--93. 

\bibitem{Erdos60}P. Erd\"os and A. Hajnal, ``Some remarks on set
theory. VIII.'' {\it Michigan Math. Journal}, 1960, Vol. 7,
pp. 187--191. 

\bibitem{Fishburn85} P. Fishburn, {\it Interval orders and interval graphs},
Wiley, N.Y., 1985.

\bibitem{Szpilrain45}E. Szpilrain-Marczewski, ``Sur duex propiet\'es
des classes d'ensembles'', {\it Fund. Math.}, 1945, Vol. 33,
pp. 303--307. 

\end{thebibliography}

\noindent Vladik Kreinovich

\end{document}