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 $H_n(G)$ be the maximum number of pairwise $G$-creating Hamiltonian paths of $K_n$. Cohen, Fachini and K\"orner proved \[n^{ \frac{ 1}{ 2}n-o(n)}\leq H_n(C_4) \leq n^{ \frac{ 3}{ 4}n+o(n)}.\] In this paper we close the superexponential gap between their lower and upper bounds by proving \[n^{ \frac{ 1}{ 2}n-\frac{ 1}{ 2}\frac{ n}{ \log{ n}}-O(1)}\leq H_n(C_4) \leq n^{ \frac{ 1}{ 2}n+o\left(\frac{ n}{ \log{ n}} \right)}.\] We also improve the previously established upper bounds on $H_n(C_{ 2k})$ for $k>3$, and we present a small improvement on the lower bound of F\"uredi, 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.
Categories: math.CO math.NT