Ejemplos difíciles para la conjetura de unión cerrada de Frankl

Question

La conocida conjetura de Frankl sobre la unión cerrada afirma que si F es una familia finita de conjuntos que se cierra al tomar las uniones (es decir, si A y B pertenecen a la familia, también lo hacen $A\cup B$ ), entonces debe haber un elemento que pertenezca al menos a la mitad de los conjuntos.

Sé que cualquier enfoque ingenuo que se haga de esta conjetura es conocido por su fracaso. Por "aproximación ingenua" supongo que me refiero a algo así como una observación que se desprende de tal o cual conjetura más fuerte -parece que todas las conjeturas más fuertes sensatas en las que uno piensa son falsas-. Un ejemplo muy sencillo de una conjetura más fuerte sería que si se elige un elemento al azar, éste pertenecerá por término medio a al menos la mitad de los conjuntos. Esto es completamente falso: tomemos la familia formada por el conjunto vacío, {1}, y {1,2,3,4,5,6,7,8,9,10}, por ejemplo. Se puede intentar "corregir" este refuerzo con artificios como insistir en que para dos elementos cualesquiera hay un conjunto que contiene a uno y no al otro (lo que WLOG es el caso), pero tales correcciones no llevan muy lejos.

Lo que pido son ejemplos, ya sean pequeños o construidos teóricamente, de familias cerradas por la unión que venzan a refuerzos más sofisticados de la conjetura original. Estoy bastante seguro de que existen, pero no soy un experto en este problema, así que no los conozco.

Pido disculpas de antemano si esto se parece a una pregunta ya existente (que parece que podría ser fácilmente). Pero he buscado y no he encontrado nada.

Answer 1

Aquí hay un buen ejemplo debido a Bjorn Poonen, que he tomado de esto papel de encuesta de Bruhn y Schaudt. Está motivado por las siguientes observaciones. Sea $\mathcal{A}$ ser una familia cerrada por la unión. Llama a un elemento $x$ abundante si $x$ está contenida en al menos la mitad de los miembros de $\mathcal{A}$ .

Observación. Si $\mathcal{A}$ contiene un singleton $\{x\}$ entonces $x$ es abundante.

Prueba. Partición $\mathcal{A}$ como $\mathcal{A}_x$ y $\overline{A}_x$ donde $\mathcal{A}_x$ se compone de los miembros de $\mathcal{A}$ que contiene $x$ y $\overline{A}_x$ son los miembros de $\mathcal{A}$ que no contenga $x$ . Desde $\{x\} \in \mathcal{A}$ y $\mathcal{A}$ es una unión cerrada, el mapa $S \mapsto S \cup \{x\}$ es una inyección de $\overline{A}_x$ a $\mathcal{A}_x$ . Así, $|\overline{A}_x| \leq |\mathcal{A}_x|$ según sea necesario. $\square$

Del mismo modo, también tenemos lo siguiente.

Observación. Si $\mathcal{A}$ contiene un $2$ -Configurar $\{x,y\}$ entonces $x$ o $y$ es abundante.

Esto podría llevarnos a conjeturar el siguiente refuerzo falso de la conjetura de unión cerrada de Frankl.

Falso fortalecimiento. Dejemos que $S$ sea un miembro no vacío de $\mathcal{A}$ con el menor número de elementos. Entonces $S$ contiene un elemento abundante.

A prueba de bombas. Para dos familias $\mathcal{A}$ y $\mathcal{B}$ dejamos que $$ \mathcal{A} \uplus \mathcal{B}=\{S \cup T: S \in \mathcal{A}, T \in \mathcal{B}\}. $$

Arreglar $k \geq 3$ y para cada $i \in [k]$ definir $$ \mathcal{B}^i=\{[k+1,3k] \setminus \{2i+k-1\}, [k+1,3k] \setminus \{2i+k\}\}. $$

Por último, defina $$ \mathcal{A}^k=\{[k]\} \cup \bigcup_{i=1}^k(\{\emptyset, \{i\}, [k]\} \uplus \mathcal{B}^i) \cup (2^{[k]} \uplus [k+1,3k]). $$

Es fácil comprobar que $\mathcal{A}^k$ es una unión cerrada y que $[k]$ es el único conjunto más pequeño en $\mathcal{A}^k$ . Sin embargo, $|\mathcal{A}^k|=1+6k+2^k$ y cada $i \in [k]$ está contenida sólo en $1+(2k+2)+2^{k-1}$ miembros de $\mathcal{A}^k$ . Por lo tanto, ningún elemento de $[k]$ es abundante. $\square$

