An algorithmic Friedman-Pippenger theorem on tree embeddings and applications

An (n, d)-expander is a graph G = (V, E) such that for every X subset of V with vertical bar X vertical bar <= 2n - 2 we have vertical bar Gamma(G)(X) vertical bar >= (d + 1) vertical bar X vertical bar. A tree T is small if it has at most n vertices and has maximum degree at most d. Friedman and Pippenger (1987) proved that any ( n; d)- expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this paper, we give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs G of (N, D, lambda)-graphs Lambda, as long as G contains a positive fraction of the edges of Lambda and lambda/D is small enough. In several applications of the Friedman-Pippenger theorem, including the ones in the original paper of those authors, the (n, d)-expander G is a subgraph of an (N, D, lambda)-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. As an example, we discuss a recent result of Alon, Krivelevich, and Sudakov (2007) concerning embedding nearly spanning bounded degree trees, the proof of which makes use of the Friedman-Pippenger theorem. We shall also show a construction inspired on Wigderson-Zuckerman expander graphs for which any sufficiently dense subgraph contains all trees of sizes and maximum degrees achieving essentially optimal parameters. Our algorithmic approach is based on a reduction of the tree embedding problem to a certain on-line matching problem for bipartite graphs, solved by Aggarwal et al. (1996).

Wavelet analysis of MODIS time series to detect expansion and intensification of row-crop agriculture in Brazil

Since 2000, the southwestern Brazilian Amazon has undergone a rapid transformation from natural vegetation and pastures to row-crop agricultural with the potential to affect regional biogeochemistry. The goals of this research are to assess wavelet algorithms applied to MODIS time series to determine expansion of row-crops and intensification of the number of crops grown. MODIS provides data from February 2000 to present, a period of agricultural expansion and intensification in the southwestern Brazilian Amazon. We have selected a study area near Comodoro, Mato Grosso because of the rapid growth of row-crop agriculture and availability of ground truth data of agricultural land-use history. We used a 90% power wavelet transform to create a wavelet-smoothed time series for five years of MODIS EVI data. From this wavelet-smoothed time series we determine characteristic phenology of single and double crops. We estimate that over 3200 km(2) were converted from native vegetation and pasture to row-crop agriculture from 2000 to 2005 in our study area encompassing 40,000 km(2). We observe an increase of 2000 km(2) of agricultural intensification, where areas of single crops were converted to double crops during the study period. (C) 2007 Elsevier Inc. All rights reserved.