A pinboard by
Peleg Michaeli

PhD student, Tel Aviv University


Studying graph-theoretic properties of the trace, considered as a (random) subgraph

Given some graph (nodes connected with edges), a walker is located at a given "starting" node. At each step, the walker looks at its current neighbours (nodes which are connected to its current location by an edge) and chooses one, uniformly at random, independently of all previous choices, and traverse the edge leading to that node, and so on. The set of nodes visited by the walker (up to some predetermined time) is called the range of the walk, and the set of edges traversed by the walker is called the trace of the walk.

We consider the subgraph obtained by the trace, on the same node set. This is, by definition, a random subgraph. The main goal now is to investigate this random creature in graph-theoretic perspective, i.e., ask standard graph-theoretic questions about it, such is: is it connected? does it contain a long cycle? etc.

This question is somewhat new in its field. While many questions have been asked regarding the range of a random walk on a finite graph, this question about the trace is novel.