6
$\begingroup$

By a egg-box diagram I will simply mean a (possibly infinite) rectangular array of holes, with some of the holes containing an egg (denoted by a filled-in circle) and the rest of the holes are empty (denoted with an empty circle). For instance $$ \begin{array}{|c|c|c|c|} \hline \bullet & \circ & \circ &\circ \\ \hline \bullet & \circ & \bullet &\bullet \\\hline \circ & \bullet & \bullet & \bullet\\\hline \end{array} $$ is a $3\times 4$ egg-box diagram.

When I say that two eggs are connected in a diagram, I mean that we can pass from one egg to the other egg via a series of rook moves (i.e., moving within a given column or row) without ever stopping on an empty hole. All the eggs in the previous diagram are connected; it takes at most 4 moves to get from one egg to another. For added simplicity, we consider "staying put" as a row (and as a column) move. (Consequently, eggs connected in $n$ moves are also connected in $n+1$ moves.) In the diagram above, note that the egg in the top left corner is connected to the egg in the bottom right corner in three moves, by a column-row-column movement, but not a row-column-row movement.

By a permutation I will just mean a permutation of the rows and columns. For instance, if we consider the permutation where we switch the two middle columns and cyclically shift the rows downward, and we apply that permutation to the diagram above, then $$ \begin{array}{|c|c|c|c|} \hline \circ & \bullet & \bullet & \bullet\\\hline \bullet & \circ & \circ &\circ \\ \hline \bullet & \bullet & \circ&\bullet \\\hline \end{array} $$ is the diagram we obtain.

By an automorphism of a diagram I will mean a permutation that results in the same diagram. For example, the only automorphisms of the first diagram are the identity permutation and the permutation that only switches the last two columns.

The types of diagrams I care about satisfy an extremely strong switching property: If there are two eggs that lie in the same row (or column), then there is an automorphism that switches the eggs. (Note: Such an automorphism may need to permute many other rows and columns too.)

Question: Is there a diagram satisfying the switching property, where all the eggs are connected in three moves, but (at least) two eggs are not connected in three moves if we start with a column movement?

The motivation for my questions comes from the fact that I can translate some of my work in ring theory into this combinatorial situation. I'm wondering how much of what we can prove algebraically is really just a consequence of combinatorial ideas. In particular, if we change "three" to "two" in the previous question, the answer is no, and this gives a much simpler proof for something I had previously proven using some deep algebra.

$\endgroup$
2
  • $\begingroup$ This looks like Rees matrix semigroups $\endgroup$ Commented Aug 5, 2022 at 22:27
  • 1
    $\begingroup$ Your egg-box diagrams can also be interpreted as simple bipartite graphs with vertices in each part indexed by rows and columns, respectively. The eggs correspond to edges and your notions of connectedness and automorphisms correspond to the same notions for bipartite graphs. $\endgroup$ Commented Aug 8, 2022 at 14:42

1 Answer 1

1
$\begingroup$

It turns out (surprisingly) that the answer to my question is yes, and there are even finite examples. I came up with the following diagram $$ \begin{array}{|c|c|c|c|c|c|} \hline \circ & \circ & \bullet & \circ & \bullet & \bullet\\\hline \circ & \bullet & \circ & \bullet & \circ & \bullet\\\hline \bullet & \circ & \circ & \bullet & \bullet & \circ\\\hline \bullet & \bullet & \bullet & \circ & \circ & \circ\\\hline \end{array} $$ where for any pair of rows, there is exactly one column with eggs in just those two rows.

$\endgroup$

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