Реферат: This chapter contains some background material on equitable partitions (perfect colorings) and completely regular codes, including a survey of known results and some original results. Section 1.1 contains the main definitions related to the theory of completely regular codes and important correspondences between defined objects. Section 1.2 describes known properties of equitable partitions. In Section 1.3, we consider some very general ways to construct equitable partitions. In Section 1.4, we consider classes of combinatorial objects (mostly, classes of objects that are optimal in terms of a certain bound on their parameters) that are equivalent to equitable partitions, i.e., can be alternatively defined as a cell of an equitable partition with special parameters. Section 1.5 contains a small survey of results on completely regular codes in distance-regular graphs different from Hamming, Johnson, Grassmann, and Doob graphs. The following results of this section are new, up to our knowledge: Theorem 1.1 (generalization of Delsarte’s definition of completely regular codes to non-distance-regular graphs), Lemma 1.4 (generalized correlation-immunity bound for T-designs), Theorems 1.2 and 1.3 (a new necessary condition on the existence of equitable partitions: a triangle inequality for eigenvectors of the quotient matrix), Lemma 1.7 (a sufficient condition for the strict monotonicity of an intersection array), Theorem 1.4 (strong distance invariance of some combinatorial designs), Theorem 1.6 (generalized Bierbrauer–Friedman bound), the complete list of parameters of completely-regular codes in cubic distance-regular graphs in Section 1.5 (it was known earlier only for some of these graphs). Some other results, e.g., Propositions 1.33 and 1.58, are more-or-less straightforward consequences of the general theory and might be known in the folklore. The content of this chapter is limited by the knowledge and expertize of its authors, and some deep results on completely regular codes related to the theory of association schemes (for example, most of the results of [62]) are not mentioned here.

Библиографическая ссылка: Krotov D.S. , Potapov V.N.
Completely regular codes and equitable partitions
Глава монографии Completely Regular Codes in Distance-Regular Graphs. – Chapman & Hall., 2025. – C.5-87. – ISBN 9781032494449.

Даты:

Опубликована в печати:	6 нояб. 2024 г.
Опубликована online:	15 мар. 2025 г.

Идентификаторы БД: Нет идентификаторов

Цитирование в БД: Пока нет цитирований