Эта публикация цитируется в
1 статье
О размерах систем пар множеств с $1$-перекрестным пересечением
А. В. Косточкаab,
Г. МакКортa,
М. Нахвиa a University of Illinois at Urbana-Champaign, Urbana IL, USA
b Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
Аннотация:
Пусть
$\{(A_i,B_i)\}_{i=1}^m$ — система пар множеств. Фюреди, Дьярфаш и Кираи назвали ее
системой с $1$-перекрестным пересечением, если
$|A_i\cap B_j|$ равно
$1$ при
$i\neq j$ и
$0$ при
$i=j$. Они исследовали такие системы и их обобщения; в частности, они рассмотрели
$m(a,b,1)$ — наибольший размер системы с
$1$-перекрестным пересечением, для которой
$|A_i|\leq a$ и
$|B_i|\leq b$ для всех
$i$. Фюреди, Дьярфаш и Кираи показали, что
$m(n,n,1)\geq 5^{(n-1)/2}$, и поставили вопрос, имеются ли оценки сверху величины
$m(n,n,1)$, которые намного лучше, чем классическая оценка
${2n\choose n}$ Боллобаша для систем с перекрестным пересечением.
Отвечая на один из их вопросов, Хольцман недавно доказал, что если
$a,b\geq 2$, то
$m(a,b,1)\leq \frac{29}{30}\binom{a+b}{a}$. Он также высказал гипотезу, что множитель
$\frac{29}{30}$ в его оценке можно заменить на
$\frac{5}{6}$. Цель настоящей работы состоит в доказательстве последней оценки.
Ключевые слова:
системы пар множеств, пересекающиеся системы, разбиения ребер графов.
УДК:
519.101
MSC: 35R30 Статья поступила: 24.04.2021
Окончательный вариант: 24.04.2021
Принята к печати: 11.06.2021
DOI:
10.33048/smzh.2021.62.506