Оценки мощности минимального 1-совершенного битрейда в графе Хэмминга

Оценки мощности минимального 1-совершенного битрейда в графе Хэмминга Full article

Journal

Дискретный анализ и исследование операций
ISSN: 1560-7542

Output data

Year: 2014, Volume: 21, Number: 6, Pages: 3-10 Pages count : 8

Tags

граф Хэмминга, полином Кравчука, 1-совершенный битрейд

Authors

Воробьёв К.В. ^1,2 , Кротов Д.С. ^1,2

Affiliations

1	Институт математики им. С. Л. Соболева СО РАН, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2	Новосибирский гос. университет, ул. Пирогова, 2, 630090 Новосибирск, Россия

Улучшены известные нижняя и верхняя оценки на минимальную мощность носителя собственной функции графа Хэмминга $H(n,q)$, где $q>2$. В частности, оценена мощность минимального 1-совершенного битрейда в $H(n,q)$. Показано, что мощность такого битрейда ограничена снизу величиной $2^{n-(n-1)/q}(q-2)^{(n-1)/q}$ в случае $q≥4$ и $3^{n/2}(1-O(1/n))$ в случае $q=3$. Кроме того, предложена конструкция, позволяющая строить битрейды мощности $q^{(q-2)(n-1)/q}2^{(n-1)/q+1}$ при $n≡1$ mod $q$, где $q$ – степень простого числа. Библиогр. 10.

Воробьёв К.В. , Кротов Д.С.
Оценки мощности минимального 1-совершенного битрейда в графе Хэмминга
Дискретный анализ и исследование операций. 2014. Т.21. №6. С.3-10. РИНЦ

Vorob'ev K.V. , Krotov D.S.
Bounds for the size of a minimal 1-perfect bitrade in a Hamming graph
Journal of Applied and Industrial Mathematics. 2015. V.9. N1. P.141-146. DOI: 10.1134/s1990478915010159 Scopus РИНЦ OpenAlex

Submitted:	Oct 23, 2014
Accepted:	Nov 10, 2014

Elibrary:

22547709

DB	Citing
Elibrary	1