RUS  ENG
Полная версия
ЖУРНАЛЫ // Проблемы передачи информации // Архив

Пробл. передачи информ., 2012, том 48, выпуск 4, страницы 56–61 (Mi ppi2095)

Эта публикация цитируется в 3 статьях

Большие системы

Замечание по поводу задачи о неотрицательных суммах по $k$-подмножествам

А. Айдинянa, В. М. Блиновскийab

a Отделение математики, Университет Билефельда, Германия
b Институт проблем передачи информации им. А. А. Харкевича РАН

Аннотация: Для заданного множества, состоящего из $n$ действительных чисел с неотрицательной суммой, рассмотрим семейство всех его $k$-элементных подмножеств с неотрицательными суммами. Насколько малой может быть мощность такого семейства? Показано, что эта задача тесно связана с задачей, поставленной Алсведе и Хачатряном в [1]. Последняя в некотором специальном случае есть не что иное, как задача определения минимального числа $c_n(k)$, такого что любой $k$-однородный гиперграф на $n$ вершинах с $c_n(k)+1$ ребрами имеет совершенное дробное паросочетание. Показано, что результат, полученный в [1], можно применить к первой задаче. Кроме того, выдвинута гипотеза, что эти задачи имеют общее решение.

УДК: 621.391.1+519.1

Поступила в редакцию: 20.06.2012
После переработки: 31.07.2012


 Англоязычная версия: Problems of Information Transmission, 2012, 48:4, 347–351

Реферативные базы данных:


© МИАН, 2024