Skip to main content
1 of 4
Noam D. Elkies
  • 79.9k
  • 15
  • 281
  • 376

Nice question. Will Sawin's upper bound of $2n/3 + 1$ is attained 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.

Jeremy Martin also asks:

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

Experimentally (for $3 \leq n \leq 16$) the adjacency matrix of this graph 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. Assuming that indeed the minimal eigenvalue is $-3$, it would follow 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 suffices to prove the optimality of Will Sawin's cocliques of size $5$ for $n=6$ and of size $7$ for $n=9$.

Noam D. Elkies
  • 79.9k
  • 15
  • 281
  • 376