# Hexagonal rooks

Suppose you have a triangular chessboard of size $n$, whose "squares" are ordered triples $(x,y,z)$ of nonnegative integers that add up to $n$. A rook can move to any other point that agrees with it in one coordinate -- for example, if you are on $(3,1,4)$ then you can move to $(2,2,4)$ or to $(6,1,1)$, but not to $(4,3,1)$.

What is the maximum number of mutually non-attacking rooks that can be placed on this chessboard?

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

-
Can you prove what the maximal number of mutually non-attacking bishops is on an ordinary n×n chessboard? – Zsbán Ambrus Jul 30 '12 at 21:52
The bishop question is easy - it's 2n-2. Put bishops along two opposite edges and remove two at adjacent corners. This is maximal since there are only 2n-1 different North-East diagonals, and two of these are opposite corners so only 2n-2 can be filled. – Carl Jul 30 '12 at 22:27
The graph is regular, of degree $2n$. If you put a rook on $(n,0,0)$, the problem reduces to finding the maximum number of non-attacking rooks on the board of order $n-2$. I think the graph has enough symmetry that no matter where you put the first rook you reduce the problem to that of order $n-2$, but I'm not sure. If the graph does have that symmetry, then by induction you get more-or-less $n/2$ rooks ($(n+2)/2$ if $n$ is even, $(n+1)/2$ if $n$ is odd). – Gerry Myerson Jul 30 '12 at 23:01
That's a nice idea, but I don't think it works. If you remove (2,1,0) from $G_3$, you get a path of length $3$, not a cycle. – David Speyer Jul 30 '12 at 23:23
One of the coordinates must have an average value of no more than $n/3$ among all the rooks. The maximal number of distinct nonnegative integers whose avergae is $n/3$ is $2n/3+1$. This is a better bound. – Will Sawin Jul 31 '12 at 1:00

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

-
Good references. The first paper (Nivasch-Lev, Mathematics Magazine 2005) ends up giving another proof of the $\lfloor 2n/3 \rfloor + 1$ bound, and the same construction to attain this bound. – Noam D. Elkies Jul 31 '12 at 15:23
Cristi, thanks! I didn't know about either of these references. – Jeremy Martin Jul 31 '12 at 19:35
You're welcome, Jeremy. – Cristi Stoica Jul 31 '12 at 20:21

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$.

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.

-
Noam, you've scooped me! :-) Jennifer Wagner and I have recently proved this conjecture by giving an explicit basis of eigenvectors. Writeup forthcoming. (Even more generally, we conjecture that the "simplicial rook graph" --- put a vertex at each lattice point in the $n$th dilate of the standard simplex in $\mathbb{R}^d$; edges are pairs of vertices at Hamming distance 2 -- has integer eigenvalues.) Corollary: the independence number of the triangular rook graph is at most $3(n+2)(n+1)/(2(2n+3))$. But, indeed, this bond is not tight. Back to the independence question: it appears tha – Jeremy Martin Jul 31 '12 at 4:14
Seems like your comment was cut off by the 600-character limit. Anyway, it's not really a "scoop" since I only conjectured it (though I see that the lower bound of $-3$ on the spectrum is not hard, and likewise for your generalization to higher dimension). – Noam D. Elkies Jul 31 '12 at 4:34
I was going to ask about the independence number about the higher-dimensional simplicial rook graph. The computational evidence I have suggests that the least eigenvalue is $\min(-n,-\binom{d}{2})$. E.g., for $d=4$, $n\geq 6$, this would imply that the independence number $\alpha(n)$ is at most $a(n)=\lfloor(n+1)(n+3)/3\rfloor$. This is not a tight bound (e.g., $a(6)=21$, $\alpha(6)=16$) and I would guess that it is not even asymptotically tight. – Jeremy Martin Aug 1 '12 at 14:36
The eigenvalue bound (which you probably mean to be $\max(-n,-{d\choose 2})$, not $\min$) can be proved in the same way, by writing the adjacency matrix as the sum of $d\choose 2$ adjacency matrices (one for each direction) each with minimal eigenvalue $-1$. – Noam D. Elkies Aug 1 '12 at 14:47

For n=6 you can fit 5 rooks

(0,2,4) (4,0,2) (1,4,1) (3,3,0) (2,1,3)

For n=9 you can fit 7 rooks

(0,3,6) (6,0,3) (2,6,1) (4,5,0) (3,1,5) (5,2,2) (1,4,4)

-

A visualization aid, $n=10$:

And now here are Will Swain's rook placements:

-