11 votos

¿Son unimodales los términos de error de las sumas parciales de inclusión-exclusión?

A menudo enseño inclusión-exclusión : $$|A B| = |A| + |B| |A B|$$ sugiriendo que $|AB|$ es un factor de corrección para $|A|+|B|$ . Entonces enseño la versión de tres sets:

$$|ABC| = |A| + |B| + |C| |AB| |AC| |BC| + |ABC|$$

sugiriendo de nuevo que $(|AB|+|AC|+|BC|)$ y luego $+|ABC|$ son factores de corrección.

Bueno, se me ha ocurrido que quizá utilizar más términos de la inclusión-exclusión general no sea siempre una buena idea.

De hecho, con cinco conjuntos es fácil encontrar ejemplos en los que $|A|+|B|+|C|+|D|+|E|$ es una mejor aproximación a $|ABCDE|$ que es la segunda suma parcial: $$|A|+|B|+|C|+|D|+|E| \left({|AB|+|AC|+|AD|+|AE|+|BC|+ \atop |BD|+|BE|+|CD|+|CE|+|DE|}\right).$$

En otras palabras, el "término restante" en la inclusión-inclusión no es necesariamente monotónicamente no creciente.

Sin embargo, no he encontrado ningún ejemplo en el que el término resto no sea unimodal.

Dada una colección $\{A_i : 1 i k \}$ de subconjuntos de $\{ 1, \ldots, n \}$ defina los términos restantes

$$R_m = \left|\;\; \sum_{r=m}^k (-1)^r \sum_{I \in \Large\binom{[k]}{r}} \left| \bigcap \{ A_i : i \in I \}\right|\;\; \right|$$

Debe $R$ ser unimodal?

¿Siempre se da el caso de que haya algún $j$ con $R_2 R_3 \cdots R_j R_{j+1} \cdots R_k$ ?

9voto

aetaur Puntos 11

No es necesario que los términos de error sean unimodales. Sea $x$ sea un punto que está en $A_i$ para exactamente $n \geq 1$ índices $i \in [k] := \{1,\ldots,k\}$ . Conocer $n$ en realidad no es tan difícil dar una fórmula para $x$ al término de error $R_m$ y creo que esto aclara bastante lo que está pasando. En realidad usaré $R_m$ para

$$ \left| \bigcup_{i=1}^k A_i \right| - \left( \sum_{r=1}^m (-1)^{r+1} \sum_{I \in \binom{[k]}{r}} \left| \bigcap_{i \in I} A_i \right| \right)$$

es decir, el firmado error que resulta cuando contamos sólo la contribución a la fórmula de inclusión-exclusión de $r$ -intersecciones dobles, $1 \leq r \leq m$ .

Desde $n \geq 1$ , $x$ debe contribuir exactamente $1$ a $| \bigcup_{i =1}^k A_i |$ . Para números enteros positivos $r$ el número de $r$ -subconjuntos de elementos $I$ de $[k]$ para lo cual $x \in \bigcap_{i \in I} A_i$ es $\binom{n}{r}$ (eligiendo entre los $n$ índices $i$ para lo cual $x \in A_i$ ). Así, $x$ La contribución de $R_m$ es simplemente

$$ 1 - \left[ \binom{n}{1} - \binom{n}{2} + \ldots \pm \binom{n}{m} \right] = \sum_{r = 0}^m (-1)^r \binom{n}{r} = (-1)^m \binom{n-1}{m}$$

donde la forma cerrada puede obtenerse utilizando la identidad $\binom{a+1}{b+1} = \binom{a}{b} + \binom{a}{b+1}$ e inducción. Desgraciadamente no veo una prueba combinatoria. Ahora está claro que $x$ La contribución de $R_m$ es más significativo cuando $m \sim (n-1)/2$ y es $0$ para $m \geq n$ .

Ahora es fácil refutar la unimodalidad. Por ejemplo, si ponemos las cosas de modo que el universo consiste en un gran número $N$ de puntos que están en $A_i$ por ejemplo $10$ de la $i \in [k]$ y un único punto más que se encuentra en $A_i$ para $100$ de la $i \in [k]$ entonces $|R_m|$ tendrá un pico alrededor de $m=4,5$ cuando el $N$ puntos tienen el mayor efecto. El punto adicional contribuirá en mayor medida al error cuando $m \sim 50$ y esto dará lugar a otro pico en $R_m$ desde el $N$ puntos ya habrán dejado de tener efecto después de que $m=10$ .


Añadido: Como muestra la respuesta de Gerry, el contraejemplo que propuse más arriba es bastante subóptimo. No había jugado con los números en absoluto cuando lo di, así que hice los números grandes por una vaga paranoia sobre los efectos de borde.

Estoy de acuerdo en que el ejemplo de Gerry minimiza simultáneamente el número de conjuntos de la colección y el número de elementos del universo. Si $c_n \geq 0$ es el número de elementos en exactamente $n$ conjuntos de la colección para $n=1,2,\ldots,k$ entonces, a partir del argumento anterior, tenemos

$$R_m = (-1)^m \sum_{n=1}^k c_n \binom{n-1}{m}$$

Por lo tanto, las posibilidades para la secuencia de residuos absolutos son exactamente las combinaciones lineales enteras no negativas de las filas de la matriz:

$$\begin{array}{clcr} 0 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & \cdots \\ 3 & 3 & 1 & 0 & 0 & 0 & 0 & \cdots \\ 4 & 6 & 4 & 1 & 0 & 0 & 0 & \cdots \\ 5 & 10 & 10 & 5 & 1 & 0 & 0 & \cdots \\ 6 & 15 & 20 & 15 & 6 & 1 & 0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$

Por ejemplo, los residuos absolutos del ejemplo de Gerry se obtienen tomando coeficientes no nulos 6, 4 y 1 para las filas 2ª, 3ª y 7ª. Creo que, visto así, quizá sea más fácil convencerse de que se trata de la elección "mínima" de coeficientes para que la combinación lineal resultante no presente unimodalidad.

9voto

user8269 Puntos 46

He aquí un ejemplo explícito de no unimodalidad. Utilizamos $7$ conjuntos: $$\eqalign{A_1&=A_2=\lbrace a,b,c,d,e,f,g,h,i,j,k\rbrace\cr A_3&=\lbrace g,h,i,j,k\rbrace\cr A_4&=A_5=A_6=A_7=\lbrace k\rbrace\cr}$$ Entonces los restos absolutos van $20,19,20,15,6,1,0$ .

Este puede ser, en cierto sentido, el ejemplo mínimo. No creo que se pueda hacer con menos de $7$ conjuntos, o menos de $11$ (pero mis razones implican un considerable juego de manos y apelaciones a la verosimilitud).

7voto

Brad Tutterow Puntos 5628

Esto no es directamente una respuesta a tu pregunta sobre la unimodalidad, pero espero que esté bien publicarlo ya que es una respuesta bastante buena a la pregunta planteada implícitamente en la primera parte de tu mensaje: ¿hasta qué punto es cierto que los términos finales de la fórmula son "correcciones" de la suma parcial?

Este documento de Linial y Nisan analiza el comportamiento de la secuencia $R_m$ en términos de cuánto se aproxima a la respuesta final. Resulta que la aproximación es pobre a través de $m=O(\sqrt{k})$ y entonces empieza a proporcionar estimaciones bastante buenas de la respuesta final. Estoy bastante seguro de que el comportamiento en la primera fase no es necesariamente monótono, lo que significa que la respuesta a tu pregunta es "no", pero no creo que esto se aborde directamente en el documento.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X