Zobrazeno 1 - 10
of 416
pro vyhledávání: '"Pegden A"'
We study the intersection of a random geometric graph with an Erd\H{o}s-R\'enyi graph. Specifically, we generate the random geometric graph $G(n, r)$ by choosing $n$ points uniformly at random from $D=[0, 1]^2$ and joining any two points whose Euclid
Externí odkaz:
http://arxiv.org/abs/2411.04349
Autor:
Frieze, Alan, Pegden, Wesley
We study the fixation probability for two versions of the Moran process on the random graph $G_{n,p}$ at the threshold for connectivity. The Moran process models the spread of a mutant population in a network. Throughtout the process there are vertic
Externí odkaz:
http://arxiv.org/abs/2409.11615
If four people with Gaussian-distributed heights stand at Gaussian positions on the plane, the probability that there are exactly two people whose height is above the average of the four is exactly the same as the probability that they stand in conve
Externí odkaz:
http://arxiv.org/abs/2407.02589
We prove that a polynomial fraction of the set of $k$-component forests in the $m \times n$ grid graph have equal numbers of vertices in each component, for any constant $k$. This resolves a conjecture of Charikar, Liu, Liu, and Vuong, and establishe
Externí odkaz:
http://arxiv.org/abs/2310.15152
Autor:
Frieze, Alan, Pegden, Wesley
The greedy and nearest-neighbor TSP heuristics can both have $\log n$ approximation factors from optimal in worst case, even just for $n$ points in Euclidean space. In this note, we show that this approximation factor is only realized when the optima
Externí odkaz:
http://arxiv.org/abs/2310.03222
Autor:
Pegden, Wesley, Sevekari, Anish
In this paper, we provide a family of dynamic programming based algorithms to sample nearly-shortest self avoiding walks between two points of the integer lattice $\mathbb{Z}^2$. We show that if the shortest path of between two points has length $n$,
Externí odkaz:
http://arxiv.org/abs/2307.05042
Autor:
Frieze, Alan, Pegden, Wesley
We discuss the existence of Hamilton cycles in the random graph $G_{n,p}$ where there are restrictions caused by (i) coloring sequences, (ii) a subset of vertices must occur in a specific order and (iii) there is a bound on the number of inversions i
Externí odkaz:
http://arxiv.org/abs/2305.00880
We study the intersecting family process initially studied in \cite{BCFMR}. Here $k=k(n)$ and $E_1,E_2,\ldots,E_m$ is a random sequence of $k$-sets from $\binom{[n]}{k}$ where $E_{r+1}$ is uniformly chosen from those $k$-sets that are not already cho
Externí odkaz:
http://arxiv.org/abs/2302.09050
Publikováno v:
Proceedings of the Edinburgh Mathematical Society 67 (2024) 287-298
We show that if an open set in $\mathbb{R}^d$ can be fibered by unit $n$-spheres, then $d \geq 2n+1$, and if $d = 2n+1$, then the spheres must be pairwise linked, and $n \in \left\{ 0, 1, 3, 7 \right\}$. For these values of $n$, we construct unit $n$
Externí odkaz:
http://arxiv.org/abs/2210.13981
Autor:
Frieze, Alan, Pegden, Wesley
We consider the problem of generating uniformly random partitions of the vertex set of a graph such that every piece induces a connected subgraph. For the case where we want to have partitions with linearly many pieces of bounded size, we obtain appr
Externí odkaz:
http://arxiv.org/abs/2206.00579