New bounds on even cycle creating Hamiltonian paths using expander graphs

Harcos, Gergely and Soltész, Dániel (2020) New bounds on even cycle creating Hamiltonian paths using expander graphs. COMBINATORICA, 40. pp. 435-454. ISSN 0209-9683

Preview

Text 1904.pdf Download (253kB) | Preview

Abstract

We say that two graphs on the same vertex set are G-creating if their union (the union of their edges) contains G as a subgraph. Let Hn(G) be the maximum number of pairwise G-creating Hamiltonian paths of Kn. Cohen, Fachini and Körner proved n12n−o(n)≤Hn(C4)≤n34n+o(n). In this paper we close the superexponential gap between their lower and upper bounds by proving n12n−12nlogn−O(1)≤Hn(C4)≤n12n+o(nlogn). We also improve the previously established upper bounds on Hn(C2k) for k>3, and we present a small improvement on the lower bound of Füredi, Kantor, Monti and Sinaimeri on the maximum number of so-called pairwise reversing permutations. One of our main tools is a theorem of Krivelevich, which roughly states that (certain kinds of) good expanders contain many Hamiltonian paths.

Actions (login required)

Edit Item