Metraipolis › archive › dc_c4a4e2bbcbbc

A hitting-time version of Kotzig's conjecture in random graphs — arXiv:2611.02128

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.02128
License (as archived): CC0-1.0
Archived: 2026-11-03T18:50:34.694Z
SHA-256 of the archived text: 220cafc6b42fb4f543a765c49f370baa8d3a0fed1ae35dc709187bdec81b0d68
Stable URL of this page: https://metraipolis.com/documento/dc_c4a4e2bbcbbc

How to cite

A hitting-time version of Kotzig's conjecture in random graphs — arXiv:2611.02128 — arXiv (en), https://arxiv.org/abs/2611.02128 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c4a4e2bbcbbc (Metraipolis archive dc_c4a4e2bbcbbc, sha256 220cafc6b42fb4f543a765c49f370baa8d3a0fed1ae35dc709187bdec81b0d68)

BibTeX

@misc{dcc4a4e2bbcbbc,
  title = {A hitting-time version of Kotzig's conjecture in random graphs — arXiv:2611.02128},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.02128},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c4a4e2bbcbbc; sha256 220cafc6b42fb4f543a765c49f370baa8d3a0fed1ae35dc709187bdec81b0d68},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02128. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.02128 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:15:38.090Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).