Skip to content. | Skip to navigation

Personal tools

This is SunRain Plone Theme

Navigation

You are here: Home / Discrete Mathematics Seminars / A tour problem on a toroidal chessboard

A tour problem on a toroidal chessboard

Event details

When

Feb 13, 2019
from 02:30 PM to 03:30 PM

Where

AULA M - Department of Computer Science - Strada le Grazie 15, Verona

Contact Name

Add event to calendar

Dr. Simone Costa, University of Brescia

 

Let us consider a partially filled \(n\times m\) array \(A\), a vector of directions, one for each row, \(R:=(r_1,\dots,r_n)\in \{\leftarrow,\rightarrow\}^n\) and a vector of directions, one for each column, \(C:=(c_1,\dots,c_m)\in \{\uparrow,\downarrow\}^m\). For example:

\[\begin{array}{l|r|r|r|r|r|r|r|}
& \uparrow   & \downarrow   & \uparrow   & \uparrow    &\uparrow   & \downarrow  & \downarrow   \\\hline
\rightarrow  & \bullet &    &    &    &    \bullet &  \bullet &  \bullet \\\hline
\rightarrow   & \bullet &  \bullet &       &    &   &  \bullet &  \bullet \\\hline
\leftarrow   &    \bullet &  \bullet &  \bullet &     &    &  &  \bullet \\\hline
\leftarrow   &    \bullet &  \bullet &  \bullet &  \bullet &       &    &   \\\hline
\rightarrow   &     &   \bullet &   \bullet &   \bullet &   \bullet &    &    \\\hline
\rightarrow   &      &     &  \bullet &  \bullet &  \bullet &  \bullet &    \\\hline
\leftarrow   &      &      &   &  \bullet &  \bullet &  \bullet &  \bullet \\\hline
\end{array}\]

From a filled position \((i,j)\), we move first in the row \(i\) following the direction of \(r_i\) (skipping the holes) and then, from the intermediate position \((i,j')\), we move in the direction of \(c_{j'}\) (skipping the holes) arriving in the position \(S_{R,C}(i,j)\). We propose the following problem:
Is it possible to choose \(R\) and \(C\) so that, starting from a filled position and iterating \(S_{R,C}\), we cover all the filled positions of \(A\)?

In this talk we will see how this problem naturally arises studying biembeddings of orthogonal cycle decompositions on surfaces via Heffter arrays. Although the general problem is widely open, we have been able to solve it in some instances and here we will present an overview of the results we achieved and of the open questions we met.

Bibliography

[1] D.S. Archdeacon, Heffter arrays and biembedding graphs on surfaces, Electron. J. Combin. 22 (2015) \#P1.74.

[2]  S. Costa, M. Dalai, A. Pasotti, A tour problem on a toroidal chessboard., In preparation.

[3] S. Costa, F. Morini, A. Pasotti, M.A. Pellegrini, Globally simple Heffter arrays and orthogonal cyclic cycle decompositions., Austral. J. Combin. 72 (2018), 549--593.

[4] J.H. Dinitz and A.R.W. Mattern, Biembedding Steiner triple systems and $n$-cycle systems on orientable surfaces, Austral. J. Combin. 67 (2017), 327--344.

Document Actions

Filed under: ,