3
$\begingroup$

The work of Hearth Taxel revealed some other results related to genies' chess. For example, there is an arrangement $A$ of pawns on a 10×10 board such that no 3×3 submatrix is empty and

  • $A$ is symmetric about the main diagonal, which is all pawns
  • Removing any pawn from $A$ leaves at least one empty submatrix, i.e. it is minimal
  • Without the diagonal pawns, $A$ is the adjacency matrix of a symmetric graph, where there are automorphisms taking any vertex/edge to any other vertex/edge. In particular this implies that the row and column sums of $A$ are all equal

Can you find a solution?

$\endgroup$
2
  • $\begingroup$ Does a submatrix have to be a connected subgrid? I mean, does it have to be the intersection of three consecutive rows with three consecutive columns, or can it be the intersection of any three rows and any three columns? $\endgroup$
    – Ankoganit
    Commented Dec 20, 2021 at 12:13
  • 1
    $\begingroup$ @Ankoganit See the first problem for what submatrix means: ranks/files don't have to be consecutive. $\endgroup$ Commented Dec 20, 2021 at 12:22

1 Answer 1

4
$\begingroup$

I claim that

The adjacency matrix of the Petersen graph (with the diagonal elements filled) would work

The first and third conditions are obviously satisfied; to see the zeroth condition

We need to show that for any two sets of three vertices, there exists an edge between them. It's clear if these two set have a common vertex (just take the element on the diagonal); otherwise these two sets must be disjoint. It's not too hard to check cases (whether all three vertices are from a pentagon, or it splits into two from a pentagon, and one from the other one) to verify that this indeed works.

To see the second condition:

If the said pawn is on the diagonal, corresponding a to a vertex $v$ on the "outer pentagon", take the submatrix corresponding to $\{v, p, q \}$ and $\{ v, p', q' \}$, where $p,q$ are the vertices "opposite" to $v$ in the outer pentagon, $v'$ is the vertex on the "inner pentagon" connected to $v$, and $\{ p', q' \}$ are the vertex "opposite" to $v'$ in the "inner pentagon". If it's not on the diagonal, since the Petersen graph is 3-arc transitive (in particular: it acts transitively on the edges, so let that said pawn correspond to $\overline{vv'}$. Take $\{v, p, q \}$ and $\{v', p', q' \}$ to be the rows and columns of the submatrix.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.