Leírás
Let $H_1,H_2$ be undirected gaphs on the same vertex set, and $G$ a (smaller graph). We say that $H_1$ and $H_2$ are $G$-creating if their union (the union of their edges) contains $G$ as a subgraph. Let $H_n(C_k)$ be the maximum number of pairwise $C_k$-creating Hamiltonian paths of the complete graph $H_n$. In a previous talk the exact value of $H_n(C_3)$ was determined for all $n$. In a (different) previous talk the behavior of $H_n(C_{2k+1})$ was discussed, and its value was asymptotically determined if $2k$ is a power of two. The behavior of $H_n(C_{2k})$ was much less understood, for the first non-trivial case, $H_n(C_4)$, Cohen, Fachini and Körner proved
$$n^{n/2-o(n)} \leq H_n(C_4) \leq n^{3n/4+o(n)}. $$
In this talk we improve their upper bound to $H_n(C_4) \leq n^{n/2+o(n)}$ closing the superexponential gap. We discuss the implications of this method for $H_n(C_{2k})$ and if time permits we discuss connections between the value of $H_n(C_4)$ and the so-called reversing permutations conjecture.