Search

We prove that the number of symmetric chain decompositions of the Boolean lattice 2^{[n]} is \begin{equation*} \left (\frac {n}{2e}+o(n)\right)^{2^n}. \end{equation*} Furthermore, the number of symmetric chain decompositions of the hypergrid [t]^n is \begin{equation*} n^{(1-o_n(1))\cdot t^n}. \end{equation*} [ABSTRACT FROM AUTHOR]

In 1979, Shearer and Kleitman conjectured the existence of [n/2] + 1 orthogonal chain decompositions of the hypercube poset Qn and constructed two orthogonal chain decompositions. In this paper, we make the first nontrivial progress on this conjecture by constructing three orthogonal chain decompositions of Qn for all n ≥ 4 with the possible exceptions n = 9,11,13, 23. To do this, we introduce the notion of "almost orthogonal symmetric chain decompositions." We explicitly describe three such decompositions of Q5 and Q7 and describe conditions which allow us to decompose products of hypercube posets into k almost orthogonal symmetric chain decompositions given such decompositions of the original hypercube posets. [ABSTRACT FROM AUTHOR]

Research on space efficient graph algorithms, particularly for st-connectivity, has a long history including the celebrated polynomial time, O(lg n) bits1 algorithm in undirected graphs by Reingold J. JACM. 55(4) (2008), and polynomial time, n/2Θ(lgn) bits algorithm in directed graphs by Barnes et al. SICOMP. 27(5), 1273-1282 (1998). Recent works by Asano et al. ISAAC (2014) and Elmasry et al. STACS (2015), reconsidered classical fundamental graph algorithms focusing on improving the space complexity. Elmasry et al. gave, among others, an implementation of breadth first search (BFS) in a graph G with n vertices and m edges, taking the optimal O(m + n) time using O(n) bits improving the naïve O(n lg n) bits implementation. Similarly, Asano et al. provided space efficient implementations for performing depth first search (DFS) in a graph G. We continue this line of work focusing on improving the space requirement for implementing a few classical graph algorithms. Our first result is a simple data structure that can maintain any subset S of a universe of u elements using just u + o(u) bits and supports in constant time, apart from the standard insert, delete and membership queries, the operation findany that finds and returns any element of the set (or outputs that the set is empty). It can also enumerate all elements present currently in the set in no particular order in O(k + 1) time where k is the number of elements currently belonging to the set. While this data structure supports a weaker set of operations than that of Elmasry et al. STACS (2015), it is simple, more space efficient and is sufficient to support a BFS implementation optimally in O(m + n) time using at most 2n + o(n) bits. Later, we further improve the space requirement of BFS to at most n lg 3 + o(n) bits albeit with a slight increase in running time to O(m lg nf(n)) time where f(n) is any extremely slow growing function of n, and the o term in the space is a function of f(n). We also discuss a similar time-space tradeoff result for finding a minimum weight spanning tree of a weighted (bounded by polynomial in n) undirected graph using n + O(n/f(n)) bits and O(m lg nf(n)) time, for any function f(n) such that 1 ≤ f(n) ≤ n. For DFS in a graph G, we provide an implementation taking O(m + n) time and O(n lg m/n) bits. This partially answers at least for sparse graphs, a question asked by Asano et al. ISAAC (2014) whether DFS can be performed in O (m + n) time and using O(n) bits, and also simultaneously improves the DFS result of Elmasry et al. STACS (2015). Using our DFS algorithm and other careful implementations, we show how one can also test for biconnectivity, 2-edge connectivity, and find cut vertices and bridges of a given undirected graph within the same time and space bounds; earlier classical linear time algorithms for these problems used Ω(n lg n) bits of space. [ABSTRACT FROM AUTHOR]

This study analyses the changes in energy-related carbon dioxide (CO 2 ) emissions of the agricultural sector in China from 2005 to 2013. Using the logarithmic mean Divisia index (LMDI) decomposition method, this study attributes the changes in agricultural CO 2 emissions to agricultural CO 2 emissions intensity, agricultural productive income intensity, rural residents’ income structure, the distribution pattern of residential income, the distribution pattern of national income, economic development, provincial population distribution, and population scale, and treats these factors as technology, distribution, and population effects. Based on this, the nested decomposition problem, which has not been mentioned in related studies, is solved. To emphasize the importance of the logarithmic mean weight functions, two different chain LMDI decomposition methods are developed that are based on differences in the logarithmic mean weight functions. The results show that the distribution pattern of national income and rural residents’ income structure are two key factors that separately stimulate and suppress the changes in China's agricultural energy-related CO 2 emissions. After nested decomposition of the distribution pattern of residential income, the suppressing influence from the rural population proportion is stronger than the stimulating influence from rural-urban income inequity. Although the results of the two chain LMDI decomposition methods are similar, only the distribution pattern of national income and rural residents’ income structure maintain positive impacts on the changes in China's agricultural CO 2 emissions by year, while the rural residents’ income structure, distribution pattern of residential income, and rural population proportion continue to have negative impacts on changes in China's agricultural CO 2 emissions by year. Furthermore, the technology, distribution, and population effects could not suppress China's agricultural CO 2 emissions simultaneously in most years. [ABSTRACT FROM AUTHOR]

We extend the study on shadowable points recently introduced by Morales in relation to chaotic or non-chaotic properties. Firstly, some sufficient conditions for a quantitative shadowable point to be approximated by an entropy point are given. As a corollary, we get different three chaotic conditions from which a shadowable point becomes an entropy point. Secondly, we provide a dichotomy on the interior of the set of shadowable chain recurrent points by two canonical chaotic and non-chaotic dynamics, the full shift and odometers. [ABSTRACT FROM AUTHOR]

Thermal decomposition of cellulose can be upgraded by means of an electron-beam irradiation to produce valuable organic products via chain mechanisms. The samples being irradiated decompose effectively at temperatures below the threshold of pyrolysis inception. Cellulose decomposition resembles local "explosion" of the glucopyranose unit when fast elimination of carbon dioxide and water precede formation of residual carbonyl or carboxyl compounds. The dry distillation being performed during an irradiation gives a liquid condensate where furfural and its derivatives are dominant components. Excessively fast heating is adverse, as it results in a decrease of the yield of key organic products because pyrolysis predominates over the radiolytic-controlled decomposition of feedstock. Most likely, conversion of cellulose starts via radiolytic formation of macroradicals do not conform with each other, resulting in instability of the macroradical. As a consequence, glucosidic bond cleavage, elimination of light fragments (water, carbon oxides, formaldehyde, etc.) and formation of furfural take place. [ABSTRACT FROM AUTHOR]

Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an O(∣V∣²) algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an O(∣V∣³) algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs. [ABSTRACT FROM AUTHOR]

In this paper we give a decomposition of a 4-connected graph G into nonseparating chains, which is similar to an ear decomposition of a 2-connected graph. We also give an O(∣V (G)∣2∣E(G)∣) algorithm that constructs such a decomposition. In applications, the asymptotic performance can often be improved to O(∣V (G)∣3). This decomposition will be used to find four independent spanning trees in a 4-connected graph. [ABSTRACT FROM AUTHOR]