Видеотека
 RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
 Видеотека Архив Популярное видео Поиск RSS Новые поступления

Дни комбинаторики и геометрии II
16 апреля 2020 г. 17:10–17:40, Онлайн-конференция

Induced and non-induced poset saturation problems

B. Patkos

 Количество просмотров: Эта страница: 28 Youtube Video:

Аннотация: A subfamily $\mathcal G \subseteq \mathcal F \subseteq 2^{[n]}$ of sets is a non-induced (weak) copy of a poset $P$ in $\mathcal F$ if there exists a bijection $i:P \to \mathcal G$ such that $p\le_P q$ implies $i(p)\subseteq i(q)$. In the case where in addition$p\le_P q$ holds if and only if $i(p)\subseteq i(q)$, then $\mathcal G$ is an induced (strong) copy of $P$ in $\mathcal F$. We consider the minimum number $sat (n, P)$ [resp. $sat^*(n, P)$] of sets that a family $\mathcal F \subseteq 2^{[n]}$ can have without containing a non-induced [induced] copy of $P$ and being maximal with respect to this property, i.e., the addition of any $G \in 2^{[n]} \setminus \mathcal F$ creates a non-induced [induced] copy of $P$.

We prove for any finite poset $P$ that $sat(n, P)\le 2^{|P|-2}$, a bound independent of the size $n$ of the ground set. For induced copies of $P$, there is a dichotomy: for any poset $P$ either $sat^*(n,P)\le K_P$ for some constant depending only on $P$ or $sat^*(n,P)\ge \log_2 n$. We classify several posets according to this dichotomy, and also show better upper and lower bounds on $sat(n,P)$ and $sat^*(n,P)$ for specific classes of posets.

Our main new tool is a special ordering of the sets based on the colexicographic order. It turns out that if $P$ is given, processing the sets in this order and adding the sets greedily into our family whenever this does not ruin non-induced [induced] $P$-freeness, we tend to get a small size non-induced [induced] $P$-saturating family.

Joint work with Keszegh, Lemons, Martin, and Pálvölgyi.

Материалы: balazs_saturation_slides.pdf (317.6 Kb)

 ОТПРАВИТЬ:
 Обратная связь: math-net2022_01 [at] mi-ras ru Пользовательское соглашение Регистрация посетителей портала Логотипы © Математический институт им. В. А. Стеклова РАН, 2022