{
  "abstract": "A family of perfect matchings on the same vertex set is said to have the Kotzig property if the union of any pair of matchings forms a Hamilton cycle. Kotzig famously conjectured that, when $n$ is even, the complete graph on $n$ vertices can be decomposed into $n-1$ perfect matchings with the Kotzig property. A closely related conjecture of Wormald states that, for fixed $d \\ge 3$, whp a random $d$-regular graph contains $d$ perfect matchings with the Kotzig property. Recently, the first and third authors considered a version of these problems for the binomial random graph $G(n,p)$ and proved that, for every fixed $k$, there is $C=C(k)$ such that whp $G(n,C\\log n/n)$ contains $k$ perfect matchings with the Kotzig property. We strengthen this result by showing a hitting time version: for every fixed $k$, whp the hitting time in the random graph process for finding $k$ edge-disjoint perfect matchings with the Kotzig property is the same as the hitting time for a graph with minimum degree $k$. This is a generalisation of the celebrated result of Bollobás and Frieze for even $n$ establishing the hitting time for $k$ edge-disjoint Hamilton cycles. The proof uses several ideas. We first design a coupling, via a randomised algorithm, of the random graph at the hitting time with $k$ almost-independent perfect matchings and a set of random reservoir edges, which may be of independent interest. We then prove various statistical properties of these matchings, in particular concerning the cycle structure of the $2$-factors formed by pairs of matchings. This includes a novel concept of ``shuffledness'', which we establish through a careful exposure argument and a concentration inequality for random permutations. Finally, we show that the initial $2$-factors can be merged into Hamilton cycles, using the random reservoir edges, by analysing certain Pósa-type rotations via branching processes.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2611.02128",
  "author_total": 3,
  "authors": [
    {
      "name": "Stefan Glock"
    },
    {
      "name": "Lyuben Lichev"
    },
    {
      "name": "Amedeo Sgueglia"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/0f46326kps7ej.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2611.02128",
  "fulltext_url": null,
  "id": "0f46326kps7ej",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2611.02128",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.CO"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://arxiv.org/pdf/2611.02128",
  "pmcid": null,
  "pmid": null,
  "published": "2026-11-01",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/0f46326kps7ej.ris",
  "sources": [
    {
      "first_seen": "2026-11-03T12:21:10Z",
      "native_id": "2611.02128",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2611.02128"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    }
  ],
  "title": "A hitting-time version of Kotzig's conjecture in random graphs",
  "title_text": "A hitting-time version of Kotzig's conjecture in random graphs",
  "type": "preprint",
  "updated_at": "2026-11-05T15:20:22Z",
  "url": "https://research.draconitic.com/paper/0f46326kps7ej",
  "venue": "arXiv",
  "versions": []
}