This content will become publicly available on November 27, 2024

Rainbow Hamilton cycles in random geometric graphs
Abstract

Let be chosen independently and uniformly at random from the unit ‐dimensional cube . Let be given and let . The random geometric graph has vertex set and an edge whenever . We show that if each edge of is colored independently from one of colors and has the smallest value such that has minimum degree at least two, then contains a rainbow Hamilton cycle asymptotically almost surely.

more » « less
NSF-PAR ID:
10477428
Author(s) / Creator(s):
;
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Random Structures & Algorithms
ISSN:
1042-9832
Format(s):
Medium: X
National Science Foundation
##### More Like this
1. Letdenote the power set of [n], ordered by inclusion, and letdenote the random poset obtained fromby retaining each element fromindependently at random with probabilitypand discarding it otherwise. Givenanyfixed posetFwe determine the threshold for the property thatcontainsFas an induced subposet. We also asymptotically determine the number of copies of a fixed posetFin. Finally, we obtain a number of results on the Ramsey properties of the random poset.

more » « less
2. We study the rank of a random n × m matrix An, m; k with entries from GF(2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all (nk) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix An, m; k forms the vertex-edge incidence matrix of a k-uniform random hypergraph H. The rank of An, m; k can be expressed as follows. Let |C2| be the number of vertices of the 2-core of H, and | E (C2)| the number of edges. Let m* be the value of m for which |C2| = |E(C2)|. Then w.h.p. for m < m* the rank of An, m; k is asymptotic to m, and for m ≥ m* the rank is asymptotic to m – |E(C2)| + |C2|. In addition, assign i.i.d. U[0, 1] weights Xi, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X(S) = ∑j∊S Xj. Define a basis as a set of n – 1 (k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1.202.
more » « less
3. Abstract Context

Habitat fragmentation is a leading threat to biodiversity, yet the impacts of fragmentation on most taxa, let alone interactions among those taxa, remain largely unknown.

Objectives

We studied how three consequences of fragmentation—reduced patch connectivity, altered patch shape, and edge proximity—impact plant-dwelling mite communities and mite-plant-fungus interactions within a large-scale habitat fragmentation experiment.

Methods

We sampled mite communities from the leaves ofQuercus nigra(a plant species that has foliar domatia which harbor fungivorous and predacious mites) near and far from edge within fragments of varying edge-to-area ratio (shape) and connectivity via corridors. We also performed a mite-exclusion experiment across these fragmentation treatments to test the effects of mite presence and fungal hyphal abundance on leaf surfaces.

Results

Habitat edges influenced the abundance and richness of leaf-dwelling mites; plants closer to the edge had higher mite abundance and species richness. Likewise, hyphal counts were higher on leaves near patch edges. Despite both mite and fungal abundance being higher at patch edges, leaf hyphal counts were not impacted by mite abundance on those leaves. Neither patch shape nor connectivity influenced mite abundance, mite species richness, or the influence of mites on leaf surface fungal abundance.

Conclusion

Our results suggest that mites and foliar fungi may be independently affected by edge-structured environmental gradients, like temperature, rather than trophic effects. We demonstrate that large-scale habitat fragmentation and particularly edge effects can have impacts on multiple levels of microscopic communities, even in the absence of cascading trophic effects.

more » « less
4. Abstract

Let be a simple graph and be the chromatic index of . We call a ‐critical graphif for every edge of , where is maximum degree of . Let be an edge of ‐critical graph and be an (proper) edge ‐coloring of . Ane‐fanis a sequence of alternating vertices and distinct edges such that edge is incident with or , is another endvertex of and is missing at a vertex before for each with . In this paper, we prove that if , where and denote the degrees of vertices and , respectively, then colors missing at different vertices of are distinct. Clearly, a Vizing fan is an ‐fan with the restricting that all edges being incident with one fixed endvertex of edge . This result gives a common generalization of several recently developed new results on multifan, double fan, Kierstead path of four vertices, and broom. By treating some colors of edges incident with vertices of low degrees as missing colors, Kostochka and Stiebitz introduced ‐fan. In this paper, we also generalize the ‐fan from centered at one vertex to one edge.

more » « less
5. Abstract

Letbe the random directed graph onnvertices where each of thepossible arcs is present independently with probabilityp. A celebrated result of Frieze shows that ifthentypically has a directed Hamilton cycle, and this is best possible. In this paper, we obtain a strengthening of this result, showing that under the same condition, the number of directed Hamilton cycles inis typically. We also prove a hitting‐time version of this statement, showing that in the random directed graph process, as soon as every vertex has in‐/out‐degrees at least 1, there are typicallydirected Hamilton cycles.

more » « less