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?

$\endgroup$
  • $\begingroup$ do you require your tournaments to be finite? $\endgroup$ – Dima Pasechnik Apr 29 at 21:20
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.

$\endgroup$
  • $\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 Apr 30 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 Apr 30 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 May 1 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.