Problema de maximización relacionado con el conjunto de representantes comunes

Question

Se nos da el conjunto $\{1, \dots n\}$ y solicitó construir $A = \{A_1 \dots A_s\}$ donde $|A_i|=k$ , $|A| = s$ , $A_i \subset \{1, \dots n\}$ .

Decimos que $S$ es un conjunto mínimo de representantes comunes de $A$ si $\forall i \in 1\dots k :S\cap A_i \ne \emptyset$ et $|S|$ es mínimo posible.

La tarea consiste en proponer dicha configuración de $A$ donde $\eta(A) = 2$ et $s$ es máxima.
$\eta(A)$ es la cantidad de diferentes $S$ existente para un determinado $A$ .

Ejemplo
$\{1, \dots 5\}$ , $k = 3$
$A = \{\{1,2,3\}\{1,2,4\},\{1,2,5\}\}$
Toma, $s = |A| = 3$ et $\eta(S) = 2$ ya que hay 2 conjuntos de representantes: $\{1\},\{2\}$ .

Proyecto de solución
Fijamos dos elementos de $\{1 \dots n\}$ . Supongamos que son $1$ et $2$ sin pérdida de generalidad.
Construimos $A$ con respecto a la norma : $\forall i \in 1\dots k : 1 \in A_i, 2 \in A_i$ .
Todos los demás elementos llenos de todas las formas distintas posibles.
Entonces, $|S| = 1$ (es $1$ ou $2$ ). Por lo tanto $\eta(A) = 2$ mientras que $s= \binom {n-2} {k-2}$ .
El problema es que no tengo ni idea de cómo demostrar la maximalidad.
Tampoco estoy muy seguro de que mi solución proporcione el máximo $s$ .
Su ayuda será muy apreciada.

Answer 1

Para el caso $n \equiv 1 \mod 2$ . Definimos $n = 2m+1$ , $k = m+1$ .
Entonces podemos definir dos conjuntos de representantes, $S_1$ et $S_2$ tal que:

• $|S_1| = |S_2| = m$
• $\{1 \dots n\} = S_1 \cup S_2 \cup x$
• $S_1 \cap S_2 = \emptyset$
• $S_1 \cap x = \emptyset$
• $S_2 \cap x = \emptyset$ .

A continuación, construimos $A$ de tal manera que contenga todas las combinaciones posibles de tamaño k, excepto las que contengan todos los elementos para $S_j$ et $x$ . Sólo hay dos, así que $s = \binom n {\lfloor n/2 \rfloor + 1} - 2$ .

Para $n \equiv 0 \mod 2$ se aplica la misma lógica pero sin $x$ .
Los resultados adquiridos serían máximos, ya que cuanto más grande $|S|$ da la restricción más débil sobre $A_i$ estructura, y para $\eta(S) = 2$ no podemos ampliar $|S|$ más sin romper la restricción de la minimalidad del conjunto.