Forum Problem Lists Definitions FAQ

15.90 (2002)

Open

Let $\Gamma$ be an infinite directed graph, and $\overline{\Gamma}$ the underlying undirected graph. Suppose that the graph $\overline{\Gamma}$ admits a vertex-transitive group of automorphisms, and the graph $\overline{\Gamma}$ is connected and of finite valency. Does there exist a positive integer $k$ (possibly depending on $\Gamma$) such that for any positive integer $n$ there is a directed path of length at most $k \cdot n$ in the graph $\Gamma$ whose initial and terminal vertices are at distance at least $n$ in the graph $\overline{\Gamma}$?

Contributor: V. I. Trofimov

Progress

Comment of 2005: It is proved that there exists a positive integer $k'$ (depending only on the valency of $\overline{\Gamma}$) such that for any positive integer $n$ there is a directed path of length at most $k' \cdot n^2$ in the graph $\Gamma$ whose initial and terminal vertices are at distance at least $n$ in the graph $\overline{\Gamma}$ (V. I. Trofimov, Europ. J. Combinatorics, 27, no. 5 (2006), 690–700).

Comments

All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic. If you want to submit a proof (or a partial proof), please use the dedicated proof submission form rather than posting it in the comments.
Order by newest first or oldest first.

No comments yet. Be the first to comment.

Proof claims

Proof claims are the responsibility of the submitter. Appearance here does not mean the claim has been checked for mathematical correctness. Moderators only screen for spam, abuse, and obviously low-effort submissions.

No proof claims yet.