El problema de los subconjuntos de a $\{1, 2,\dots,n\}$

Question

Deje $A=\{1, 2,\dots,n\}$ ¿Cuál es el máximo número posible de subconjuntos de a $A$ con la propiedad de que dos de ellos tienen exactamente un elemento en común ?

Tengo la fuerte sospecha de que la respuesta es $n$, pero no puede probarlo.

Answer 1

Este es un conocido tipo de problema en la combinatoria. (Intente buscar en google "exacto intersecciones".) La (ligera) la generalización de su reclamo, por lo que se requiere de $|A\cap B|=\ell>0$ siempre $A\neq B$, es al parecer debido a Fisher.

Deje $\mathcal{A}$ ser una familia de subconjuntos de a $\{1,2,\dots,n\}$ tal que para cada dos distintos $A,B\in\mathcal{A}$ tenemos $|A\cap B|=\ell$. Pretendemos $|\mathcal{A}|\leq n$. Sin duda estamos hecho si algunos de $A\in\mathcal{A}$ tiene el tamaño de $\ell$ (esto es, en donde utilizamos $\ell>0$), por lo que asumir lo contrario.

Para cada una de las $A\in\mathcal{A}$ considera que el indicador "vector" $1_A\in\mathbf{R}^n$ $1_A(x)=1$ si $x\in A$ $0$ lo contrario. Yo reclamo que $\{1_A : A\in\mathcal{A}\}$ es un conjunto linealmente independiente, por lo $|\mathcal{A}|\leq n$.

Supongamos $\lambda_A\in\mathbf{R}$ son algunos de los coeficientes tales que

$$\sum_{A\in\mathcal{A}} \lambda_A 1_A = 0.$$

Tomando el producto escalar con $1_B$, señalando $1_A\cdot 1_B = \ell$ al $A\neq B$, tenemos

$$\lambda_B |B| + \sum_{A\neq B} \lambda_A \ell = 0.$$

Reorganizar un poco,

$$\lambda_B (|B| - \ell) = - \ell\sum_{A\in\mathcal{A}} \lambda_A.$$

Conclusión: o $\sum\lambda_A = 0$, en cuyo caso todos los $\lambda_B=0$ (desde $|B|>\ell$ todos los $B\in\mathcal{A}$) o $\sum\lambda_A\neq 0$, en cuyo caso todos los $\lambda_B$ son cero y de signo opuesto a $\sum\lambda_A$, imposible.

Answer 2

Sugerencia: Para un conjunto de duración $i > 2$, ningún otro conjunto puede tener cualquier subconjunto del conjunto $i \ge 2$ como un subconjunto.

Answer 3

[De cómo recuperar a mostrar ideas, no porque esto es válido o respuesta completa.]

Deje $S_1,S_2,\dots,S_m$ ser una secuencia no vacía de conjuntos tal que cuando se $i\neq j$,$|S_i\cap S_j|=1$. A continuación, queremos demostrar que:

$$\left|\bigcup S_i\right| \geq m$$

Deje $S=\cup S_i$. Para cualquier $x\in S$, definir $n_x=\left\{i:x\in S_i\}\right|$. A continuación, nos muestra la siguiente forma bastante sencilla:

$$\sum_{x\in S} n_x = \sum_{i=1}^m |S_i|$$ $$\sum_{x\in S} \binom{n_x}{2} =\binom m 2$$ $$\binom{|S|}{2} \geq \sum_{i=1}^{m} \binom{|S_i|}{2}$$

La primera cuenta los pares de $(x,i)$ $x\in S_i$ en dos maneras. El segundo cuenta los pares de $i,j\in\{1,\dots,m\}$ en dos maneras. El último es un resultado de cualquier pareja en $S$ está contenida en más de un $S_i$.

Podemos afirmar $n_x>1$ todos los $x$ porque si $n_x=1$ cualquier $x$ le puede quitar que un $x$ e la $S_i$, y obtener un contra-ejemplo con un menor $m$.

Si hay alguna que no está vacía $J\subsetneq I=\{1,\dots,m\}$ tal que $$|\bigcup_{j\in J} S_j|< |J|$$ we'd also have a smaller counterexample. So we can assume that $\izquierda|\bigcup_{j\J} S_j\right|\geq |J|$ for all $\emptyset\neq J\subsetneq I$.

En particular, esto significa que $|S|\geq m-1$. Desde que asumimos que tenemos un contraejemplo, que significa que $|S|=m-1$.

Pero esto también significa que para cualquier $J\subsetneq I$ podemos encontrar un conjunto de los distintos representantes de la $x_{i}\in S_i$ cuando $i\in J$, por el Hall del matrimonio teorema.

La fijación de $k\in I$, nos jet $J_k=I\setminus\{k\}$. entonces tenemos un conjunto de $m-1$ distintos elementos $\{x_i:i\neq k\}$$x_i\in S_i$. Desde que asumimos nuestro conjunto no tiene ningún tipo de elemento de, nosotros tenemos ese $\{x_i\}=\cup_{j\in I} S_j$.

Todavía no estoy viendo.