Il primo amore non si scorda mai or an up-to-date survey of small embeddings for partial even-cycle systems (Q1402882)

In this paper the author is aiming at an up-to-date survey of small embeddings for partial even-cycle systems. A 4-cycle system of order \(n\) is a pair \((S,C)\), where \(C\) is a collection of edge disjoint 4-cycles which partitions the edge set of the complete undirected graph \(K_n\) with vertex set \(S\). It is well known that the spectrum for 4-cycle systems (that is the set of all \(n\) such that a 4-cycle system of order \(n\) exists) is precisely the set of all \(n\equiv 1\pmod 8\) and that if \((S,C)\) is a 4-cycle system of order \(n\) then \(|C|= n(n- 1)/8\). A partial 4-cycle system of order \(n\) is a pair \((X, P)\), where \(P\) is a collection of edge disjoint 4-cycles of the edge set of \(K_n\) with vertex set \(X\). The difference between a complete 4-cycle system and a partial 4-cycle system is that the edge disjoint 4-cycles belonging to a partial 4-cycle system do not necessarily contain all the edges of \(K_n\). The partial 4-cycle system \((X,P)\) is said to be embedded in the complete 4-cycle systems \((S,C)\) provided \(X\subseteq S\) and \(P\subseteq C\). As an example, a partial 4-cycle system of order 7 can be embedded in the 4-cycle system of order 9, which cannot be true in general. Hence the problem of whether or not a partial 4-cycle system can always be embedded in another 4-cycle system. In general, for the spectrum of an \(m\)-cycle system as well as an embedding (as small as possible) for a partial \(m\)-cycle system, we can pose the same question: Does there exist an algorithm which will produce for any partial 4-cycle system \((X,P)\) a 4-cycle system \((S,C)\) such that \(X\subseteq S\) and \(P\subseteq C\), which should be the smallest systems? The best possible bound is approximately \(n+\sqrt{n}\). And then the general problem of finding an algorithm which will embed a partial \(m\)-cycle system in an \(m\)-cycle system, which should be as small as possible. Much work has been done on this problem for both odd- and even-cycle lengths. For further details concerning odd cycles, refer to the author [6]. In fact the bounds mentioned in this paper are the best-known bounds to date for odd-cycle systems. Regarding even-cycle system of order \(n\), it has been improved by Wilson. Some more results, namely a partial \(2k\)-cycle system of order at most \(k_n+ d(k)\), where \(d(k)\) is a function of \(k\), are also discussed. Thus the object of this paper is mainly an attempt at popularizing embedding problems for partial cycle systems.