Search

An n-bit (cyclic) Gray code is a (cyclic) sequence of all n-bit strings such that consecutive strings differ in a single bit. We describe an algorithm which for every positive integer n constructs an n-bit cyclic Gray code whose graph of transitions is the d-dimensional hypercube Q d if n = 2 d , or a subgraph of Q d if 2 d ? 1 < n < 2 d . This allows to compress sequences that follow this code so that only ${\it \Theta}(\log\log n)$ bits per n-bit string are needed. The algorithm generates the transitional sequence of the code in a constant amortized time per one transition.

We consider the problem of constructing a cyclic listing of all bitstrings of length 2 n + 1 with Hamming weights in the interval [ n + 1 − l , n + l ] , where 1 ≤ l ≤ n + 1 , by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (the case l = 1 ). We provide a solution for the case l = 2 , and we solve a relaxed version of the problem for general values of l , by constructing cycle factors for those instances. The proof of the first result uses the lexical matchings introduced by Kierstead and Trotter, which we generalize to arbitrary consecutive levels of the hypercube . The proof of the second result uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets . We also present several new constructions of such decompositions based on lexical matchings. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-dimensional hypercube for any n ≥ 12 .

This study evaluated the environmental genotoxic load of mountain and alpine habitats of Slovak mountains caused by the total mixture of air pollutants at 69 sites using the phytoindicator Pinus mugo. The level of overall genotoxicity was determined by pollen grain abortion assay. This shows that the test is sensitive enough to detect contamination from more distant sources, including long-range transboundary pollutants. It extends the applicability of this test to mountain environments. Soil and plant samples (pollen, one-two year old needles) were collected during a three-year growing period (2011-2013). The study identified source regions of pollutants by assessments at different altitudes and slope exposures. The highest genotoxicity was found in the Little Fatra Mts. on Suchy Mt., with pollen abortivity 3.52 % which represented a 23.5 times higher genotoxic load than at the control site. Samples from mountain peaks showed a higher genotoxicity in 2012 than in 2011 on most mountains. A gradual increase of pollen abortivity and needle Pb content (one year old) with increasing altitude was found in the vertical transect in Belian Tatras. The influence of subsoil type was analysed; higher genotoxicity and Pb content in soil and needles were found on limestone subsoil (Sivy vrch Mt.) and higher values of needle Cd were on granite (Brestova Mt.). The highest Pb and Cd concentrations in needles were measured in the Great Fatra Mts. on Krizna Mt. situated between highly-industrialized areas. The other mountain ranges with the high loading by Pb, Cd were Chocske vrchy Mts. and Low Tatra Mts. The lead content increased with needle age, but the correlation between soil Pb and needle Pb was not confirmed. The positive correlation between soil Pb and abortivity was found only at mountain peaks. The results showed a significant impact of both local industrial and transboundary sources of pollutants. Based on the results, the studied Slovak mountains were not strongly burdened by Pb, Cd and an overall mixture of air pollutants. This methodological approach may contribute to the assessment of urban exposome by comparing the external exposure in urban environment of big cities with background - mountain areas, where the only possible source is long-range transport.