On the Steenrod length of real projective spaces: Finding longest chains in certain directed graphs
type: Item
instance of: scholarly article
title: On the Steenrod length of real projective spaces: Finding longest chains in certain directed graphs
zbMATH Open document ID: 0934.05070
DOI: 10.1016/S0012-365X(98)00383-5
author: R. Vakil
published in: Discrete Mathematics
publication date: 2000-04-10T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1331484
zbMATH Keywords: chains
zbMATH Keywords: homotopy theory
zbMATH Keywords: directed graph
reviewed by: David P. Brown
MaRDI profile type: Publication
cites work: Q3961493
cites work: Ideals in triangulated categories: Phantoms, ghosts and skeleta
description: scientific article; zbMATH DE number 1331484