On the Steenrod length of real projective spaces: Finding longest chains in certain directed graphs (Q1300989): Difference between revisions

Suppose a directed graph has vertices labeled with nonnegative integers \(1,2,\dots\). Suppose there is an outgoing edge from vertex \(n\) for each zero in the binary representation of \(n\): if the \(2^s\) position is 0 the corresponding edge is from vertex \(n\) to vertex \(n-2^s\). Let \(f(n)\) be the length of the longest sequence of edges starting at vertex \(n\) and \(g(n)\) the longest sequence of edges starting from any vertex \(q\leq n\). The author studies properties of \(f\) and shows that the frequency table of \(g(n)\) is a sequence of non-decreasing powers of 2 where \(2^a\) appears \(a+1\) times, \(a\geq 1\). The topological motivation and several open questions are also included.