zbMATH — the first resource for mathematics

Perfect Skolem sets. (English) Zbl 1135.05002
Summary: A Skolem sequence is a sequence \(s_{1},s_{2},\dots ,s_{2n}\) (where \(s_i\in A=\{1,\dots ,n\}\)), each \(s_i\) occurs exactly twice in the sequence and the two occurrences are exactly \(s_i\) positions apart. A set \(A\) that can be used to construct Skolem sequences is called a Skolem set. The problem of deciding which sets of the form \(A=\{ 1 ,\dots ,n\}\) are Skolem sets was solved by Thoralf Skolem in the late 1950s. We study the natural generalization where \(A\) is allowed to be any set of \(n\) positive integers. We give necessary conditions for the existence of Skolem sets of this generalized form. We conjecture these necessary conditions to be sufficient, and give computational evidence in favor of our conjecture. We investigate special cases of the conjecture and prove that the conjecture holds for some of them. We also study enumerative questions and show that this problem has strong connections with problems related to permutation displacements.

05A05 Permutations, words, matrices
05A15 Exact enumeration problems, generating functions
11B83 Special sequences and polynomials
PDF BibTeX Cite
Full Text: DOI arXiv
[1] Baker, C.A., Extended Skolem sequences, J. combin. des., 3, 363-379, (1995) · Zbl 0885.05040
[2] Baker, C.A.; Nowakowski, R.J.; Shalaby, N.; Sharary, A., m-fold and extended m-fold Skolem sequences, Utilitas math., 45, 153-167, (1994) · Zbl 0808.05001
[3] Bebeacua, C.; Mansour, T.; Postnikov, A.; Severini, S., On the X-rays of permutations, Electron notes discrete math., 20, 193-203, (2005) · Zbl 1179.05003
[4] J.C. Bermond, A.E. Brouwer, A. Germa, Systémes de triplets et differences associées, in: Colloquium CRNS, Problémes combinatoires et théorie des graphes, Orsay, 1976.
[5] Habbas, Z.; Krajecki, M.; Singer, D., The Langford’s problem: a challenge for parallel resolution of csp, (), 789-796 · Zbl 1057.68686
[6] Langford, D., Problem, Math. gaz., 42, 228, (1958)
[7] Lehmer, D.H., Permutations with strongly restricted displacements, (), 755-770 · Zbl 0225.05009
[8] Linek, V., Note concerning an odd langford sequence, European J. combin., 22, 1, 79-83, (2001) · Zbl 1008.05026
[9] J. Miller, Langford’s problem, \(\langle\)http://www.lclark.edu/\(\sim\)miller/langford.html⟩, 2005.
[10] G. Nordh, Generalization of Skolem sequences, Master’s Thesis, Department of Mathematics, Linköpings Universitet, Sweden, 2003.
[11] Priday, C.J., On Langford’s problem, Math. gaz., 43, 250-253, (1959) · Zbl 0107.24904
[12] Shalaby, N., The existence of near-Skolem and hooked near-Skolem sequences, Discrete math., 135, 303-319, (1994) · Zbl 0818.05008
[13] Shalaby, N., Skolem sequences, the CRC handbook of combinatorial designs, (1995), CRC Press Boca Raton, FL
[14] Simpson, J.E., Langford sequences: perfect and hooked, Discrete math., 44, 97-104, (1983) · Zbl 0514.05007
[15] Skolem, T., On certain distributions of integers in pairs with given differences, Math. scand, 5, 57-68, (1987) · Zbl 0084.04304
[16] R.P. Stanley, Enumerative Combinatorics, vol. 1. Cambridge University Press, New York, 1986.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.