0
$\begingroup$

I've been looking at Kelly's conjecture that every regular tournament on $2n+1$ vertices can be decomposed into $n$ edge-disjoint Hamiltonian cycles. I'm aware that a proof has been given for large $n$, see here. Nevertheless, I've taken a shot at the problem from a different perspective (with no real hopes of achieving progress to be frank) and I've encountered an odd issue.

Let $G_{2n+1}$ be the graph constructed as follows. The vertices are the $(2n)!$ directed Hamiltonian cycles in $K_{2n+1}$, and two vertices are connected by an edge iff the two Hamiltonian cycles are edge-disjoint (regardless of orientation of the edges).

I claim that this graph has no $(n+1)$-cliques and that the number of $n$-cliques equals the number of labelled regular tournaments with $2n+1$ vertices. The correspondence between $n$-cliques and labelled regular tournaments which admit a decomposition into $n$ edge-disjoint Hamiltonian cycles is clear by the construction of $G_{2n+1}$. The claim is then equivalent to Kelly's conjecture, since this would create a bijection between (labelled) regular tournaments and regular tournaments that decompose into edge-disjoint Hamiltonian cycles.

Or so I thought. I computed the number of cliques for $G_5$ and $G_7$ and compared them to the first entries in this OEIS page counting the number of labelled regular tournaments. The number of $2$-cliques (edges) in $G_5$ is 24, which matches, but I get that the number of $3$-cliques (triangles) in $G_7$ is $7680$, which exceeds the number of labelled regular tournaments on $7$ vertices, namely $2640$. (Numerical note: it exceeds it by $5040 = 7!$).

I'll give a brief explanation for how I obtained $7680$ triangles in $G_7$ (perhaps I made a silly, easy mistake). The degree of a vertex $v$ equals the number of Hamiltonian cycles that are edge-disjoint with $v$ taking into consideration orientation. This number is twice what is given in the entries of this other OEIS sequence, so in $G_7$, each vertex has degree $46$.

Through painstakingly going through the possible Hamiltonian cycles that are edge-disjoint with a given fixed one, I've determined which vertices adjacent to $v$ have an edge between them. I count $32$ such edges, so there are $32$ triangles attached to $v$. The graph is symmetric with $720$ vertices, each triangle is counted three times when summed over all vertices, so there are $\frac{720 \times 32}{3} = 7680$ triangles in the graph.

So my question boils down to: what's going on here? How can I be counting more regular tournaments that decompose into edge-disjoint Hamiltonian cycles than labelled regular tournaments? Obviously I made a mistake somewhere. But even when trying to force the numbers to agree, I would need to get $11$ triangles per vertex to obtain $2640$ triangles in the graph, but my computation requires that there be an even number of triangles per vertex, since we're counting those Hamiltonian cycles with reversed orientation too.

Sorry for the very long post, I hope this makes sense.

$\endgroup$
7
  • 3
    $\begingroup$ I think the issue is that $n$-cliques of $G_{2n+1}$ are not in bijection with labelled regular tournaments on $2n+1$ vertices. Each $n$-clique corresponds to a particular way to decompose into Hamiltonian cycles, but a fixed regular tournament can be decomposed in more than one way. $\endgroup$
    – Tony Huynh
    Feb 21, 2023 at 3:21
  • $\begingroup$ @TonyHuynh Oh I didn't even consider that possibility, thanks for pointing this out! I'll look into this and see if I can determine the overcount given by the different ways the tournament can be decomposed $\endgroup$ Feb 21, 2023 at 3:26
  • 1
    $\begingroup$ 720 tournaments with a single decomposition; 1680 with three decompositions; 240 with eight decompositions. Data $\endgroup$ Feb 21, 2023 at 9:00
  • $\begingroup$ @PeterTaylor Thank you, this data is enlightening. Sorry for the late response, but is there any hope to produce similar data for labelled regular tournaments on 9 vertices? Or are there simply too many such graphs? $\endgroup$ Mar 11, 2023 at 1:08
  • 1
    $\begingroup$ I get 640604160 4-cliques. The frequency distribution among the tournaments is quite messy. 40320 tournaments with 144 decompositions each; 120960 with 152; 4480 with 162; 120960 with 180; 362880 with 182; 120960 with 186; 362880 with 188; 362880 with 190; 362880 with 194; 483840 with 206; 362880 with 208; 362880 with 218; 120960 with 264; 40320 with 288. Python code $\endgroup$ Mar 31, 2023 at 8:19

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.