4
$\begingroup$

Is it true that every finite tournament is contained in some finite vertex-transitive tournament? If not, is it known which tournaments satisfy this property? This seems like a basic question, but I have not been able to find a relevant reference.

In a comment @bof claims that every finite tournament is contained in some finite cyclic tournament. Why is that?

Improve this question
$\endgroup$
1
  • $\begingroup$ do you require your tournaments to be finite? $\endgroup$
    – Dima Pasechnik
    Commented Apr 29, 2019 at 21:20

2 Answers 2

Reset to default
3
$\begingroup$

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any odd (per bof) $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes. As bof notes in comment this is not so.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.

Improve this answer
$\endgroup$
3
  • $\begingroup$ My answer is also about finite tournaments, but it asks for more, namely the property that all partially defined automorphisms can be extended. The resulting tournament would be also edge-transitive etc. $\endgroup$
    – Andreas Thom
    Commented Apr 30, 2019 at 8:23
  • $\begingroup$ I don't know anything about uncountable tournaments, but your construction seems to work fine in the countable case. In fact there is one vertex-transitive countable tournament which contains a copy of every countable tournament. Namely, the random countable tournament contains a copy of every countable tournament, so it suffices to embed the random tournament in an "infinite cyclic tournament". $\endgroup$
    – bof
    Commented Apr 30, 2019 at 21:53
  • 1
    $\begingroup$ In this construction, you can take $N=O(n^2)$, see e.g. en.wikipedia.org/wiki/… . $\endgroup$
    – Emil Jeřábek
    Commented May 1, 2019 at 11:35
2
$\begingroup$

It was shown in [Bernhard Herwig and Daniel Lascar, Extending partial automorphisms and the profinite topology on free groups, Trans. Amer. Math. Soc. 352 (2000), 1985-2021] that every finite tournament is contained in a finite tournament with the extension property for partial automorphisms if and only a certain question about the profinite topology of the free group has a positive answer. The questions asks if it is equivalent that a finitely generated subgroup $H$ of a free group is closed in the odd-topology (arising from all quotients of odd order) and that the implication $a^2 \in H \Rightarrow a \in H$ holds.

In particular, this (slightly stronger assertion than just vertex transitivity) is an open problem.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ it looks much stronger assertion than vertex transitivity (to say the least, it implies the edge transitivity, yes?) $\endgroup$
    – Fedor Petrov
    Commented May 1, 2019 at 2:55

You must log in to answer this question.

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