Given an $n \times m$ toral chess board, we color each square with either Black or White. The line separating two squares of different colors, is called a Black-White boundary. How many colorings of the toral chess board yield $k$ Black-White boundaries ?

Another phrasing: Let us denote by $T_{n,m} := C_n \times C_m$ the Cartesian graph product of two cycles.

How many ways are there to color the vertices of $T_{n,m}$ red and blue, such that the number of edges with different color vertices, equals $k$ ?

Yet another phrasing: How many partitions $\{X,Y\}$ of $V(T_{n,m})$ are there, such that $$|E(X,Y)| = k. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.