Seminario Interdipartimentale
di Algoritmica
Monday,
July 2, 2007, 12:00 noon
Few
Distance sets
Zoltan
Furedi, University
of Illinois at Urbana-Champaign and Renyi Institute of
Mathematics,
Hungarian
Academy of Sciences
DI - Department of
Computer Science,
Via Salaria 113
Seminar Room, third floor
Abstract:
One
of the basic combinatorial problems is to describe
the distance relations of subsets.
This is a very general framework and the answers depend
very much on whether the underlying metric space is finite
(like codes, graphs, data bases) or infinite (like
Euclidean spaces, max norm, L_1-norm).
We start with an overview of few-distance problems
with beautiful proofs, e.g., Petty's equidistant set theorem,
Larman-Rogers-Seidel 1977 on 2-distance sets in $E^d$
and then survey the tools (geometric, probabilistic and
algebraic methods) and newest results, too.