报告题目：The Snake-in-the-Box Problem

报告人：Sergey Kitaev (University of Strathclyde)

报告时间： 5月22日下午4:00

                                                 

报告地点： 博B108

摘要:

The snake-in-the-box problem involves finding the longest induced path in a hypercube, starting from a corner and avoiding revisiting or stepping into neighbours of previous nodes. Each node in the path (except the head and tail) must have exactly two neighbours in the path. Formally, it's a special case of the induced subgraph isomorphism problem. A related variant, the coil-in-the-box problem, seeks long induced cycles.

First introduced by Kautz in 1958, the problem has applications in error-correcting codes, where the paths form Gray codes that detect single-bit errors. These codes are valuable in areas like electrical engineering and network design. As the hypercube’s dimension increases, finding the longest snake or coil becomes computationally difficult.

The presentation is intended to be self-contained and accessible to a broad audience.