A354568 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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