|
Эта публикация цитируется в 1 научной статье (всего в 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}$. Цель настоящей работы состоит в доказательстве последней оценки.
Ключевые слова:
системы пар множеств, пересекающиеся системы, разбиения ребер графов.
Статья поступила: 24.04.2021 Окончательный вариант: 24.04.2021 Принята к печати: 11.06.2021
Образец цитирования:
А. В. Косточка, Г. МакКорт, М. Нахви, “О размерах систем пар множеств с $1$-перекрестным пересечением”, Сиб. матем. журн., 62:5 (2021), 1039–1048; Siberian Math. J., 62:5 (2021), 842–849
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj7612 https://www.mathnet.ru/rus/smj/v62/i5/p1039
|
|