RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2021, том 62, номер 5, страницы 1039–1048 (Mi smj7612)

Эта публикация цитируется в 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


 Англоязычная версия: Siberian Mathematical Journal, 2021, 62:5, 842–849

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


© МИАН, 2024