Algebraically recurrent random walks on groups
Initial steps are presented towards understanding which finitely generated groups are almost surely generated as semigroups by the path of a random walk on the group.
Researcher profile
Hilary Finucane
Hilary Finucane contributes to research discovery and scholarly infrastructure.
ResearcherAffiliation not importedOpen to collaborate
Trust snapshot
Quick read
Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
4topics
4close collaborators
Actions
Decide how to stay connected
Identity and collaboration
How to connect with this researcher
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Open a focused conversation when the fit is right
Claim this author entity first to unlock direct invitations.
Research graph
See the researcher in context
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
Building this graph slice
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
3 published item(s)
preprint2011arXiv
Comparing Pedigree Graphs
Pedigree graphs, or family trees, are typically constructed by an expensive process of examining genealogical records to determine which pairs of individuals are parent and child. New methods to automate this process take as input genetic data from a set of extant individuals and reconstruct ancestral individuals. There is a great need to evaluate the quality of these methods by comparing the estimated pedigree to the true pedigree. In this paper, we consider two main pedigree comparison problems. The first is the pedigree isomorphism problem, for which we present a linear-time algorithm for leaf-labeled pedigrees. The second is the pedigree edit distance problem, for which we present 1) several algorithms that are fast and exact in various special cases, and 2) a general, randomized heuristic algorithm. In the negative direction, we first prove that the pedigree isomorphism problem is as hard as the general graph isomorphism problem, and that the sub-pedigree isomorphism problem is NP-hard. We then show that the pedigree edit distance problem is APX-hard in general and NP-hard on leaf-labeled pedigrees. We use simulated pedigrees to compare our edit-distance algorithms to each other as well as to a branch-and-bound algorithm that always finds an optimal solution.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Finite Voronoi decompositions of infinite vertex transitive graphs
In this paper, we consider the Voronoi decompositions of an arbitrary infinite vertex-transitive graph G. In particular, we are interested in the following question: what is the largest number of Voronoi cells that must be infinite, given sufficiently (but finitely) many Voronoi sites which are sufficiently far from each other? We call this number the survival number s(G). The survival number of a graph has an alternative characterization in terms of covering, which we use to show that s(G) is always at least two. The survival number is not a quasi-isometry invariant, but it remains open whether finiteness of the s(G) is. We show that all vertex transitive graphs with polynomial growth have a finite s(G); vertex transitive graphs with infinitely many ends have an infinite s(G); the lamplighter graph LL(Z), which has exponential growth, has a finite s(G); and the lamplighter graph LL(Z^2), which is Liouville, has an infinite s(G).
0 citations0 reviewsNo code linkedOpen access