6
$\begingroup$

Recall that a tournament is a directed graph $T$ such that for every pair of distinct vertices $\{v,w\}$, exactly one of the ordered pairs $(v,w)$, $(w,v)$ is an arc of $T$.

A tournament is strongly connected (or just strong) if for any ordered pair of vertices $(v,w)$, there is a directed path from $v$ to $w$.

A Hamilton path in a tournament is a directed path visiting every vertex exactly once, and several authors have considered questions about how many Hamilton paths a tournament on $n$ vertices might possess.

User @bof asked about the minimum number of Hamilton paths in a strong tournament in this question, and this question turned out to have an exact answer.

$$ h_{\min}(n) = \begin{cases} 3 \cdot \beta^{n-3}, & n \equiv 0 \pmod 3;\\ \beta^{n-1}, & n \equiv 1 \pmod 3;\\ 9 \cdot \beta^{n-5}, & n \equiv 2 \pmod 3. \end{cases} $$ where $\beta = \sqrt[3]{5}$.

(We need the adjective "strong" in the question about minimum numbers of Hamilton paths because otherwise the answer is always 1, achieved by the transitive tournament)

I would like to know if there is an exact formula for $h_{\max}(n)$.

What do I know?

I started by computing the numbers of Hamilton paths in the tournaments for smallish $n$, and then entered the values into the OEIS, and was rewarded with A038375 which told me that the sequence starts

1, 1, 3, 5, 15, 45, 189, 661, 3357, 15745

where 15745 is the maximum number of Hamilton paths among 10-vertex tournaments.

There are about 903 million 11-vertex tournaments, and so it was feasible to count their Hamilton paths and find the maximum for 11-vertex tournaments, which turns out to be 95095, which I then added to the sequence in the OEIS.

1, 1, 3, 5, 15, 45, 189, 661, 3357, 15745, 95095

Can we look at the extremal tournaments and try to say something sensible about them?

Well, for 11 vertices, we can say something very sensible indeed - the winner is the Cayley digraph $$ \mathrm{Cay}(\mathbb{Z}_{11}, \{1,3,4,5,9\}). $$ (Of course, $\{1,3,4,5,9\}$ is the set of squares in $\mathbb{Z}_{11}$ and so you may know this as the Paley (di)graph $P(11)$ or just Paley tournament.)

There is a unique tournament on 10 vertices with the maximum number of Hamilton paths, obtained by deleting a vertex from $P(11)$.

There is a unique 9-vertex winner, which is another circulant digraph, namely $$ \mathrm{Cay}(\mathbb{Z}_{9},\{1,2,3,5\}). $$

There are six 8-vertex tournaments with 661 Hamilton paths, one of which is obtained by deleting a vertex from the 9-vertex winner, and the others can all be obtained from this by reversing a couple of arcs.

Then the unique $7$-vertex winner is the Paley (di)graph $$ P_7 = \mathrm{Cay}(\mathbb{Z}_7,\{1,2,4\}). $$

It seems highly plausible that the Paley tournament will always have the maximum number of Hamilton paths whenever it exists, but merely being plausible is not enough.

I could only find some asymptotic / probabilistic work of Alon (and collaborators) on the maximum number of Hamilton paths in tournaments, but perhaps there is something I missed?

$\endgroup$
1
  • 1
    $\begingroup$ It is $f(n)n!/2^n$, where $f$ is at least constant and at most polynomial (see more details in Alon and Spencer's Probabilistic method), an exact formula in such questions is a rare luck, I doubt that it exists $\endgroup$ Commented Feb 4, 2022 at 7:36

0

You must log in to answer this question.

Browse other questions tagged .