RUS  ENG
Полная версия
СЕМИНАРЫ

Большой семинар лаборатории комбинаторных и геометрических структур
3 сентября 2020 г. 19:00, Москва, Онлайн! https://zoom.us/j/279059822 пароль: первые шесть цифр числа \pi после запятой


A useful tool in combinatorics: Intersecting set-pair systems

Z. Furedi


https://youtu.be/qjfCumzZIIY

Аннотация: The notion of cross intersecting set pair system (SPS) of size $m$, $\Big(\{A_i\}_{i=1}^m, \{B_i\}_{i=1}^m\Big)$ with $A_i\cap B_i=\emptyset$ and $A_i\cap B_j\ne\emptyset$, was introduced by Bollobás and it became an important tool of extremal combinatorics. His classical result states that $m\le {a+b\choose a}$ if $|A_i|\le a$ and $|B_i|\le b$ for each $i$.
After reviewing classical proofs, applications and generalizations, our central problem is to see how this bound changes with additional conditions.
In particular we consider {$1$-cross intersecting} set pair systems, where $|A_i\cap B_j|=1$ for all $i\ne j$. We show connections to perfect graphs, clique partitions of graphs, and finite geometries. Many problems are proposed.
Most new results is a joint work with A. Gyárfás and Z. Király.


© МИАН, 2024