## Schedules in {0,1}n (Open)

Summary: It is desired to find the distribution of cycle lengths in a certain family of digraphs. The nth graph in this family has vertex set {0,1}n, and (u,v) belongs to the edge set if and only if v can be obtained from u by (i) changing the first coordinate from 0 to 1, (ii) changing the nth coordinate from 1 to 0, or (iii) changing a consecutive pair from (1,0) to (0,1). A first step would be to determine or estimate the length of the longest cycle in such a graph. This problem arises in connection with multichamber tools for IC manufacturing.

Classification: Primary, discrete mathematics; Secondary, graph theory

**Download Problem**[PDF]

**Dusan Jevtic**

Applied Materials, Inc.

2861 Scott Blvd.

M/S 1950

Santa Clara, CA 95050

e-mail: Dusan_Jevtic@amat.com