Abstract We consider the algorithmic problem of generating each subset of [ n ] : = 1 , 2 , … , n whose size is in some interval [ k , l ] , 0 ≤ k ≤ l ≤ n , exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k = 0 and l = n this is the classical problem of generating all 2 n subsets of [ n ] by element additions removals, and for k = l this is the classical problem of generating all ( n k ) subsets of [ n ] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n , k , and l , improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant O ( 1 ) time per generated set and O ( n ) space. Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n -dimensional cube Q n induced by all levels [ k , l ] . We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q 2 k + 1 induced by all levels [ k − c , k + 1 + c ] , c ∈ 0 , 1 , … , k , has a Hamilton cycle. We also prove an approximate version of this generalized conjecture, showing that this graph has a cycle that visits a ( 1 − o ( 1 ) ) -fraction of all vertices.
In @cite_35 an algorithm is presented that generates the vertices of @math for an arbitrary interval @math such that any two consecutive vertices have Hamming distance 1 or 2, where the value 2 appears only between vertices on level @math and @math , but the Hamming distance between the first and last vertex is arbitrary, possibly @math . The running time of that algorithm is @math per generated vertex. In addition, this paper presents a loopless algorithm, achieving @math time per generated vertex, to generate all vertices in @math level by level, using only distance-2 steps in each level. In particular, these enumerations are not cycles in @math , and they are not tight.
@cite_35
2109410667
In this paper, we consider a popular randomized broadcasting algorithm called push-algorithm defined as follows. Initially, one vertex of a graph G=(V,E) owns a piece of information which is spread iteratively to all other vertices: in each timestep t=1,2, every informed vertex chooses a neighbor uniformly at random and informs it. The question is how many time steps are required until all vertices become informed (with high probability). For various graph classes, involved methods have been developed in order to show an upper bound of @math on the runtime of the push-algorithm, where N is the number of vertices and @math denotes the diameter of G. However, no asymptotically tight bound on the runtime based on the mixing time of random walks has been established. In this work we fill this gap by deriving an upper bound of @math , where @math denotes the mixing time of a certain random walk on G. After that we prove upper bounds that are based on certain edge expansion properties of G. However, for hypercubes neither the bound based on the mixing time nor the bounds based on edge expansion properties are tight. That is why we develop a general way to combine these two approaches by which we can deduce that the runtime of the push-algorithm is (log N) on every Hamming graph.