Independent sets in the union of two Hamiltonian cycles (Q668015)

Summary: Motivated by a question on the maximal number of vertex disjoint Schrijver graphs in the Kneser graph, we investigate the following function, denoted by \(f(n,k)\): the maximal number of Hamiltonian cycles on an \(n\) element set, such that no two cycles share a common independent set of size more than \(k\). We shall mainly be interested in the behavior of \(f(n,k)\) when \(k\) is a linear function of \(n\), namely \(k=cn\). We show a threshold phenomenon: there exists a constant \(c_t\) such that for \(c<c_t\), \(f(n,cn)\) is bounded by a constant depending only on \(c\) and not on \(n\), and for \(c_t <c\), \(f(n,cn)\) is exponentially large in \(n (n \rightarrow \infty)\). We prove that \(0.26 < c_t < 0.36\), but the exact value of \(c_t\) is not determined. For the lower bound we prove a technical lemma, which for graphs that are the union of two Hamiltonian cycles establishes a relation between the independence number and the number of \(K_4\) subgraphs. A corollary of this lemma is that if a graph \(G\) on \(n>12\) vertices is the union of two Hamiltonian cycles and \(\alpha(G)=n/4\), then \(V(G)\) can be covered by vertex-disjoint \(K_4\) subgraphs.