Hexagonal rooks

Nice question!

For the maximum number of pairwise non-defending rooks, Will Sawin proved an upper bound of $(2n/3) + 1$ in his comment to the original question. This bound is attained, at least to within $O(1)$, by two rows of $n/3 - O(1)$ rooks each, starting from around $(2n/3,n/3,0)$ and $(n/3,2n/3,1)$ and proceeding by steps of $(-1,-1,2)$ until reaching the $y=0$ or $x=0$ edge of the triangle. This construction generalizes Sawin's five-Rook placement for $n=6$.

On further thought, it seems we actually achieve $\lfloor (2n/3) + 1 \rfloor$ exactly for all $n$. Here's how it works for $n=12$ and $n=15$, with $(2n/3)+1 = 9$ and $11$ respectively:

                                            .   
                                           . . 
                                          . . . 
            .                            . . . . 
           . .                          . . . . . 
          . . .                        R . . . . . 
         . . . .                      . . . . . . R 
        R . . . .                    . R . . . . . . 
       . . . . . R                  . . . . . . . R . 
      . R . . . . .                . . R . . . . . . . 
     . . . . . . R .              . . . . . . . . R . . 
    . . R . . . . . .            . . . R . . . . . . . . 
   . . . . . . . R . .          . . . . . . . . . R . . . 
  . . . R . . . . . . .        . . . . R . . . . . . . . . 
 . . . . . . . . R . . .      . . . . . . . . . . R . . . . 
. . . . R . . . . . . . .    . . . . . R . . . . . . . . . . 

Starting from such a solution with $n=3m$, we can add an empty row to get an optimal solution for $n=3m+1$, and remove an edge (and the Rook it contains) to get an optimal solution for $n=3m-1$. So this should solve the problem for all $n$.

Jeremy Martin also asks:

More generally, is anything known about the graph whose vertices are these ordered triples and whose edges are rook moves?

I don't remember reading about this graph before. Experimentally (for $3 \leq n \leq 16$) its adjacency matrix has all eigenvalues integral, the smallest being $-3$ with huge multiplicity $n-1\choose 2$; more precisely:

Conjecture. For $n \geq 3$ the eigenvalues of the adjacency matrix are: a simple eigenvalue at the graph degree $2n$; a $n-1\choose 2$-fold eigenvalue at $-3$; and a triple eigenvalue at each integer $\lambda \in [-2,n-2]$, except that $\mu := \lfloor n/2 \rfloor - 2$ is omitted, and $\mu - (-1)^n$ has multiplicity only $2$.

This is probably not too hard to show. For example, the $\lambda = -3$ eigenvectors constitute the codimension-$3n$ space of functions whose sum over each of the $3(n+1)$ Rook lines vanishes. [Added later: in the comment Jeremy Martin reports that he and Jennifer Wagner already made and proved the same conjecture.]

Given that the minimal eigenvalue is $-3$, it follows by a standard argument in "spectral graph theory" that the maximal cocliques have size at most $3(n+1)(n+2)/(4n+6) = 3n/4 + O(1)$. But that's asymptotically worse than $2n/3 + O(1)$, though it's still good enough to prove the optimality of Will Sawin's cocliques of size $5$ for $n=6$ and of size $7$ for $n=9$.

Here's some gp code to play with this graph and its spectrum:

{
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
}

running "R($n$)" puts a list of the vertices in "l" and returns the adjacency matrix with the corresponding labeling. So for instance

matkerint(R(7)-2)~
matkerint(R(8)-1)~

returns matrices whose rows are nice generators of the $2$-dimensional eigenspaces of the $n=7$ and $n=8$ graphs.


Here is a paper about this problem: "Non-attacking queens on a triangle".

And here's another one "Putting Dots in Triangles"


A visualization aid, $n=10$:
           HexChess n=10

And now here are Will Swain's rook placements:
HexRooks n=6,5HexRooks n=9,7