The perfect 1-factorisation conjecture holds asymptotically
A famous conjecture of Anton Kotzig states that for every even integer $n\ge 4$, the complete graph $K_n$ of order $n$ can be decomposed into $n - 1$ perfect matchings such that every pair of these matchings forms a Hamilton cycle. Despite the great interest, the conjecture is far from being solved. Here we show that the conjecture holds asymptotically, namely that $K_n$ can be decomposed into $n-1$ perfect matchings such that $(1-o(1))n$ of them have the property that any pair forms a Hamilton cycle.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.09459
curl -X POST /api/v1/records/arxiv/2607.09459/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.09459/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'