1 votos

Existencia de una familia de conjuntos con algunas propiedades

¿Es posible encontrar un ejemplo de una familia $\mathcal{F}$ de $n$ conjuntos finitos distintos no vacíos, un universo de tamaño máximo $n/4$ con al menos $\lfloor \frac{2}{3}{n \choose 2} \rfloor$ parejas desordenadas de conjuntos con al menos un elemento en común entre los dos conjuntos, y ningún elemento que pertenezca al menos a $n/2$ ¿conjuntos de la familia?

0voto

zjffdu Puntos 123

Tomemos un plano proyectivo finito: en aras de la concreción, el plano de Fano $PG(2, 2)$ . Tiene siete puntos $P$ y siete líneas $L$ donde cada línea pasa por tres puntos y cada par de líneas se cruza.

Tome un segundo conjunto $S$ que es disjunta de $P$ y un elemento $x$ que tampoco está. Considere $$\mathcal{F} = L \times 2^S \cup \{\{x\}\}$$ y que $n = |\mathcal{F}| = 7 \cdot 2^{|S|} + 1$ . Cada elemento de $P$ está en $\frac{3}{7}(n-1)$ conjuntos; cada elemento de $S$ está en $\frac{1}{2}(n-1)$ conjuntos; $x$ está en un conjunto. Todo par de conjuntos que no incluya $\{x\}$ tiene una intersección no vacía. El tamaño del universo es $|S| + 8$ por lo que esta familia satisface todas las restricciones siempre que $4|S| + 32 \le 7 \cdot 2^{|S|} + 1$ lo que es cierto si $|S| \ge 3$ .


Para valores más generales de $n$ , dejemos que $a$ sea el mayor número entero tal que $7 \cdot 2^a < n$ . Si tomamos dos conjuntos disjuntos $S_1, S_2$ con $|S_1| = |S_2| = a$ entonces $L \times \left(2^{S_1} \cup 2^{S_2} \right)$ tiene más de $n$ pero cada elemento de $S_1 \cup S_2$ ocurre exactamente $7 \cdot 2^{a-1} < \frac n2$ veces. Cada elemento de $P$ ocurre exactamente $3 \cdot 2^{a+1}$ veces, por lo que al elegir $\mathcal{F} \subset L \times \left(2^{S_1} \cup 2^{S_2} \right)$ debemos tener cuidado de mantener la proyección sobre $L$ equilibrado, pero si hacemos esto entonces cada elemento de $P$ no se producirá más de $\frac{3}{7}n + 3$ veces.

Entonces simplemente requerimos que el universo sea suficientemente pequeño. Ahora el tamaño del universo es $7 + 2a$ y comprobamos que la construcción funciona para $n \ge 44$ .

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