Let
This content will become publicly available on November 27, 2024
Rainbow Hamilton cycles in random geometric graphs
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
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Random Structures & Algorithms
- ISSN:
- 1042-9832
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
denote the power set of [ n ], ordered by inclusion, and letdenote the random poset obtained from by retaining each element from independently at random with probability p and discarding it otherwise. Givenany fixed posetF we determine the threshold for the property thatcontains F as an induced subposet. We also asymptotically determine the number of copies of a fixed posetF in. Finally, we obtain a number of results on the Ramsey properties of the random poset . -
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
-
more » « less
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 of
Quercus 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
Abstract Let be a simple graph and be the chromatic index of . We call a ‐
critical graph if for every edge of , where is maximum degree of . Let be an edge of ‐critical graph and be an (proper) edge ‐coloring of . Ane‐fan is 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
Abstract Let
be the random directed graph on n vertices where each of thepossible arcs is present independently with probability p . A celebrated result of Frieze shows that ifthen typically 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 in is 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 typically directed Hamilton cycles.
