ИСТИНА |
Войти в систему Регистрация |
|
ИСТИНА ИНХС РАН |
||
In our talk, we will be mainly concerned with subjects that lie on the edge of combinatorial geometry and coding theory. As for combinatorial geometry, the two problems, which are most important and closely connected to each other, are the Nelson--Hadwiger problem on finding the space chromatic number and the Borsuk problem on partitioning sets in spaces into parts of smaller diameter. It turns out that the strongest existing results for both problems are obtained with the help of systems of (0,1)-vectors with forbidden scalar products and their generalizations onto arbibtrary finite systems of vectors in $ {\mathbb Z}^n $ with similar restrictions. Here we naturally come to some classical as well as completely novel concepts and problems of coding theory. In the lecture, we will first give a survey of results for the Nelson--Hadwiger and Borsuk problems. Then we shall proceed to discussing related coding-theoretic questions concerning (0,1)-vectors and other integer point systems. We will also speak about probabilistic versions of these questions, by defining random subgraphs of some important ``distance graphs'' and treating of their properties. In particular, we will exhibit very recent results on the stability of some classical extremal values in coding theory. Finally, we shall formulate conjectures and open questions.