Supongamos que tengo n finito establece un1 y unn contenida en algunos fijos set S y am dado no negativo números enteros N y y N Nn 1 tales que cada Ai tiene cardinalidad N y cada intersección k-tuple tiene cardinalidad menor o igual a Nk.
¿Puedo usar esto para construir un buen límite inferior en la cardinalidad de la Unión de la A?
Una solución mejor que mi anterior
max_{1\leq i \leq n} en {i \elegir 2}N_2
(Es decir, podemos considerar simplemente, sólo yo soy de los conjuntos en lugar de todos los n de ellos, y, a continuación, aplicar mi argumento anterior para obtener un límite inferior en el tamaño de la unión europea de los que se establece, que es también un límite inferior en el tamaño del total de la unión.)
De hecho, se puede averiguar el valor de i que maximiza esta obligado: será el más grande de la i N - (i-1)N_2 es positivo (ya que esta es la diferencia entre la cota obtenida usando yo y que la obtenida utilizando i-1). Esto es i = \lfloor N/N_2 \rfloor +1.
Así, se tomó el valor de i, la mejor solución que veo es
nN - {n\elegir 2} N_2 si n< i y - {i \elegir 2} N_2.
Esta es, al menos, no negativo. En el último caso, es del orden de N^2/(2N_2).
**
Por supuesto, todavía no estoy utilizando toda la información. No veo cómo conseguir algo más allá de la inclusión-exclusión cuando todo lo que tenemos son límites superiores en los tamaños de los triples y la mayor de las intersecciones. Animo a cualquier persona que piensa que no hay un argumento en no publicar.
(Editado para corregir mi aritmética para el orden de los obligados en el i <= n caso).
(edit: Como Reid Barton señaló estoy asumiendo que usted tiene algún tipo de límite inferior en el Nk , así como un límite superior...si este no es el caso, incluyendo más términos no ayuda en absoluto)
Generalizar Hugh Thomas respuesta, una opción podría ser la de tomar un vistazo a lo que el Bonferonni Desigualdades dar. Esencialmente, usted puede dejar de inclusión-exclusión después de cualquier sustracción y siempre vas a estar a la izquierda con un límite inferior.
Así que si usted no tiene suficiente de la Nk a ejecutar la inclusión-exclusión de todo el camino a través de, o si se hace el cálculo intratable, ver cuál es la mejor cota inferior se puede obtener de lo que usted es.
Utilice el principio de inclusión-exclusión.
No sé la razón para hacer esta pregunta, por lo que es poco probable que lo que voy a escribir va a ser útil. Sin embargo, hay un método sencillo que me gusta mucho para deducir un límite inferior sólo desde el conocimiento de que N_2 es pequeño. Puede ser contenido en lo que se ha dicho anteriormente, no he comprobado.
La idea es pensar en cada conjunto A_ i 01-función con valores en un conjunto de tamaño M. luego miramos la ell_ 2 de la norma de sum_i A_i. La plaza de la ell_ 2 de la norma es sum_ {i,j}|A_ i cap A_ j|, que por supuesto es en la mayoría de las nN + n(n-1)N_ 2. Pero también tenemos un límite inferior: el ell_ 1 de la norma de la suma es nN, del que se desprende que la plaza de la ell_ 2 de la norma es, al menos, (nN)^2/M.
Poniendo estos dos bits de información en conjunto da un límite inferior para el M de nN/(1+(n-1)N_ 2/N). Así, por ejemplo, si N_ 2 = cN para algunas pequeñas constante positiva c, entonces el límite inferior es aproximadamente N/c.
Existe el límite obvio de nN - {n \choose 2} N_2.
(Estoy tomando N_2 ser el límite en el tamaño de una intersección de 2 conjuntos; No estoy seguro si eso es lo que quisiste decir.)
Creo que no es posible hacerlo mejor en general, porque las intersecciones triples y más grandes todo pueden ser cero, en que caso el límite es alcanzado.
Por supuesto, uno podría ser capaz de decir más en una situación más especial, ¿tienes algo más específico en mente?
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.
