For integers k≥1 and n≥2k+1, the Kneser graph K(n,k) is the graph whose vertices are the k-element subsets of {1,…,n} and whose edges connect pairs of subsets that are disjoint. The Kneser graphs of the form K(2k+1,k) are also known as the odd graphs. We settle an old problem due to Meredith, Lloyd, and Biggs from the 1970s, proving that for every k≥3, the odd graph K(2k+1,k) has a Hamilton cycle. This and a known conditional result due to Johnson imply that all Kneser graphs of the form K(2k+2a,k) with k≥3 and a≥0 have a Hamilton cycle. We also prove that K(2k+1,k) has at least 22k−6 distinct Hamilton cycles for k≥6. Our proofs are based on a reduction of the Hamiltonicity problem in the odd graph to the problem of finding a spanning tree in a suitably defined hypergraph on Dyck words.

For any integer n ≥ 1, a middle levels Gray code is a cyclic listing of all bitstrings of length 2 n +1 that have either n or n +1 entries equal to 1 such that any two consecutive bitstrings in the list differ in exactly one bit. The question whether such a Gray code exists for every n ≥ 1 has been the subject of intensive research during the past 30 years and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. Proc. London Math. Soc. , 112(4):677--713, 2016]. In this work, we provide the first efficient algorithm to compute a middle levels Gray code. For a given bitstring, our algorithm computes the next ℓ bitstrings in the Gray code in time O ( n ℓ (1+ n /ℓ)), which is O ( n ) on average per bitstring provided that ℓ = Ω ( n ).

We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time O^*(eps^{-0.617}) where eps is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected Theta^*(eps^{-1}), and on all previous algorithms whenever eps = Omega(0.708^n). We also consider algorithms for 3-SAT with an eps fraction of satisfying assignments, and prove that it can be solved in O^*(eps^{-2.27}) deterministic time, and in O^*(eps^{-0.936}) randomized time. Finally, to further demonstrate the applicability of this framework, we also explore how similar techniques can be used for vertex cover problems.

For any integer n ≥ 1 a middle levels Gray code is a cyclic listing of all n-element and (n + 1)- element subsets of {1,2,…, 2n +1} such that any two consecutive subsets differ in adding or removing a single element. The question whether such a Gray code exists for any n ≥ 1 has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T. Mütze. Proof of the middle levels conjecture. To appear in Proc. London Math. Soc., 2014]. In a follow-up paper [T. Mütze and J. Nummenpalo. An efficient algorithm for computing a middle levels Gray code. Proc. ESA, 2015] this existence proof was turned into an algorithm that computes each new set in the Gray code in time O(n) on average. In this work we complete this line of research by presenting an algorithm for computing a middle levels Gray code in optimal time and space: Each new set is generated in time O(1), and the required space is O(n).