  Ближайшие семинары Календарь семинаров Список семинаров Архив по годам Регистрация семинара Поиск RSS Ближайшие семинары

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

M. Tancer

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

Аннотация: 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-net2020_11 [at] mi-ras ru Пользовательское соглашение Регистрация Логотипы © Математический институт им. В. А. Стеклова РАН, 2020