Encontrar el número máximo de miembros en el club de matemáticas.

Tienes razón sobre el límite inferior, pero no el superior. El límite superior correcto es$\lfloor n/2\rfloor$para cualquier valor fijo de$k\leq n/2$.

Para ver que este es un límite superior, fije un club con$M$miembros y contar los bordes del gráfico, es decir, pares que son enemigos. debe haber$Mk$empareja con exactamente una persona en el club (cada persona en el club tiene$k$enemigos, ninguno de los cuales está en el club). Hay algún número$r\geq 0$de parejas que están fuera del club. Ahora todos los que no están en el club tienen$k$enemigos, y eso da$(n-M)k$pares ordenados donde la primera persona no está en el club. Esto cuenta cada uno de los$Mk$empareja con exactamente una persona en el club una vez, y cada uno de los$r$parejas de dos no miembros dos veces. Entonces$(n-M)k=2r+Mk$, y desde$r\geq 0$tenemos$n-M\geq M$.

Este límite puede lograrse para cualquier$n$. (Si$k$es impar, entonces cualquier gráfico con cada vértice que tenga un grado$k$debe tener$n$siendo par.) Para ver esto, comience con el gráfico bipartito completo con ambas partes teniendo tamaño$n/2$- cada vértice tiene grado$n/2$. Ahora elimine una coincidencia perfecta, que existe por el teorema de Hall (un corolario del teorema de Hall es que cualquier gráfico bipartito regular, a menos que sea$0$-regular - tiene una combinación perfecta). Esto disminuye todos los grados en$1$. Sigue haciendo esto hasta que cada grado sea$k$. Claramente, cualquiera de las partes del gráfico original no contiene bordes, por lo que es un palo válido y tiene un tamaño$n/2$.

Ahora, para obtener algo entre los dos límites, solo necesita mezclar las dos construcciones. Por ejemplo, si$k=3$y$n=100$puedes obtener$M=25$tomando$25$Copias de$K_4$, o$M=50$por la construcción anterior. Para obtener, digamos,$M=41$, llevar$9$Copias de$K_4$y hacer la construcción de arriba en el resto$64$vértices. Su club óptimo entonces tendrá una persona de cada$K_4$y$32$gente del resto.

Imitando la prueba del enlace, tenemos$k\cdot M \geq n-M$entonces$M\geq {n\over k+1}$

Para el límite superior:

Dejar$G$Sea un gráfico de estudiantes conectados si son enemigos. Claramente este gráfico tiene$\varepsilon ={nk\over 2}$. Supongamos que el conjunto de vértices de este gráfico se puede representar como la unión de camarillas máximas$Q_1,Q_2,...Q_m$. Ya que podemos elegir de cada camarilla como máximo$1$estudiante que tenemos$M\leq m$. Entonces necesitamos encontrar el valor mínimo de$m$. Pero esto ahora es un problema de Clique Covering Number .

Así que si:

• $n=2l+1$entonces podemos hacer$l+1$camarillas por lo que tenemos$M\leq l+1 = \lfloor {n+1\over 2} \rfloor$.
• $n=2l$entonces podemos hacer$l$camarillas por lo que tenemos$M\leq l = \lfloor {n\over 2} \rfloor$.