Pares de intersección de los conjuntos de tamaño fijo

Question

El Erdős-Ko-Rado teorema habla acerca de cómo los grandes de intersección conjunto del sistema (un conjunto de pares de intersección de conjuntos) puede ser si el tamaño de la base es fija. Estoy interesado acerca de la intersección de establecer sistemas en los que el conjunto de base no es fijo, pero el tamaño de los conjuntos acotados. Puedo probar el siguiente lema (ver la prueba a continuación).

Lema 1. Para cada número natural $k$ no es un número natural $N(k)$ tal que para cada conjunto $C$ cada uno de cuyos elementos son conjuntos de tamaño en la mayoría de las $k$, si cada dos elemento de $C$ tiene un común de los miembros, hay un kernel $A$ que es un conjunto de tamaño en la mayoría de las $N$, de modo que cada dos elemento de $C$ también tiene en común un miembro que está en $A$.

Me gustaría saber si este lema es conocido en la literatura, y si me puede dar una simple prueba de lo que la mía.

También me gustaría saber qué vinculados pueden dar a la $N(k)$. Exacto obligado es, probablemente, difícil y no demasiado interesante, pero me gustaría obtener el orden de magnitud, decir si se puede hacer $N(k)$ un polinomio de $k$. Mi prueba sólo da $N(k) = 2^{O(k^2)}$, así que cualquier cosa con un menor orden de magnitud sería bueno. (Sé que $N(k)$ se $\Omega(k^2)$. Usted puede mostrar esta utilizando un prime $q$ entre $k/2-1$ e $k-1$ y, a continuación, dejando $C$ el conjunto de líneas de un número finito de plano proyectivo de orden $q$.)

También hay un fortalecimiento de la lema, que sigue fácilmente de mi prueba y que pueden ser útiles.

Lema 2. Para cada número natural $k$ no es un número natural $N^{\ast}(k)$ tal que para cada conjunto $C$ cada uno de cuyos elementos son conjuntos de tamaño en la mayoría de las $k$, si cada dos elemento de $C$ tiene un común de los miembros, hay un kernel $A$ que es un conjunto de tamaño en la mayoría de las $N^{\ast}$, de modo que si $Y \in C$ e $X$ es un conjunto que cruza cada elemento de $C$ e $X$ tiene más de $k$ elementos , a continuación, $X \cap Y \cap A$ es no vacío.

Actualización: el original de la redacción del lema 2 estaba equivocado, he añadido la condición de que $|X|\le k$.

Estoy haciendo la misma pregunta que el anterior para esta versión más fuerte, y también si se sigue fácilmente desde el primer lema.

La prueba del lema 1.

Fix $k$. Vamos a utilizar la inducción en $p$ a mostrar la existencia de un conjunto $A_p$ de manera tal que el tamaño de $A_p$ está delimitado por un constante número natural, dependiendo únicamente de la $k$ e $p$ (pero no $C$), y que para cada $X \in C$ bien $p \le |X \cap A_p|$ o de la intersección $X \cap Y \cap A_p$ no está vacía para cada $Y\in C$. Esto es suficiente ya que el $A = A_{p+1}$ cumple las condiciones del lema (de hecho, incluso $A = A_p$ funcionaría). El caso de $p = 0$ es trivial, debido a que $A_0$ puede ser el conjunto vacío.

Ahora supongamos que hemos encontrado $A_p$ y queremos construir $A_{p+1}$. Ahora ordenar los elementos de $C$ en clases de equivalencia tal que dos elemento es equivalente, si su intersección con $A_p$ es igual. Hay en la mayoría de las tantas clases como subconjuntos de $A_p$ (o incluso de los subconjuntos en la mayoría de las $k$ elementos), que es una constante obligado porque el tamaño de $A_p$ es acotado por una constante. Ahora eligió un solo elemento de cada clase de equivalencia y deje $B$ el conjunto de estos elementos. Deje $A_{p+1} := A_p \cup \bigcup_{Y\in B} Y$.

