Многомерные пороговые матрицы и экстремальные матрицы порядка 2
Ключевые слова:
multidimensional matrix, extremal matrix, threshold matrix, selfdual Boolean functionАннотация
Статья посвящена многомерным (0,1)-матрицам, экстремальным относительно свойства содержать полидиагональ (дробное обобщение диагонали). Любая экстремальная матрица является пороговой, то есть ее носитель состоит в точности из таких элементов, для которых взвешенная сумма инцидентных гиперграней превосходит некоторый порог.
Во-первых, мы докажем, что неэквивалентные пороговые матрицы имеют различные распределения единиц по гиперграням. Далее будет установлено, что экстремальные матрицы порядка 2 совпадают со множеством самодвойственных пороговых булевых функций. С помощью этого факта мы найдем асимптотику числа экстремальных матриц порядка 2 и приведем контрпримеры к некоторым гипотезам об экстремальных матрицах. Наконец, мы опишем экстремальные матрицы порядка 2 с малым разнообразием гиперграней.
