Worksheet 01 Combinatorics with Applications in Computer Science

CS607. Combinatorics with Applications in Computer Science

Worksheet 01

Released: 04 Jan, 2024

Problem 1. Relationship between Hamming Distance and Error Correction

Recall that a code \(C\) is a subset of \(S^n\), where \(S\) is a fixed, finite alphabet and \(S^n\) denotes the set of all strings of length \(n\) over \(S\). Recall also that the hamming distance between two \(n\)-length strings \(u\) and \(v\) over \(S\) is the number of indicies on which \(u\) and \(v\) differ, and \(d(C)\) denotes the smallest hamming distance between any pair of strings in \(C\). Finally, a code \(C\) is said to correct \(t\) errors if for every \(u \in S^n\) there is at most one \(w \in C\) such that \(d(u,w) \leq t\).

Now consider the following statement.

A code \(C\) corrects \(d\) errors if and only if: \(d(C) \geq {\color{red}{\star}}\).

What is \({\color{red}\star}\)?

Problem 2. The (Nearly) Impossible Chessboard Puzzle

Is it possible to color the edges of a 64-dimensional hypercube with 64 colors so that the following property holds?

For every vertex of the hypercube, all its neighbors are colored with 64 distinct colors.

Note. A 64-dimensional hypercube is a graph that has one vertex for every bit string of length 64, and two vertices are adjacent if and only if their hamming distance is one.