Por lo tanto todos tenemos que demostrar es que por cada $X \in C$ bien $X \cap A_{p+1}$ tiene al menos $p+1$ o elementos que se cruza cada elemento de $C$. A partir de la hipótesis de inducción sabemos que $X \cap A_p$ tiene, al menos, $p$ elementos o se cruza con cada elemento de $C$. Si es esto último, hemos terminado, porque $X \cap A_{p+1}$ es un superconjunto de $X \cap A_p$, así que vamos a suponer ahora que el ex: $X \cap A_p$ tiene al menos $p$ elementos. Ahora si $X \cap A_{p+1}$ cruza todos los elementos de $C$, entonces hemos terminado, así que también podemos suponer que hay un $Z \in C$ tal que $X \cap A_{p+1} \cap Z$ está vacía. Ahora, considere la clase de $Z$ en la equivalencia que hemos definido anteriormente, es decir, todos los conjuntos de $Y$ para que $Y \cap A_p = Z \cap A_p$, y deje $Y$ ser el representante elemento elegimos de esta clase para la construcción. Esto significa que $Y \in B$ lo $Y \subset A_{p+1}$. Ahora $X$ e $Y$ tiene un elemento común, decir $x$. Ahora no es posible que $x \in A_p$, debido a que por nuestra segunda hipótesis de $X \cap Y \cap A_p = X \cap Z \cap A_p \subset X \cap Z \cap A_{p+1}$ está vacía. Pero, a continuación, $X \cap A_{p+1}$ tiene, al menos, $p$ elementos de $X \cap A_p$ a partir de nuestra primera hipótesis (porque $A_p \subset A_{p+1}$), y el elemento adicional $x$ que no está en $X \cap A_p$, por lo que tiene, al menos, $p + 1$ elementos, lo que completa la prueba.

Answer 1

Esta no es una respuesta, sino simplemente una manera de pensar sobre la pregunta que me gusta bastante. (Más tarde: consulte a continuación un intento de prueba.)

Vamos a considerar cada juego dentro de nuestra colección como un vértice de un grafo, y vamos a unir dos vértices si y sólo si los conjuntos correspondientes se cruzan. Eso no suena muy interesante, ya que estamos en la hipótesis de que cada par de conjuntos de cruza. Pero eso está bien ... obtenemos el grafo completo. El interés es en lo que podemos decir acerca de cómo el gráfico se construye. Para cada punto x en la planta de conjunto, podemos definir una camarilla en el gráfico: sus vértices son todos los conjuntos de nuestra colección que contienen a x. Esto nos da un sistema de camarillas, cuya unión es el conjunto de la gráfica. ¿Qué más sabemos acerca de estas camarillas? Sabemos que cada vértice está contenida en exactamente k de ellos. Y qué es lo que queremos demostrar? Que podemos elegir N(k) de nuestros grupos cerrados que cubren el grafo completo.

Se siente más natural para relajar el problema y sólo insistir en que cada vértice está contenida en en la mayoría de los k de los grupos.

En la dirección inversa, si tenemos un montón de grupos cerrados que cubren el grafo completo, que se puede asociar con cada uno de los vértices del conjunto de las camarillas que contienen ese vértice, y la condición de que los conjuntos que se intersectan es precisamente la condición de que los grupos de cubrir todos los bordes de la gráfica. Así que es un trivial de reformulación, pero creo que es una alternativa útil foto de lo que está pasando.

Añade después: aquí es un intento de mejorar el obligado a $k^{Ck}$. Creo que funciona pero no tengo 100% comprobado.

Tomar un mínimo de subcolección S de los grupos que cubre el grafo completo, y supongamos que S contiene $N$ camarillas.

Porque S es mínima, para cada camarilla en S hay algún borde contenida en eso camarilla y no de otra camarilla de S. Desde cada vértice es en la mayoría de los k grupos, sin vértices está contenida en más de k de estos bordes. Así podemos encontrar una colección de al menos N/k separe de los bordes, de cada uno de los cuales está contenida en un solo camarilla de S. sea M el número de aristas en este conjunto.

En este punto voy a ser muy superficiales. Quiero demostrar que M es en la mayoría de las $k^{Ck}$ demostrando que si es más grande que eso, entonces voy a tener que tener un vértice que está contenida en más de k camarillas.

