Explicit matchings in the middle levels of the Boolean lattice (Q1117950): Difference between revisions

In the Hasse diagram of the Boolean lattice formed by the subsets of a given set with \(2k+1\) elements (k\(\geq 1)\) the vertices in the levels k and \(k+1\) are generating a bipartite induced subgraph denoted by B(k); the vertices in the k-th level together with an edge-set consisting of all unordered pairs of vertices the corresponding subsets are disjoint form a graph 0(k). There is constructed a new class of matchings in B(k) called i-lexical matchings, \(i=0,1,...,k\), with respect to a fixed ordering of the base set \(\{1,...,2k+1\}\). The special case \(i=0\) yields the lexicographical matchings already known. It is shown that for \(k=2i>0\) any i-lexical matching in B(k) can be lowered to a matching in 0(k); therefore, explicit matchings in 0(k) for even k are obtained. Furthermore, there is considered the effect of changing the underlying ordering of the base set, and the notion of i-lexical matching is extended to make it independent of the ordering chosen. At last, the number of i-lexical matchings in B(k) is determined for every i, \(0\leq i\leq k/2\). - This paper is a contribution to the efforts which try to prove \textit{I. Havel}'s conjecture [cf. Graphs and other combinatorial topics, Proc. 3rd Czech. Symp., Prague 1982, Teubner-Texte Math. 59, 101- 108 (1983; Zbl 0528.05030)], i.e. that B(k) is Hamiltonian for every k, by finding a pair of matchings the union of which is a Hamiltonian cycle.