Timeline for Hexagonal rooks
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 1, 2012 at 14:47 | comment | added | Noam D. Elkies | 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$. | |
| Aug 1, 2012 at 14:36 | comment | added | Jeremy Martin | 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. | |
| Jul 31, 2012 at 6:01 | history | edited | Noam D. Elkies | CC BY-SA 3.0 |
Added sketch of [(2n/3)+1] rook construction for all n (and diagram for n=15)
|
| Jul 31, 2012 at 5:16 | history | edited | Noam D. Elkies | CC BY-SA 3.0 |
Added diagram for n=12
|
| Jul 31, 2012 at 4:39 | history | edited | Noam D. Elkies | CC BY-SA 3.0 |
Edited mostly to acknowledge JM&JW's proof and give gp code
|
| Jul 31, 2012 at 4:34 | comment | added | Noam D. Elkies | 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). | |
| Jul 31, 2012 at 4:14 | comment | added | Jeremy Martin | 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 | |
| Jul 31, 2012 at 3:22 | history | answered | Noam D. Elkies | CC BY-SA 3.0 |