REAL

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

[img]
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.

Item Type: Article
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 12 Mar 2021 08:51
Last Modified: 25 Apr 2023 09:35
URI: http://real.mtak.hu/id/eprint/122160

Actions (login required)

Edit Item Edit Item