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.