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

Межкафедральный семинар МФТИ по дискретной математике
4 мая 2017 г. 18:30, г. Долгопрудный, Актовый зал Лабораторного корпуса МФТИ  Simplifying inclusion-exclusion formulas

M. Tancer

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

Аннотация: Let $\mathcal{F}=\{F_1,F_2, \ldots,F_n\}$ be a family of $n$ sets on a ground set $S$, such as a family of balls in $\mathbb R^d$. For every finite measure $\mu$ on $S$, such that the sets of $\mathcal{F}$ are measurable, the classical inclusion-exclusion formula asserts that $\mu(F_1\cup F_2\cup\cdots\cup F_n)=\sum_{I:\emptyset\ne I\subseteq[n]} (-1)^{|I|+1}\mu(\bigcap_{i\in I} F_i)$; that is, the measure of the union is expressed using measures of various intersections. The number of terms in this formula is exponential in $n$, and a significant amount of research, originating in applied areas, has been devoted to constructing simpler formulas for particular families $\mathcal F$.
During the talk, I will discuss how to get an upper bound valid for an arbitrary $\mathcal F$: we show that every system $\mathcal F$ of $n$ sets with $m$ nonempty fields in the Venn diagram admits an inclusion-exclusion formula with $m^{O(\log^2n)}$ terms and with $\pm1$ coefficients, and that such a formula can be computed in $m^{O(\log^2n)}$ expected time. For every $\varepsilon>0$ we also construct systems with Venn diagram of size $m$ for which every valid inclusion-exclusion formula has the sum of absolute values of the coefficients at least $\Omega(m^{2-\varepsilon})$.
Based on a joint work with X. Goaoc, J. Matousek, P. Patak and Z. Safernova (Patakova).

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