Глава 21. Схемы отношений
21.1. ВВЕДЕНИЕ
В этой главе изложены основы теории схем отношений. Схема отношений представляет собой множество, на котором определены отношения, удовлетворяющие определенным свойствам (см. § 21.2). Целый ряд проблем в теории кодирования и в комбинаторике, таких как построение кода наибольшей мощности или построение наибольшего равновесного кода с заданным минимальным расстоянием, может быть естественным образом сформулирован в терминах построения подмножества наибольшей мощности некоторой схемы отношений. Во многих случаях это приводит к границе линейного программирования для подобных задач (если: воспользоваться теоремой 12).
Схемы отношений впервые были введены статистиками в связи с планированием экспериментов (Боуз и Меснер [183], Боуз и Шимамото [186], Джеймс [688], Огасавара [1007], Огава. [1008], Ямамото др. [1444], Рагхаварао [1085]), и они оказались, с тех пор очень полезными и для изучения групп подстановок (см. замечания к этой гл.) и графов (Биггс [144—147] и Деймрелл [327]). Изложенные в этой главе применения этих схем в теории; кодирования были разработаны Дельсартом [352—358, 361 и 364].
В главе принят следующий порядок изложения. В § 21.2 вводятся схемы отношений и формулируются основы теории. Три
наиболее важных с точки зрения теории кодирования примера, а именно схемы Хэмминга, Джонсона и схемы, образуемые симплектическими формами, обсуждаются в § 21.3-21.6. Мы увидим, что 1 код является подмножеством в схеме Хэмминга, а равновесный код является подмножеством в схеме Джонсона. Свойства подмножеств произвольной схемы отношений изучаются в § 21.7. Наконец, в § 21.8 и 21.9 рассматриваются подмножества симплектических форм и t-схемы.