Vamos a la M separe de los bordes se llama $x_1y_1,...,x_My_M$, y deje $K_i$ ser la camarilla que contiene $x_i$ e $y_i$. Vamos a partir de dos pandillas $L_i$ e $M_i$ de $K_i$, que se obtiene por extracción de $x_i$ y uno por la eliminación de $y_i$. Luego entre ellos $L_i$ e $M_i$ cubrir todas las aristas que se $K_i$ cubre, además de la perimetral $x_iy_i$. Así que vamos a hacer si podemos mostrar que algunos vértices tiene que estar incluido en más de 2k de las camarillas $L_i$ e $M_i$, junto con otras camarillas que no contengan ninguna de las aristas $x_iy_i$.

Así, nuestra hipótesis es que ahora tenemos un montón de grupos, y para cada i no camarilla contiene $x_i$ e $y_i$, y sin embargo todos los otros pares $x_iy_j$ o $y_ix_j$ se unen en al menos uno de los grupos. Queremos mostrar que algunos vértice está contenida en al menos 2k camarillas.

En particular, para cada i y j (no igual a) debemos tener una camarilla que se une a $x_i$ a $y_j$ o $y_i$ a $x_j$ (ya que en realidad debemos hacer ambas cosas). Pero no camarilla siempre contiene $x_i$ e $y_i$ o ambos $x_j$ e $y_j$.

Dado cualquier camarilla $K$ a partir de la nueva colección, el conjunto de pares ij tal que $K$ se une a $x_i$ a $y_j$ o $y_i$ a $x_j$ es un bipartito gráfico. (Su vértice conjuntos son el conjunto de i tal que $K$ contiene $x_i$ y el conjunto de i tal que $K$ contiene $y_i$.) Así que nos gustaría para cubrir un grafo completo con M vértices con bipartita de los gráficos, de tal manera que ningún vértice está contenida en más de 2k de los grafos bipartitos.

Un promedio de argumento (este es el boceto de bits) debe demostrar que podemos descuento bipartito gráficos con un conjunto de vértices que es menor que la de cM/k, ya que no contribuyen lo suficiente para el grado medio. Pero si simplemente usamos bipartito de gráficas con los conjuntos de vértices de tamaño al menos cM/k, entonces podemos usar el siguiente argumento estándar. Deje $X_1$ ser uno de los conjuntos de vértices de la primera bipartito gráfico. Entonces ninguno de los bordes dentro de $X_1$ están cubiertos. Así que por inducción sabemos que el número de vértices en $X_1$ es en la mayoría de los M(k-1) (donde la M que estamos tratando de obligado es M(k)). Pero es también, al menos cM(k)/k, por lo que tenemos un límite de $(k/c)^k$ para M.

Agregó más adelante: yo creo que puede ser capaz de utilizar ideas similares a probar un límite inferior. Tome $2^k$ pares de $x_sy_s$, donde cada s es un vértice de la discreta k-dimensional del cubo. Para cada i entre 1 y k formar una camarilla por unirse todos los $x_s$ tal que $s_i=0$ a todos los $y_s$ tal que $s_i=1$, y también al revés. A continuación, para cada s no es igual a t vamos a cubrir tanto los bordes de la $x_sy_t$ e $x_ty_s$. También, nunca llegamos a cubrir el borde de la $x_sy_s$, y el número de camarillas es 2k. Una cosa más ... cada vértice está contenida precisamente en 2k camarillas hasta ahora. Añadimos ahora en todos los grupos de tamaño 2 con vértice conjuntos de $x_s,y_s$. Así que ahora cada vértice es precisamente en 2k+1 camarillas. Así que tenemos un sistema mínimo de, al menos, $2^k$ camarillas, con cada vértice en 2k+1 de ellos. Por lo tanto, el límite para el problema original (si mi razonamiento es correcto) es al menos exponencial.

Answer 2

Aquí es cómo hacer que la última parte de gowers la prueba precisa (la idea es de Gábor Simonyi).

Usted tiene un grafo completo de $M$ vértices cubiertos por $t$ bipartito gráficos tal que cada vértice es en la mayoría de los $4k-2$ de estos gráficos. Quieres demostrar que el $M \le 2^{4k-2}$. Ahora para cada gráfico bipartito y cada vértice no en ella, el doble del vértice y agregar uno a cada clase de color. Se han duplicado cada vértice al menos $t-4k+2$ veces así que ahora tiene, al menos, $2^{t-4k}$ vértices. Cada vértice está en cada gráfico bipartito, y aún cada vértice se une a cada uno con un borde de al menos un bipartito gráfico, por lo que no puede haber más de $2^tM$ vértices, o de lo contrario habría dos vértices que estaba en la misma clase en cada gráfico bipartito. Por lo tanto, $M \le 2^{4k-2}$.

