---
_id: '14867'
abstract:
- lang: eng
  text: <jats:p>Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$
    edges is presented chosen uniformly at random from the ones that have not been
    presented yet. We are then asked to choose at most one of the presented edges
    and add it to the current graph. Our goal is to construct a Hamiltonian graph
    with $(1+o(1))n$ edges within as few rounds as possible. We show that in this
    process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\log
    n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian
    graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along
    the first $(0.5+o(1))n\log n$ rounds of the random graph process. This answers
    a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds
    is asymptotically optimal as the first $0.5n\log n$ edges do not span a Hamilton
    cycle w.h.p. The case $K=\Theta(\log n)$ implies that the Hamiltonicity threshold
    of the corresponding Achlioptas process is at most $(1+o(1))(1+(\log n)/2K) n$.
    This matches the $(1-o(1))(1+(\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky
    and Sudakov and resolves the problem of determining the Hamiltonicity threshold
    of the Achlioptas process with $K=\Theta(\log n)$. We also show that in the above
    process one can construct a graph $G$ that spans a matching of size $\lfloor V(G)/2)
    \rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\log n)/2K) n$ rounds w.h.p.
    Our proof relies on a robust Hamiltonicity property of the strong $4$-core of
    the binomial random graph which we use as a black-box. This property allows it
    to absorb paths covering vertices outside the strong $4$-core into a cycle.</jats:p>
acknowledgement: "This project has received funding from the European Union’s Horizon
  2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
  No 101034413.\r\n"
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
citation:
  ama: 'Anastos M. Constructing Hamilton cycles and perfect matchings efficiently.
    In: <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory
    and Applications</i>. Masaryk University Press; 2023:36-41. doi:<a href="https://doi.org/10.5817/cz.muni.eurocomb23-005">10.5817/cz.muni.eurocomb23-005</a>'
  apa: 'Anastos, M. (2023). Constructing Hamilton cycles and perfect matchings efficiently.
    In <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory
    and Applications</i> (pp. 36–41). Prague, Czech Republic: Masaryk University Press.
    <a href="https://doi.org/10.5817/cz.muni.eurocomb23-005">https://doi.org/10.5817/cz.muni.eurocomb23-005</a>'
  chicago: Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.”
    In <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory
    and Applications</i>, 36–41. Masaryk University Press, 2023. <a href="https://doi.org/10.5817/cz.muni.eurocomb23-005">https://doi.org/10.5817/cz.muni.eurocomb23-005</a>.
  ieee: M. Anastos, “Constructing Hamilton cycles and perfect matchings efficiently,”
    in <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory
    and Applications</i>, Prague, Czech Republic, 2023, pp. 36–41.
  ista: 'Anastos M. 2023. Constructing Hamilton cycles and perfect matchings efficiently.
    Proceedings of the 12th European Conference on Combinatorics, Graph Theory and
    Applications. EUROCOMB: European Conference on Combinatorics, Graph Theory and
    Applications, 36–41.'
  mla: Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.”
    <i>Proceedings of the 12th European Conference on Combinatorics, Graph Theory
    and Applications</i>, Masaryk University Press, 2023, pp. 36–41, doi:<a href="https://doi.org/10.5817/cz.muni.eurocomb23-005">10.5817/cz.muni.eurocomb23-005</a>.
  short: M. Anastos, in:, Proceedings of the 12th European Conference on Combinatorics,
    Graph Theory and Applications, Masaryk University Press, 2023, pp. 36–41.
conference:
  end_date: 2023-09-01
  location: Prague, Czech Republic
  name: 'EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications'
  start_date: 2023-08-28
corr_author: '1'
date_created: 2024-01-22T12:20:15Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2025-09-09T14:24:21Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.5817/cz.muni.eurocomb23-005
ec_funded: 1
external_id:
  arxiv:
  - '2209.09860'
  isi:
  - '001448447300005'
file:
- access_level: open_access
  checksum: fb1d9a1e7389d90ec0e5e76934373cf8
  content_type: application/pdf
  creator: dernst
  date_created: 2024-01-24T09:34:43Z
  date_updated: 2024-01-24T09:34:43Z
  file_id: '14881'
  file_name: 2023_Eurocomb_Anastos.pdf
  file_size: 464230
  relation: main_file
  success: 1
file_date_updated: 2024-01-24T09:34:43Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: 36-41
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
publication: Proceedings of the 12th European Conference on Combinatorics, Graph Theory
  and Applications
publication_identifier:
  eissn:
  - 2788-3116
publication_status: published
publisher: Masaryk University Press
quality_controlled: '1'
status: public
title: Constructing Hamilton cycles and perfect matchings efficiently
tmp:
  image: /images/cc_by_nc_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
    (CC BY-NC-ND 4.0)
  short: CC BY-NC-ND (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2023'
...