Este ejemplo pone de manifiesto uno de los obstáculos a la hora de demostrar la Conjetura de la Unión Cerrada; es difícil predecir dónde estarán los elementos abundantes.

Answer 2

i) Definiciones :
Dejemos que $F$ sea una familia cerrada de unión (familia U.C. para abreviar)
Dejemos que $S$ := $\cup_{ \Omega \in F} \Omega $ (el apoyo de la familia).
Dejemos que $F_{x} $ denotan los miembros de $F$ que contiene $x$ .

A) Unión cerrada Variación media ( con $S$ ser $T_0$ -separado por $F$ )

$ \sum_{x \in S}{ |F_{x}| } is \ge |F|.|S|/2 $ .
( Eso es la media $F_x$ tamaño (en $S$ ) es mayor que $|F|/2$ )

Nota : No encuentro ningún contraejemplo.
El $T_0$ separación de $ S $ por $ F $ significa que para dos puntos diferentes cualesquiera ${x,y} $ existe un miembro de $F$ que contiene un punto y no el otro (¡puede elegir cuál!) .

Otra vía de generalización que no puedo descartar es la variación de los conjuntos múltiples.

B) Variación de Mutltiset :
F es una familia de $(\Omega,\eta_{\Omega})$ donde:
- la $\Omega$ forma una familia U.C dicen $F_0$
- $\eta : F_0 \rightarrow \mathbb {N}^{\gt 0}$ ( o $\mathbb {R^{\gt 0}}$ o $ [1,2,..,p]$ ordenado naturalmente )
- para cualquier $ \Omega_1 , \Omega_2$ de $F_0$ : $ \eta_{\Omega_1 \cup \Omega_2} \ge Sup ( \eta_{\Omega_1} ,\eta_{\Omega_2} )$

Ahora la conjetura es: La mejor medida $F_x$ es al menos la mitad que la de $F$ donde medida significa la suma de las medidas de los miembros : la conjetura estándar de U.C. aparece cuando $\eta$ es la función constante uno.

C) El punto de vista general: (no es estrictamente una generalización como pide M.O.),
El problema de U.C. creo que es de naturaleza fundamental, pertenece a estructuras muy débiles en el siguiente sentido: en el álgebra las estructuras débiles (o básicas o atómicas) son los ideales, en el caso de un orden (o celosía) es una alteración (una familia estable por sobreinclusión, si no se dice que un sobreconjunto de cualquier miembro es un miembro), mientras que tenemos en este problema algo aún más débil o básico: estable sólo por max. Todo esto viene de observar, primero, que la conjetura de U.C. es fácil para la familia de los trastornados y sigue sin resolverse por lo demás y, segundo, que las técnicas algebraicas no son muy útiles.

Answer 3

No estoy seguro de si este es el tipo de cosas que estás buscando, pero aquí hay un fortalecimiento de la conjetura original para la que me gustaría tener un contraejemplo.

Dejemos que $\mathcal{S}$ sea una familia de unión cerrada y que $V$ sea el conjunto máximo en $\mathcal{S}$ . Dado $x \in V$ , escriba $\mathcal{S}\_x $ para la familia $\{A\setminus\{x\}: \ A \in \mathcal{S}, x \in A\}$ y $d_{\mathcal{S}}(x)= |\mathcal{S}_x|$ para el grado de $x$ en $\mathcal{S}$ .

Afirmación: Supongamos que $x$ es un elemento de $\mathcal{V}$ de grado mínimo en $\mathcal{S}$ . Entonces, para cada $y \neq x$ tenemos \frac{d_{mathcal{S}_x}(y)}{d(x)}geq \min \left(\frac{1}{2}, \frac{d(y)}{|mathcal{S}|}right).\f

(En otras palabras, si un elemento tiene el grado más bajo en $\mathcal{S}$ que los demás elementos deben estar bien correlacionados con él).

Answer 4

Aquí hay una generalización, bastante fuerte : Dejemos que $E$ sea un conjunto finito $F\subset \mathcal P(E)$ , de tal manera que $\emptyset\notin F$ , $E\in F$ y $F$ cerrado para la unión.

Dejemos que $f(F)=\left\{x\in E| |F_x|<|F|/2\right\}$ donde $F_x=\left\{a\in F|x\in a\right\}$ .

Conjetura: $f(F)\notin F$ .

(Conjetura de Unión Cerrada $\iff$ $f(F)\ne E$ ).