1
$\begingroup$

Does every tournament on $\omega$ contain an infinite directed path that doesn't visit any vertex twice?

$\endgroup$

1 Answer 1

2
$\begingroup$

If $x\to y\to z\ldots$ and $x\leftarrow y\leftarrow z\leftarrow\dots$ are both called infinite paths, then yes. For two vertices $x<y$ color an edge $xy$ of the complete graph on $\omega$ red or blue in dependence of the direction of $xy$ in the tournament. By infinite Ramsey theorem, there exists an infinite monochromatic subgraph which contains an infinite path.

If $x\leftarrow y\leftarrow z\leftarrow\dots$ is not called an infinite path, then no: consider the tournament in which all edges are directed towards lesser number.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .