Mathematics – Combinatorics
Scientific paper
2007-11-12
Published in Combinatorics, Probability and Computing, 16 (2007), issue 1, 159-166
Mathematics
Combinatorics
10 pages
Scientific paper
We answer three questions posed in a paper by Babson and Benjamini. They introduced a parameter $C_G$ for Cayley graphs $G$ that has significant application to percolation. For a minimal cutset of $G$ and a partition of this cutset into two classes, take the minimal distance between the two classes. The supremum of this number over all minimal cutsets and all partitions is $C_G$. We show that if it is finite for some Cayley graph of the group then it is finite for any (finitely generated) Cayley graph. Having an exponential bound for the number of minimal cutsets of size $n$ separating $o$ from infinity also turns out to be independent of the Cayley graph chosen. We show a 1-ended example (the lamplighter group), where $C_G$ is infinite. Finally, we give a new proof for a question of de la Harpe, proving that the number of $n$-element cutsets separating $o$ from infinity is finite unless $G$ is a finite extension of $Z$.
No associations
LandOfFree
Cutsets in infinite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Cutsets in infinite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Cutsets in infinite graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-128400