Buena pregunta!
Para el número máximo de pares no la defensa de torres,
Se Sawin demostrado un límite superior de $(2n/3) + 1$
en su comentario a la pregunta original. Este límite se alcanza,
al menos hasta dentro de $O(1)$, por dos filas de $n/3 - O(1)$ torres cada una,
a partir de alrededor de $(2n/3,n/3,0)$ e $(n/3,2n/3,1)$
y por el procedimiento de los pasos de $(-1,-1,2)$ hasta llegar a la
$y=0$ o $x=0$ borde del triángulo. Esta construcción
generaliza Sawin de cinco Torre de la colocación de $n=6$.
En otro pensamiento, parece que la forma de lograr
$\lfloor (2n/3) + 1 \rfloor$ exactamente para todos los $n$.
He aquí cómo funciona para $n=12$ e $n=15$,
con $(2n/3)+1 = 9$ e $11$ respectivamente:
.
. .
. . .
. . . . .
. . . . . . .
. . . R . . . . .
. . . . . . . . . . R
R . . . . . R . . . . . .
. . . . . R . . . . . . . R .
. R . . . . . . . R . . . . . . .
. . . . . . R . . . . . . . . . R . .
. . R . . . . . . . . . R . . . . . . . .
. . . . . . . R . . . . . . . . . . . R . . .
. . . R . . . . . . . . . . . R . . . . . . . . .
. . . . . . . . R . . . . . . . . . . . . . R . . . .
. . . . R . . . . . . . . . . . . . R . . . . . . . . . .
A partir de una solución con $n=3m$, se puede agregar una fila vacía
para obtener una solución óptima para $n=3m+1$, y quitar un borde
(y la Torre que contiene) para obtener una solución óptima para $n=3m-1$.
Así que esto debería resolver el problema para todas las $n$.
Jeremy Martin también le pregunta:
De manera más general, es todo lo conocido sobre el grafo cuyos vértices
son estos ordenó triples y cuyos bordes están torre se mueve?
Yo no recuerdo haber leído acerca de este gráfico antes.
Experimentalmente (por $3 \leq n \leq 16$) de su matriz de adyacencia
tiene todos los autovalores integral, el ser más pequeño $-3$ con enorme multiplicidad
$n-1\choose 2$; más precisamente:
Conjetura. Para $n \geq 3$ los autovalores de la matriz de adyacencia son:
un autovalor simple en el gráfico de grado $2n$; a $n-1\choose 2$veces
autovalor en $-3$; y un triple autovalor en cada entero
$\lambda \in [-2,n-2]$, salvo que $\mu := \lfloor n/2 \rfloor - 2$
se omite, y $\mu - (-1)^n$ tiene multiplicidad sólo $2$.
Esto probablemente no es demasiado difícil de demostrar. Por ejemplo, el $\lambda = -3$
los vectores propios constituyen la codimension-$3n$ espacio de funciones
cuya suma de cada una de las $3(n+1)$ Torre líneas se desvanece.
[Añade después: en el comentario de Jeremy Martin informes que
él y Jennifer Wagner ya hecho y probado de la misma conjetura.]
Dado que el mínimo autovalor es $-3$,
se sigue por un argumento estándar en "espectral de la teoría de grafos"
que la máxima cocliques han tamaño en la mayoría de las $3(n+1)(n+2)/(4n+6) = 3n/4 + O(1)$.
Pero eso es asintóticamente peor que $2n/3 + O(1)$, aunque todavía
lo suficientemente bueno como para demostrar la optimalidad de la Voluntad Sawin del cocliques de tamaño
$5$ para $n=6$ y de tamaño $7$ para $n=9$.
He aquí algunos gp de código para jugar con este gráfico y su espectro:
{
R(n)=
l = [];
for(a=0,n,for(b=0,n-a,l=concat(l,[[a,b,n-a-b]])));
matrix(#l,#l,i,j,vecmin(abs(l[i]-l[j]))==0) - 1
}
la ejecución de "R($n$)" pone una lista de los vértices en forma de "l" y devuelve
la matriz de adyacencia con el correspondiente etiquetado. Así, por ejemplo,
matkerint(R(7)-2)~
matkerint(R(8)-1)~
devuelve las matrices cuyas filas son agradables generadores de la
$2$-dimensiones subespacios propios de la $n=7$ e $n=8$ gráficos.