Actualización: corregido errores en las fórmulas.

Actualización: mis números estaban aún apagado, he marcado las actualizaciones. La estimación que se recibe, no es $ M \le 2^{2k} $ pero $ M \le 2^{4k-2} $ lo $ N \le 2k\cdot 2^{4k-2} $. La razón es que una vez que reemplazar las camarillas $ K_i $ con $ L_i, M_i $, cada vértice $ x_j $ o $ y_j $ será en la mayoría de los $ 2k-1 $ camarillas, así, en el nuevo grafo completo cada vértice es en la mayoría de los $ 4k-2 $ grafos bipartitos.

Answer 3

Dos otros usuarios y yo mismo llegó de forma independiente con una defectuosa de la prueba de su lema uso de la Δ-Sistema de Lema. Si bien este no es un camino viable para probar su resultado, se da cierta imagen intuitiva de lo que estas familias C parecer. Δ-sistemas fueron estudiados por primera vez por Erdős y Rado (Intersección teoremas para los sistemas de conjuntos, I, II, III). Una más reciente papel en el tema es Deuber, Erdős, Gunderson, Kostochka, Meyer, de la Intersección de las declaraciones de los sistemas de conjuntos, J. Combinat. La Teoría De La Ser. Un 79 (1997), 118--132. MR1449752

Una manera de enfatizar la independencia del tamaño de la familia C es el estado el lema sin la suposición implícita de que el C es finito. De hecho, una aplicación del Teorema de Compacidad muestra que la existencia de la N(k) en su Lema 1 es equivalente al hecho de que:

Para cada (posiblemente infinita) de la familia C de k-elemento de los conjuntos de parejas con las intersección no vacía no es un conjunto finito tal que cualquiera de los dos elementos de C se cruzan en A.

Se deduce la existencia de N(k) a partir de este hecho en la misma forma en que se deduce la finitos Ramsey Teorema de los infinitos Teorema de Ramsey. Demostrar el teorema de esta manera le permite saltarse un par de líneas de la prueba, evitando el énfasis que el tamaño de a es independiente de C. sin Embargo, hay poca ganancia en no señalar el uniforme de los límites, ya que le da un (posiblemente crudo), vinculado en N(k) que la compacidad argumento no.

Answer 4

No estoy seguro acerca de una sencilla prueba, porque me parece una prueba muy elegante. Creo que puedo conectar la declaración a algo que es (o era) bien estudiado. Parece que conseguir una mejora en la envolvente, pero sería bueno si alguien verificó el argumento.

Vamos a N ser los números naturales. Recordemos que el Erdős-Rado de la teoría de Ramsey teorema dice que, si hemos de color de las aristas del grafo completo de N por N los colores, entonces nos están garantizados para encontrar una infinita subconjunto S de los vértices tales que, restringido a S, el color es uno de los siguientes. (Aquí, i < j y k < l son números naturales en S.)

1. Monocromático: c(i,j) = c(k,l) para todo i,j,k,l;
2. A la derecha de color: c(i,j) = c(k,l) ffi j = l;
3. A la izquierda-de color: c(i,j) = c(k,l) si i = k;
4. Arco iris: c(i,j) =/= c(k,l) para todo (i,j)=/=(k,l).

Supongamos por un momento que su familia C de k-sets contables, revisión una enumeración C(1),C(2),..., y hacer que sus elementos se unen los vértices de un completo contables gráfico. Color del borde entre C(i),C(j) con el conjunto C(i)∩C(j). El uso de Erdős-Rado para obtener una infinita subfamilia C'(1),C'(2),..., donde el color es uno de los de arriba. Se consideran los casos.

