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

Ближайшие семинары

Для просмотра файлов Вам могут потребоваться

Межкафедральный семинар МФТИ по дискретной математике
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).

ОТПРАВИТЬ: FaceBook Twitter Livejournal
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020