

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.


0




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^22*k+1))/2 (Chen 2003);
if n <= 27, with the exception (n,k) = (5,2) (see Shields and Savage 2004);
if k >= 3 and n2*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

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, 912919.


FORMULA

T(n,1) = (n1)!/2 = A001710(n1) for n >= 3.
T(2*k+1,k) >= 2^2^(k6) 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



KEYWORD

nonn,tabf,more


AUTHOR



STATUS

approved



