A354568 Irregular triangle read by rows: T(n,k) is the number of Hamiltonian cycles in the Kneser graph K(n,k), 1 <= k < n/2.

1, 3, 12, 0, 60, 155328

Offset

3,2

Comments

It has been conjectured that T(n,k) > 0 (i.e., that K(n,k) is Hamiltonian) for all 1 <= k < n/2, with the exception (n,k) = (5,2) (the Petersen graph). See Lovász 1970 for a more general conjecture.

It is known that T(n,k) > 0 in the following cases:

if n >= (3*k+1+sqrt(5*k^2-2*k+1))/2 (Chen 2003);

if n <= 27, with the exception (n,k) = (5,2) (see Shields and Savage 2004);

if k >= 3 and n-2*k is a power of 2 (Mütze, Nummenpalo, and Walczak 2018).

References

László Lovász, Problem 11 in: Richard K. Guy (editor), Combinatorial Structures and Their Applications, Gordon and Breach 1970.

Links

Table of n, a(n) for n=3..8.

Ya-Chen Chen, Triangle-free Hamiltonian Kneser graphs, Journal of Combinatorial Theory, Series B 89 (2003), 1-16.

Torsten Mütze, Jerri Nummenpalo, and Bartosz Walczak, Sparse Kneser graphs are Hamiltonian, STOC'18 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing 2018, 912-919.

Ian Shields and Carla D. Savage, A note on Hamilton cycles in Kneser graphs, Bulletin of the Institute of Combinatorics and Its Applications 40 (2004), 13-22.

Wikipedia, Kneser graph.

Formula

T(n,1) = (n-1)!/2 = A001710(n-1) for n >= 3.

T(2*k+1,k) >= 2^2^(k-6) for k >= 6. (Mütze, Nummenpalo, and Walczak 2018).

Example

Triangle begins:
  n\k|  1      2
  ---+----------
  3  |  1
  4  |  3
  5  | 12      0
  6  | 60 155328

Crossrefs

Cf. A001710, A301560.

Sequence in context: A101710 A088799 A181405 * A072117 A162853 A162854

Adjacent sequences: A354565 A354566 A354567 * A354569 A354570 A354571

Keyword

nonn,tabf,more

Author

Pontus von Brömssen, Aug 18 2022

Status

approved