Los niños no quieren en un círculo

Question

$n\geq 3$ los niños deben colocarse en un círculo. Algunas parejas de niños no se gustan entre sí y no quieren estar al lado del otro. (El desagrado es mutuo.) ¿Cuál es el máximo $k$ de tal manera que si a cada niño no le gusta más que $k$ otros niños, entonces siempre es posible una colocación?

Si a un niño no le gusta $n-2$ otros niños, es evidente que no es posible una colocación porque no podemos encontrar dos niños para estar al lado de este niño. Si a un niño no le gusta $n-3$ otros niños, sus dos vecinos son fijos.

Answer 1

Considere a los niños como vértices de un grafo, donde una arista conecta a dos niños que se gustan. Entonces el problema se reduce a encontrar un ciclo hamiltoniano en este grafo.

Por el teorema de Dirac, todos los $n$ -gráficos de vértices cuyo grado mínimo es al menos $\left\lceil\frac n2\right\rceil$ son hamiltonianos. Esto se traduce en un máximo $k$ de $$n-1-\left\lceil\frac n2\right\rceil=\left\lfloor\frac{n-2}2\right\rfloor$$ Por ejemplo, si seis niños son tales que a cada uno le disgustan como máximo otros dos, siempre podemos sentarlos alrededor de la mesa. Si a cada uno le desagradan otros tres, y el patrón de gustos es el siguiente:

  A F
 /| |\
B | | E
 \| |/
  C D

entonces no podemos sentarlos en la mesa.

Para mostrar la nitidez del límite para $k$ mostrado arriba, dividir $n-1$ vértices en dos conjuntos $A$ y $B$ de la manera más equitativa posible (así $|A|=\left\lceil\frac{n-1}2\right\rceil$ y $|B|=\left\lfloor\frac{n-1}2\right\rfloor$ ). Construir dos gráficos $K_{|A|}$ y $K_{|B|}$ y enlazar el único vértice restante con todos los demás vértices. El gráfico resultante tiene un máximo $k$ uno más que el límite, pero es no hamiltoniano.

Answer 2

Esto es demasiado largo para un comentario, pero creo que la respuesta de @parcly-taxel es incompleta. El teorema de Dirac se traduce en un máximo $k$ de al menos $\lfloor\frac{n-2}{2}\rfloor$ no es igual. Para completar el argumento, también hay que demostrar que no hay ningún valor de $n$ para el que es posible un asiento siempre que haya como máximo $\lfloor\frac{n}{2}\rfloor$ aversión por niño.

Siguiendo el ejemplo de Parcly para $n=6$ y el comentario de Henning sobre la pregunta inicial, no hay tal $n$ por el siguiente contraejemplo:

Que el conjunto de hijos sea $\{a_1,\dots,a_{\lfloor\frac{n}{2}\rfloor},b_1,\dots,b_{\lfloor\frac{n}{2}\rfloor}\}\cup C$ , donde $C=\emptyset$ si $n$ es par y $C=\{c\}$ si $n$ es impar. Que los disgustos sean los pares $(a_i,b_j)$ . El $a$ los niños deben ser adyacentes, y también los $b$ niños, pero como máximo otro niño $c$ (que le gusta a todo el mundo) no puede separar el $a$ de la $b$ 's en ambos extremos.