1. C' no puede ser un arco iris, ya que desde cada vértice C'(i) no emanan en la mayoría de los 2^k. Nuestro color es "localmente finito", si se quiere.
2. C' no se puede ser a la izquierda-de color cualquiera. Supongamos que fuera; entonces C'(1) debe tener la misma intersección yo con todos los C'(i) para i>1. Por lo tanto I' = C'(2)∩C'(3) debe incluir yo, pero diferente de él, es decir, debe ser un adecuado superconjunto de I. a Continuación, I' = C'(2)∩C'(i) para todo i>2, y I" = C'(3)∩C'(4) debe incluir yo', sino que será un verdadero superconjunto. Seguimos como este, la obtención de una estrictamente creciente de la cadena de I,I',I",... de las intersecciones. Pero cada uno tiene el tamaño en la mayoría de los k, una contradicción.
3. Somos un argumento similar para demostrar que C no puede ser a la derecha de color. La observación es, básicamente, que el argumento en el punto 2 se ejecuta en una contradicción en la mayoría de los k pasos, así que en lugar de empezar con C'(1) y en adelante, empezamos con C'(k+1) e ir hacia atrás.
4. Los más difíciles caso es cuando C' es monocromática, que como vimos es la única posibilidad. Esto significa que C'(i)∩C'(j) es el mismo conjunto I para todo i=/=j. (Se nota que me tiene en la mayoría de los k-1 elementos.) Esto no resuelve el problema porque no pueden ser miembros de C que están a la izquierda de C', pero, como veremos, monochromaticity pone un grave restiction en ellos.

En primer lugar, tenga en cuenta que cada k-B en la C hasta que se cruzan yo, de lo contrario B tendría que cruzan el infinito de pares distintos de la familia C'(i)\I. Siguiente partimos C en p = 2^k-1 clases de equivalencia, cada una etiquetada por un subconjunto no vacío de I. pusimos cada k-de la serie B en la clase etiquetado B∩I. denominaremos a los miembros de una clase etiquetado I' ⊆ I por I'(1),I'(2),...

Para todos los discontinuo I',I" ⊆ I, si las clases etiquetados I',I" son ambos no vacío, entonces tienen en la mayoría de los k-1 elementos de cada uno de ellos: porque si yo'(1),...,I'(k) se encontraban en clase I "y yo"(1) en la clase I", entonces yo"(1)\I se cruzarían cada uno de los miembros de los pares distintos de la familia I'(1)\I,...,I'(k)\I; pero yo"(1)\I tiene a lo sumo k-1 elementos.

Ahora, por fin, la construcción de nuestra serie que desea, Una, de la siguiente manera. Para cada par de disjuntas I',I" ⊆ I tal que las clases etiquetados I',I" no vacío, obtenemos I'(1),...,I'(k-1) y yo"(1), y aferrarse a ellos. (No podría ser que muchos de I'(i); acaba de agarrar a todos ellos.) Por último nos coge un poco de conjunto que contiene a I, por ejemplo, un miembro de C' en el punto 4.

Ahora, hay (3^k-2*2^k+1)/2 (desordenada) pares de disjuntos no vacíos I',I" ⊆ I; para cada uno de estos que tenemos en la mayoría de los k conjuntos. Por lo tanto su unión, Una, tiene a lo sumo k²(3^k-2*2^k+1)/2 elementos, y tiene la propiedad de que dos miembros de la familia C se cortan en A. es evidente que esto tiene para la I'(i),I'(j) en la misma clase, y si tenemos que tomar la I'(i),I(j) en diferentes clases, I',I" se cruzan, en cuyo caso, por lo que hago "(i),I(j); o I',I" son disjuntas. En ese caso, ya que I'(i),I(j) se intersecan en I'(i), y nos aseguramos de incluir en todos los I'(1),...,I'(k-1), también estamos en buena forma. QED?

Suponiendo que el argumento anterior es correcto en absoluto, creo que es posible refinar el último bit, después de que hemos construido yo, que tal vez vienen más cerca del límite inferior que Gowers habla.

Answer 5

Me enteré de que este es un problema conocido, y que se resolvió en 1973. El Lovász: Combinatorical problemas y ejercicios en realidad le da una solución en el ejercicio 13.27. Esto le da asintóticamente mejores estimaciones que cualquier cosa que pudiera derivarse aquí.

Una generalización (donde los conjuntos están obligados a ser s-sabio de intersección en lugar de a pares) se puede encontrar en N. Alon, Z. Füredi: En el Núcleo de la Intersección de las Familias, Gráficas y Combinatoria 3, 91-94 (1987).