Order of arrival structures arbuscular mycorrhizal colonization of plants.

Priority effects - the impact of a species' arrival on subsequent community development - have been shown to influence species composition in many organisms. Whether priority effects among arbuscular mycorrhizal fungi (AMF) structure fungal root communities is not well understood. Here, we investigated whether priority effects influence the success of two closely related AMF species (Rhizophagus irregularis and Glomus aggregatum), hypothesizing that a resident AMF suppresses invader success, this effect is time-dependent and a resident will experience reduced growth when invaded. We performed two glasshouse experiments using modified pots, which permitted direct inoculation of resident and invading AMF on the roots. We quantified intraradical AMF abundances using quantitative PCR and visual colonization percentages. We found that both fungi suppressed the invading species and that this effect was strongly dependent on the time lag between inoculations. In contrast to our expectations, neither resident AMF was negatively affected by invasion. We show that order of arrival can influence the abundance of AMF species colonizing a host. These priority effects can have important implications for AMF ecology and the use of fungal inocula in sustainable agriculture.

Environmental variability counteracts priority effects to facilitate species coexistence: evidence from nectar microbes.

The order of species arrival during community assembly can greatly affect species coexistence, but the strength of these effects, known as priority effects, appears highly variable across species and ecosystems. Furthermore, the causes of this variation remain unclear despite their fundamental importance in understanding species coexistence. Here, we show that one potential cause is environmental variability. In laboratory experiments using nectar-inhabiting microorganisms as a model system, we manipulated spatial and temporal variability of temperature, and examined consequences for priority effects. If species arrived sequentially, multiple species coexisted under variable temperature, but not under constant temperature. Temperature variability prevented extinction of late-arriving species that would have been excluded owing to priority effects if temperature had been constant. By contrast, if species arrived simultaneously, species coexisted under both variable and constant temperatures. We propose possible mechanisms underlying these results using a mathematical model that incorporates contrasting effects of microbial species on nectar pH and amino acids. Overall, our findings suggest that understanding consequences of priority effects for species coexistence requires explicit consideration of environmental variability.

Best Fit Bin Packing with Random Order Revisited.

Best Fit is a well known online algorithm for the bin packing problem, where a collection of one-dimensional items has to be packed into a minimum number of unit-sized bins. In a seminal work, Kenyon [SODA 1996] introduced the (asymptotic) random order ratio as an alternative performance measure for online algorithms. Here, an adversary specifies the items, but the order of arrival is drawn uniformly at random. Kenyon's result establishes lower and upper bounds of 1.08 and 1.5, respectively, for the random order ratio of Best Fit. Although this type of analysis model became increasingly popular in the field of online algorithms, no progress has been made for the Best Fit algorithm after the result of Kenyon. We study the random order ratio of Best Fit and tighten the long-standing gap by establishing an improved lower bound of 1.10. For the case where all items are larger than 1/3, we show that the random order ratio converges quickly to 1.25. It is the existence of such large items that crucially determines the performance of Best Fit in the general case. Moreover, this case is closely related to the classical maximum-cardinality matching problem in the fully online model. As a side product, we show that Best Fit satisfies a monotonicity property on such instances, unlike in the general case. In addition, we initiate the study of the absolute random order ratio for this problem. In contrast to asymptotic ratios, absolute ratios must hold even for instances that can be packed into a small number of bins. We show that the absolute random order ratio of Best Fit is at least 1.3. For the case where all items are larger than 1/3, we derive upper and lower bounds of 21/16 and 1.2, respectively.