ترغب بنشر مسار تعليمي؟ اضغط هنا

The firefighter problem on polynomial and intermediate growth groups

179   0   0.0 ( 0 )
 نشر من قبل Gideon Amir
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

We prove that any Cayley graph $G$ with degree $d$ polynomial growth does not satisfy ${f(n)}$-containment for any $f=o(n^{d-2})$. This settles the asymptotic behaviour of the firefighter problem on such graphs as it was known that $Cn^{d-2}$ firefighters are enough, answering and strengthening a conjecture of Develin and Hartke. We also prove that intermediate growth Cayley graphs do not satisfy polynomial containment, and give explicit lower bounds depending on the growth rate of the group. These bounds can be further improved when more geometric information is available, such as for Grigorchuks group.



قيم البحث

اقرأ أيضاً

We generalize both the notion of polynomial functions on Lie groups and the notion of horizontally affine maps on Carnot groups. We fix a subset $S$ of the algebra $mathfrak g$ of left-invariant vector fields on a Lie group $mathbb G$ and we assume t hat $S$ Lie generates $mathfrak g$. We say that a function $f:mathbb Gto mathbb R$ (or more generally a distribution on $mathbb G$) is $S$-polynomial if for all $Xin S$ there exists $kin mathbb N$ such that the iterated derivative $X^k f$ is zero in the sense of distributions. First, we show that all $S$-polynomial functions (as well as distributions) are represented by analytic functions and, if the exponent $k$ in the previous definition is independent on $Xin S$, they form a finite-dimensional vector space. Second, if $mathbb G$ is connected and nilpotent we show that $S$-polynomial functions are polynomial functions in the sense of Leibman. The same result may not be true for non-nilpotent groups. Finally, we show that in connected nilpotent Lie groups, being polynomial in the sense of Leibman, being a polynomial in exponential chart, and the vanishing of mixed derivatives of some fixed degree along directions of $mathfrak g$ are equivalent notions.
208 - Bruce Kleiner 2007
We give a new proof of Gromovs theorem that any finitely generated group of polynomial growth has a finite index nilpotent subgroup. Unlike the original proof, it does not rely on the Montgomery-Zippin-Yamabe structure theory of locally compact groups.
Asymptotic properties of finitely generated subgroups of free groups, and of finite group presentations, can be considered in several fashions, depending on the way these objects are represented and on the distribution assumed on these representation s: here we assume that they are represented by tuples of reduced words (generators of a subgroup) or of cyclically reduced words (relators). Classical models consider fixed size tuples of words (e.g. the few-generator model) or exponential size tuples (e.g. Gromovs density model), and they usually consider that equal length words are equally likely. We generalize both the few-generator and the density models with probabilistic schemes that also allow variability in the size of tuples and non-uniform distributions on words of a given length.Our first results rely on a relatively mild prefix-heaviness hypothesis on the distributions, which states essentially that the probability of a word decreases exponentially fast as its length grows. Under this hypothesis, we generalize several classical results: exponentially generically a randomly chosen tuple is a basis of the subgroup it generates, this subgroup is malnormal and the tuple satisfies a small cancellation property, even for exponential size tuples. In the special case of the uniform distribution on words of a given length, we give a phase transition theorem for the central tree property, a combinatorial property closely linked to the fact that a tuple freely generates a subgroup. We then further refine our results when the distribution is specified by a Markovian scheme, and in particular we give a phase transition theorem which generalizes the classical results on the densities up to which a tuple of cyclically reduced words chosen uniformly at random exponentially generically satisfies a small cancellation property, and beyond which it presents a trivial group.
257 - Bobo Hua , Juergen Jost 2012
We consider harmonic functions of polynomial growth of some order $d$ on Cayley graphs of groups of polynomial volume growth of order $D$ w.r.t. the word metric and prove the optimal estimate for the dimension of the space of such harmonic functions. More precisely, the dimension of this space of harmonic functions is at most of order $d^{D-1}$. As in the already known Riemannian case, this estimate is polynomial in the growth degree. More generally, our techniques also apply to graphs roughly isometric to Cayley graphs of groups of polynomial volume growth.
338 - Emmanuel Breuillard 2007
We get asymptotics for the volume of large balls in an arbitrary locally compact group G with polynomial growth. This is done via a study of the geometry of G and a generalization of P. Pansus thesis. In particular, we show that any such G is weakly commensurable to some simply connected solvable Lie group S, the Lie shadow of G. We also show that large balls in G have an asymptotic shape, i.e. after a suitable renormalization, they converge to a limiting compact set which can be interpreted geometrically. We then discuss the speed of convergence, treat some examples and give an application to ergodic theory. We also answer a question of Burago about left invariant metrics and recover some results of Stoll on the irrationality of growth series of nilpotent groups.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا