Asymptotic dimension, Isoperimetric Problem, and Traveling Salesman Problem in Groups- Anna Erschler

Who speaks in this episode?

• Anna Ursler (Main speaker)

What is discussed, and when

1. 0:00 – 10:00: Anna Ursler, Aminability, Growth Function
2. 10:00 – 20:00: Growth Function, Cost Inequality
3. 20:00 – 30:00: Growth Function, Cost Inequality
4. 30:00 – 40:00: Simplicial Dimension
5. 40:00 – 50:00: Universal Traveling Assessment Problem, Z2
6. 50:00 – 1:00:00: Aminability
7. 1:00:00 – 1:03:47: Aminability, Shalom's Property

Notable quotes from "Asymptotic dimension, Isoperimetric Problem, and Traveling Salesman Problem in Groups- Anna Erschler"

• So it's my pleasure to introduce Anna Ursler who will be giving the last talk of either groups and dynamics seminar.

  about Anna Ursler · at 0:15

• The second one is about dimension. For us would be mostly about asytoic dimension. But several other notions would be of dimension are also relevant dimension.

  about Universal Traveling Assessment Problem · at 1:16

• Maybe if you know that the boundary is smaller could be chosen much smaller than the set and we are interested in this function but today we'll be even much more interested in the following.

  about Aminability · at 3:58

• Take for example a billion groups at D in this or in other groups. when I say the boundary.

  about Z2 · at 4:56

• V n here v N is the growth function that is the volumes of the balls in a graphic. The number of the spheres it seems a natur very natural conjecture it should be approximately nt minus one.

  about Growth Function · at 8:53

• Actually but for other groups it could be much larger but it couldn't be smaller. So but for polinomial growth it should be really this easy argument we know it's the same as…

  about Polynomial Growth · at 18:01

• So what is relation to our story? So yes control functions so for the moment we are comparing two functions at least as a function here which was defined here and the control function for.

  about Simplicial Dimension · at 24:41

• Aminable groups we prove now it's not possible so it seems to be what so and but the very last question we prove this algebraic consequences before we did not know much how…

  about Shalom's Property · at 1:02:00

Who and what is mentioned in this episode?

People

• Anna Ursler — Person · Main speaker · 1 mention · first at 0:15
  Introduced as the final speaker of the seminar; presents results relating Følner sets/amenability, asymptotic dimension control functions, and universal traveling salesman-type invariants.

Concepts & topics

• Aminability — Concept · Key argument · 3 mentions · first at 3:53
  Central to the discussion of group properties and the definition of certain functions within group theory.
• Growth Function — Concept · Key argument · 4 mentions · first at 8:53
  Central to the discussion of group properties and their growth behaviors.
• Polynomial Growth — Concept · Key argument · 4 mentions
  Contrasted with exponential growth in the discussion of group properties and growth functions.
• Universal Traveling Assessment Problem — Concept · Core topic · 1 mention · first at 43:17
  Introduced as one of the three main topics of the talk, relating to group theory and dynamics.
• Z2 — Concept · Core topic · 1 mention · first at 47:05
  Mentioned as an example in the discussion of group theory and dynamics, illustrating specific properties and behaviors.
• Cost Inequality — Concept · Key argument · 2 mentions · first at 17:31
  Mentioned in the context of comparing growth functions and their implications for group theory.
  Actually but for other groups it could be much larger but it couldn't be smaller. So but for polinomial growth it should be really this easy argument we know it's the same as…
• Simplicial Dimension — Concept · Key argument · 1 mention · first at 35:31
  Discussed as a notion of dimension relevant to the study of groups and their properties.
• Shalom's Property — Concept · Key argument · 1 mention · first at 1:01:21
  Mentioned in the context of discussing algebraic consequences of finite dimension in groups.

Full transcript with timestamps

0:15 So it's my pleasure to introduce Anna Ursler who will be giving the last talk of either um groups and dynamics seminar.

0:25 Thank you. Thank you for this. So I will speak about um a priority three about three topics which are priori might seem quite different but turns out to be quite related. So so we'll I'll speak about groups. So we'll have say tree

1:03 and we want to study the following problem. The first one is as a pyramid problem. The second one is about dimension. For us would be mostly about asytoic dimension. But several other notions would be of dimension are also relevant dimension

1:39 and uh we will speak also about uh universal traveling assessments problem and invariance uh that could be defined uh in something related to universal trans uh first I give some definitions. Now for the first problem. So we just consider the K graph of our group right graph that is we can see that the graph the vertices of these graphs are elements of our group tree and we have an edge between G and JS. uh if s is inside some finite generating settle dream uh this is the metric uh space we are interested in by the way some of our invarants uh and some of our questions uh uh could be studied and several question asked could be asked for matrix spaces but for groups there is a special structure that we are interested in um so this is the first problem I give some definitions So uh given such group equipped with a par generating set we call function uh js of n is the minimal cardality of of finite set

3:38 such that the size of its boundary divided the size of the Z is smaller than 1 / M. This function is defined when whenever the group is aminable. So this is one of the possible definition of aminability. Maybe if you know that the boundary is smaller could be chosen much smaller than the set and we are interested in this function but today we'll be even much more interested in the following function. I yeah it's a minimum of the diameter of such sets of diameter of B we again the same condition on the set uh such that the boundary is n times smaller than than the that just a few words what we know about such functions.

4:49 So uh maybe an easy example, easy and not so easy example. Take for example a billion groups at D uh in this or in other groups. uh when I say the boundary if you want to solve the problem exactly then it matters what definition of the boundary we take. So in all this context for precise definitions uh there is at least three stud. So we have a set for me I will usually say the boundary is internal vertx boundary. So we have a set and we look on the points of the set at distance one from the complement. This is internal vertx boundary but also one can study external vertex boundary that is the points at distance one in the complement or one can study edge boundary just the number of edges between a set and a complement.

5:57 It's I try to search the literature and my understanding that even on ZD exact solutions are not known actually. So and even approximate solutions. So for for example for for the edge boundary it seems it's as late as Barber and edge uh 201 uh 18 uh for for for the edge boundary where they say that natural um optimal sets are good for any genetic set but only they s good astoically And it seems to be an open question if they're exactly optimal for for vertx boundaries is for out to vertx boundary understand some reference one and one in ' 70s rush for or general generating sets in 95 and my understanding maybe for for internal boundary it's not known in but for us it's not very important we are interested in asytoic of this of a boundary right and then clearly it's not important with definition I take the boundary will change only optimum because they're constant and for all this function we want to know less

7:18 and just another maybe remark okay for the for the d at least it's not so difficult to see spheres are smaller than the balls so spheres balls that is furnaces if you take an more general example is of polomial growth growth then it's not absolutely obvious that the bolts are firer but this is true. So bolts are fer that is the spheres are much smaller. Bolts are fer the oldest reference I know is coding many quotes say in 98. Those similar state maybe related arguments in a little bit different language might appear earlier 98.

8:25 And uh I feel but interesting even in this very straightforward case because the groups are virtually important right so we know very good their structure it's an open question seems to be an open question what is the size of the of the of the spheres so we can consider the size of uh let's say v n + one minus v n here v N is the growth function that is the volumes of the balls in a graphic. The number of the spheres it seems a natur very natural conjecture it should be approximately nt minus one. This is known to be the case for two step important groups. It's Briar and Midona um a little bit more than 10 years ago and they ask this question actually they ask a stronger question which recently seems

9:26 [clears throat] uh turn to be out recently there are other questions uh there could be count examples but for for for this question we don't know count example I think we shouldn't expect any but surprisingly we don't know even such elementary definition returning to our function what does it mean if you want to to understand are all balls uh optimal at least asymtoically. So because the balls the size of the balls is n to the d and to to say that here the size nt minus one means optimus because constant they are optimal to of being this boundary and time smaller and this is not known even in this uh in this case but what is easy to see simply polomial growth right if you look on the balls let's look on the balls of radius between n divided by two and n like n / 2 n / 2 + one and and so on until

10:24 sorry what what is what does it mean to me for thank you say the sets the sequence of fa sets let's say omega i sequence of sets sets if the boundary the size of the boundary uh divided by the size of of the sets goes to zero. Right? This is just to say and one can ask for an instance that in sequences like this or one can ask a stronger condition for given n we want to like one / n further if the the ratio is smaller than one / n. So uh what I want to explain now it's very easy to see from polomial growth if you look on the box we don't know if all of them are constant times n for like in this question about the size of the spheres but at least very easy to see look on the balls of radius between n / two until n at least one of them should be a constant times n factor at least one of them should have sphere of size smaller than constant n d minus one. So in other words for the FA function it's

11:50 clear that if we identify function which we always do up to equivalence relation it doesn't matter if you multiply by a constant or if you multiply by arment of the by the constant so n is equivalent to n to the d where d is a growth right uh h and now there are many open questions uh formulated in this very basic using these very basic notions. So for example uh again there is a very easy argument if the growth of the group is sub exponential the both uh there is a subsequence of both which is fer uh now in binomial growth as I said it's known maybe not with an optimal parameter but the sequence of all at least it is for groups of segments exponential growth it's not known take groups of exponential growth do All BS from a sequence of FA sets we don't know in particular we don't know even for any plain example like for Griert groups we don't know at all uh what is the size of the S should we expect maybe for all of

13:09 Fer also on the opposite scale it's straightforward from the definition if we have a group of exponential growth it's not possible that all BS balls are but it's an open question can we have a subsequence of BS which is for maybe never but we don't know how to prove it so but oh so this is about just comparison with the growth function yeah

13:35 and maybe okay this what's is it possible that the size of the n is just a polomial or altering between polomials or

13:47 no no as I said like a possible argument for example like doubling Not only for for groups of growth actually for reasonable space matrix spes is doubling for example the argument explained in many codes the the spheres the size of the spheres divided by the size of the bolts goes to zero so you I you mean I is it possible on subsequence no so and yes I didn't explain but it is polomial but we don't know the optimal degree so um maybe I don't have the time to say exactly like and a better estimate in [clears throat]

14:34 estimates uh give an upper bound for for for the size of the spheres the lower bound in all polinomial growth is the same as you expect the same as it's happened for Z the lower bound is m to the power t minus one but it is known the upper bound bound the upper bound for the spheres is n d minus some constant. So contractually this constant is one but this is known only for twostep uh uh pedomal growth groups. Now a very bad beta is is in the al of mikot much better beta is in prior and we we don't know what it is but since it's really d minus something so you see the size is polinomial the question is only is if it's exactly t minus one I don't know if answers your question and so uh um this is about the boots And now yeah maybe I draw some pictures of what happens on Z two for example on Z two with at least with one definition of boundary uh the optimal sets would be walls in the matric that looks like this in

15:51 the case of the turret in the other definition of the boundary it would be squares right so this is sort of L1 uh all this is an infinity ball and but we are interested only up to a constant up to a constant they are all the same as the ball you like to to choose and uh just some command and what about dimension because we want to discuss dimension do we see some dimension of our space uh from the furnace sets not really okay in a billion case we do see right in a billion is whatever reasonable definition of dimension you will take we'll discuss in a moment a particular one. So dimension is equal to and and so okay and says function of n is n to the d. So you can say oh we see the dimension but this is a rare case when we see the dimension because even if the growth is polomial uh the growth is not a dimension.

17:07 Take group by this dimension is three but uh but the growth is n to the four and actually this n to the four is much more relevant for functions. So just in general hold on cost inequality cost inequality quality the functionically is always larger larger than row function constantly And so for for polomial growth it's really the case that it's equivalent actually but for for for other groups it could be much larger but it couldn't be smaller. So but for polinomial growth it should be really this easy argument we know it's the same as its growth and for many groups polinomial growth growth constant the growth degree is not is not our dimension but let me say what yes and what about diameters because for us today we are interested mainly in the diameters of ver sets well uh the diameters of the sets for pol would be linear you you can't make smoother than linear just by by this inequality but yes but even this

18:46 is straightforward alment I explained already it wouldn't be greater than constant times linear that is linear and so so we don't not if you look on the on the furnace sets or if you look at of oftric function we don't uh we don't see the the diameter yet. We don't see the dimension yet. Uh let me see which definition of dimension we want to use today. So we will speak about asytoic dimension dimension. The notion of sotic dimension is something sort of inspired I would say uh by the notion of libe covering dimension just I remind we don't need covering dimension but I reminding dimension first so if you have some space the back covering dimension for for reasonable symmetric spaces would be the same as topological dimension there are many ways to to define it but covering dimension defined But in the following way we have some covering I try to draw a covering of a plane. This wasn't very heavy one.

20:10 Maybe it better take something with hexagons. Let's consider the covering of our space by open set for example and uh the covering dimensions about like this. We take some covering if we want to claim that all we can take a refinement. Refinement means we just take small replace all the sets by possibly smaller sets. And then we see uh uh uh what is the maximum uh of the number such that the point belongs to several sets. For example, on this picture for for these points, it belongs to three possible sets, right? One, two, three. and uh and the dimension the topological dimension is free and I would define in a moment asic dimension it will be also free for example in this picture and so what about asic dimension it's like this we want to consider covering of our matrix space in general x and we want that for any number are the following holds There exist well so it's in the wrong place. So for all f are the resistor

21:39 covering with the following properties. that any ball of radius R belongs to one of the sets in the covering belongs to one of the sets. And um on the other hand uh uh we want to have some bound on the size of our sets and let's say diameter diameter of such sets sets is at most some function of r for the plane for example it's clear that such pictures provide you. Yes. Ah. Yes. And we look on the numbers. We look on the numbers on look on possible D such that each point each point belongs to at most D + one points to at most D + one points.

23:10 And we say the dimension is not greater than D. For example, on the plane, it's easy to see. Just take this picture, rescale it, multiply by a constant. We see. So what? So we see here the the size. So each ball of radius some constants times the side of these hexagons is uh um belongs to one of the sets. On the other hand the size of our sets is just constants time this r. So such functions f of r f of r are called control functions foric dimension function asic dimension and if r f of r is smaller than constant times If arc can be chosen in this way then the space is set to have dimension dimension is finite.

24:41 So what is relation to our story? So yes control functions uh so for the moment we are comparing two functions at least as a function here which was defined here and the control function for for asytoic dimension control function for synthetic dimension was known in some for some families of matrix space and some families of groups now asatic the synotical function apart from straightforward examples was not didn't seem to be known in any class of groups until now. And so one of my goal to explain you how to find in some situation the diameters of furnace sets and in the same situation these diameters of furnace sets. So this function is in many families of groups turns out to be equivalent to the contra function. This is our first observation.

25:41 Yeah, I forgot to say uh everything I I guess I will be speaking on today is a joint work with [clears throat] joint this department. And there is a third function related to universal traveling assessment. But since the time M is limited, it may be I will try first to formulate the results about control function as function and hopefully at the end at least quickly explain what is the other function related to segment and why it also in many families turned out to be equivalent to the contra function of synthetic dimension to theatic ones. So maybe I [clears throat] somewhere here.

27:09 So, so v is our growth function from colonial of cost inequality. Uh what is clear about the diameters? It's clear uh that diameters as as a couldn't be smaller than inverse function the function right for us uh for example if the growth exponential grow is exponential no it's not small it's greater is growth is exponential then so it's diameters are greater than lo function of p it it holds uh once says that uh uh project has lossless lossless um [clears throat] asic function.

28:33 This is terminology introduced by Pet No more than 20 years colleagues but no And he asked the question is there at least one group which is not lossless. Sorry I missed the definition of lossless

28:53 lossless if uh if if if we have equivalence if if we if equivalent so it's always greater

29:03 okay than this expression but if the equivalent let's say that the group is lossless or maybe we can say function so it's meaning function is lossless with respect totric function why he call

29:18 it's for groups no it's for any group. So for for for any groups you take just inverse function of the growth function but our main interest would be exponential growth actually and there function of exponentially is logarithmic right and so we better now ask do we have groups which are not lossless there are many families of groups which are actually lossless what why he calls it losses meaning so isatic function can be shown to be quite symmetric in variance natural invariant right of of our group. But do we get any new information from other function if you know the fer function? And a slightly different question but for regular function equivalent right do we get any information about fer if know is it metric or if we know any information about and vice versa. So uh uh and loss is if you don't lose the information if one as it give gives us the other and um so now I want to explain the

30:30 state actually there are many groups which are not lossless but somehow it seems they were not no this was not on until I say something what is losers and what is not loss and what explain what is uh the connection to to to function for dimensions dimension

31:23 several famous examples. So here would be groups and here I will write what are diameters a magic function function uh then control function for control function for simplic function uh for dimension and I will have time quickly explain Again [clears throat] the the first function would be elongation of something we call it navigation of magic.

32:14 Uh so what happens? So here we have just n to the d. uh yes the rift product is a final group I write the lamb proof on the right so z d x acts on the on the direct sum of that to z for example which is index by z d here the dmetric function would be n to the d and maybe I'll write also and it would be lossless And uh well control part would be um actually it's not completely obvious but true and well known now that control function would be n to the d is the result of prosk at lank 25 years ago something really long uh uh and this is something new but I didn't explain And you can also have end to the team or you can look. Yes, you can group on groups with spite as dimension.

33:28 We assume that dimension is um spin. So if it's finite just by by definition uh control function is linear but uh something that uh no show more than 20 years ago the diameters are linear. some new functions here will be also linear and then there are many other classes which are lossless uh maybe I don't list them all of them but at least one of them uh there are some groups of gelian general uh which given a function f uh supposing that f of n divided by n doesn't decrease. So I write increased but in fact it doesn't decrease. So uh these are groups that Jack have constructed several ago to explain that for a function if you have a reasonable function you can for any function you can construct a group with a given FA function and so uh for uh they did not describe the diameters but this can be easily done if you know all their estimates so their group would be also lost. that and they have really

35:06 prescribed diameters. So diameters would be just f of any function f such as one doesn't decrease and uh control function. So they describe further function uh we can describe diameters which are really very closely related to to to to their results. But something that wasn't known that that we we can prove now we can also evaluate control function of the synicic dimension it will be also f like this and then uh uh there are other families of solvable groups uh uh like old groups which are important by a billion. So there are many other families where we also uh have the same answer for corporal function and for uh for for fortric one.

36:04 But what are most losest examples? So the easiest example we have take just re products within group Z. Here the furnace sets at least straightforward furnace sets has the sides n to the power n to the d. So more or less close to x n to the d. But for diameter so for diameters we just our new result diameters would be n ^ d + one. uh so and we calculated the it's not we so I said we it's also broken no here it's very easy it's maybe easy but no the main thing with broken that is this one cor products with z and our function will be also like this and so this is not I

37:22 I say didn't actually estimate was a little bit like that that but their main motivation was to understand uh understand finite or not the estimate was enough but if you look carefully on the on the argument actually give this. So for some groups we study control function uh was more or less known and main goal is to control the diameters and uh to see we obtain the same answer and uh for some other classes of groups our our evaluation is new even for the constant function. Maybe I mention some other examples. Um uh like one can consider something that can space like shuffle group.

38:16 I will define in a moment shler group on Z. In this family of groups both control function evaluation and diameter so the functionation is new seems to be new and we've evaluated and it's n of dd + one also and but the fma function is approximately x n to the d. So there these are examples are also not losses there is some interest to look on these examples. uh I'll try to explain in a moment because in such question there is a special um meaning when dimension is finite. So uh finite or infinite yes for z reasonable notion of dimension dimension is infinite the group contains z to infinity. Yes.

39:17 So in this table have you taken logarithms of everything? No, it's no but I I didn't say what is the fer function for the fer function you need to take the logarithm you get n to the d maybe I didn't say it correctly but I was never writing actually the f function but here what the a for function you don't need to take the logarithm and so uh just the sha group I will say in a moment these are groups of pytoic dimension And uh what is nice to know they are also not lossless and um and we we have some other families maybe I don't list them uh here so for various families of aminable groups in particular for for many families of soluble groups these groups are not solable but at least uh so we calculated Ed three function the first one I didn't explain yet and we got the same asytoics uh seems to be a new phenomena I think and even we hesitate at the very beginning or should we expect for all

40:35 groups but we have a work in progress maybe I don't want to explain uh explain the construction yet but for this comparison quant function is in many many classes it turns to be the same but we know now to construct groups where they're not equivalent. So, and I'm really curious to know what is the condition to ensure they equivalent. Uh we have different arguments. We we don't have exactly the same argument in various classes but for some sometimes different reasons we get the same function. I'm curious to know why. So, and maybe I say a few words. What is yes I say what what is a shuffle group? So if you have a some base group for example 16 for us here uh you consider the group of planetary permutation planetary permutations of Z uh uh just permutation that permute only finite number of points and you consider extensions you consider semi direct product of this group by Z something it's called lamb shaft group uh and so

41:58 uh as I said we related functions is n to d + one and diameters is n to d + one and but maybe it's time for me to to also to define some other uh the first function I want to explain Thank you. What is the first function? uh we take a matrix space X what is universal travel assessment problem it's like this you want to approximate travel assessment problems problem you probably know like you take a finite set say V and X and you want to find the shortest path to visit all points of V and Universal Dance problem is some universal algorithm universal in the following way. You want to enumerate all points of your space X that's considered an order total order on X. numerate numerate X and then whatever set is given you just visit the points with respect to this defined in advanced order clear this agreement will almost never give exactly shortest path well if the space is a And obviously it will

44:00 give a shortest path right if you get some number of points that I think is just to insert from left to right it would be the shortest path in general you wouldn't give a shortest path you never can expect it but training problem says what is the multiplicative error we are happy if the ratio is not too bad of this path given by the algorithm by by the actual shortest path something in computer science called competitive ratio. So, so we want to say what are spaces where the competitive ratio would be nice something very easy to see if you have a metric tree like this.

44:41 What is a good way to enumerate uh the points to have a good approximation for traveling? Just I have drawn the tree on a plane and then just vis let's visit the points in such order. We just go around around the tree and the order is the first visit of the of the vertx on this picture. It's clear the path would not be greater than constant which is two in this case times the actual path. So for trees very easy to see. So it's the the ratio is a constant. That is the best possible thing one can expect is a constant. For trees is a constant. We can show for delta hyperabolic spaces particular groups it would be constant.

45:32 And uh so one of question can ask what are the spaces where it's constant it's uh I don't know exactly because sometimes space is very close to hyperbolic but not hyper hyperbolic can have this constant but this is well a typical I would say situation. Um so for us trees and hyperbolic spaces or much are the best and what happens for other spaces. The story of universal travel season problem has started with a paper platman in the 80s.

46:35 82 what studied this univers problem on the clay it's the same for us to say is it R2 or Z2 it's really equivalent problems They started both discrete and non-discrete context and they observed there is some nice algorithm which of course not so good as for the trees but with some very much controllable error. So so take for example Z2 for that. story starts with Z2 and uh plasma introduced an order on Z2. So that the ratio if you have K points if the V cardality of V is K rep is K. uh the error in this ratio shortest path given by algorithm or actual shortest path would be at most logarithmic and um maybe ask explain quickly.

47:39 Interesting enough that even for that two uh uh uh the question about actual ratio seems to be still open. So uh in the very first paper but first I explain the algorithm and maybe I have a few minutes to to comment what is known and what is not known. Um how it works. Uh the tree is not so interesting but how you would enumerate that to what total order you know on that two. I give you that too and I ask to enumerate the points. Maybe you have some favorite orders. So I guess everybody knows lexographic order right? But it would be extremely bad for ourself.

48:35 For example, one way to enumerate a point just you first place it all points on one vertical line then on the next one and then on the next one. Right? But observe that for universal tra this order does not make sense at all because take some some large con let's say take two k points and here let's take the distance k like this this vector uh yes like this take k points with some projection on vertical line and other k points with projection zero. If you try to follow the hexographic order, you will have a lot of zigzags. You will jump like this and like this. Right? So why the actual distance is linear in K, right? You just visit this, go back here and visit okay other points if will give you something like K square.

49:36 Um and this is not what what we like and but but plasma observed. There is a much better way to enumerate the points and the idea we need to take as a space filling curve on R2 on on the corresponding curve on Z2 and here the ratio would be logarithmic. It wouldn't be linear. It would be logarithmic. So uh it's it's a bit difficult to draw. I'm not good in drawing the pictures but I'll try to need to take something like a manga curve. So you can construct it by substitution. If you have four points you just visit them in some order. Then you take four tpples of four points you just visit them like this. You go here that is if you consider them as a points you want to follow this order cyclic order simply and then but we have many more points.

50:40 So we visit like this like this like this and like this. This is our on this final approximation of our two then but we want to continue to to construct the corresponding curve. We want to consider four things like this. again it's not very beautiful but in my I mean the curves are beautiful but not in my pictures uh so you you need to consider four and four and four again four like this and just on this couple of four you want again just a circle thing and here you just connect them like this visit all this and visit all this or this and you pass this is the order of Barto plasma in the very first paper they said oh there is the logarithmic bound but oh we think it's our algorithm is very efficient we we think there is a constant concept ratio which this is was very thick and really much optimistic it's it's not at all constant this ratio until recently the lower bound so plasmine for the ratio

51:51 gives it smaller than longer constant logarithm of of the number of points until recently the lower bound is log was log something I don't write exact answer but something like log to the^ 1 / 6 and here um we have cosaris who is a graduate student in princon who very recently improved this known for many years lower bound and your estimate is square root of log right

52:25 it is over log log yes but I don't want to test about log because the actual answer can be logarithm right and we still don't know so the up about log seems to be a very natural question asked in some papers so many works until now mostly by computer science people and so and some question asked the is it is it logarithmic so the cosmos uh the quaries for for the plane proves something like greater like log in this log I don't like log and this is surprising we still don't know even log but which nice to know but this is one thing but um some command uh what do we for which spaces we know there is such more or less nice saying for us logarithmic is Nice. We can't explain much matter unless the group is really very close to a tree that is hyperbolic or something very close to hyperbolic.

53:30 So the best answer even for the plane is something like logarithm and so but for for which spaces we know that bari platman estimate plasma estimate gives us logarithmic multiplicative error. So is so but so if you have space with a doubling. So if x is a space with a doubling with a doubling condition doubling condition but then it's a work of g and his liberation to something like 2005. uh you have the same upper bound as or for equidian space our result is the one let's say in 2023 or something if the SP more generally if it's is of dimension again you have the same upper bound is lower okay and we conjecture that it's if and only if and we prove this conjecture with additional properties in the infinite dimension case in many families or groups for example for all these groups uh we prove it so now I define our actual function so so so the something relatively good like this logarithmic error is true for finite

55:13 dimension it's conjecturally never true otherwise Yes, but right now I'm interested actually in groups where sa dimension is infinite that is asytoic dimension is finite but as dimension could be infinite and I want to compare what happens for control function what happens for the entities of of the of the furn sets in case the group is aminable and now I want to find the function that we study here so just take an order right so have a space x for last night in group three we want to enumerate the points and we consider some order what do we call uh lamentation of snake so let's consider something similar to the picture I have drawn here for the plane let us consider some points some two groups of points uh we can consider finite set we call it snake if we consider following things. So we consider that the emitters of one set in the other set is bounded by something by diameter of the snake

56:31 diameter of the snake is maximum of the two diameters. max diameter E1 diameter V2 and we want to study how much longer the length that is the diameter of the set is than the width and so something that was very relevant even for for for space dimension in connection with universal tra now dimension for us could be infinite as in all those examples and uh so for us we don't really discuss the algorithm of BTO plasma but we look on this other invariant we are simply interested as it is in this invariant how much a snake can be long how much the length could be longer than the width so [clears throat] given an order we consider the maximum of possible length given the diameter and then we it's we take minimum of the maximum we take the minimum o over all orders I speak about this con about the graph so I say minimum I say maximum we can define the same things continuous and it's rather infomic

57:48 and this is our function next and so now in many situation we calculated it and it turned out to be the same as the control function and now as I said among these two functions uh we now we have a kind of example though They seem to be rare. The emitters in principle could not be the same as control function as dimension. Now comparing to to other function well-known control function of this newly invented sort of by us function of snakes uh we don't know how to prove it and the question can be asked in general uh even for metric spaces are they always equivalent here we don't have count examples we have count with diameters but not for this other question. So I have maybe five minutes, few minutes. How many minutes?

58:38 Maybe few minutes. Few minutes. Yes. So okay just a few very quick words. What else we can ask about diameters and all these functions. So far I discussed this various uh geometric and variance how they related. But a very ambitious patient where very little is known. And what if we know some information about this function and we want to understand something algebraically about our group. So uh there is one case which I yes which I wrote here this result of no 20 years ago or so uh it described it was the first very interesting link why diameters uh of furnace sets are related to dimension at all.

59:30 So he proved uh inequality between these two function actually and that allowed even sometimes to check if the group has infinite dimension he used the estimates on furnaces and the corresponding statement about diameters to to to say that some groups for example some reef products are not doesn't do have in dimension now so for us we have now this variety of various this class if you give me the FA function well I don't say exactly the condition but more or less if you give me a reasonable function uh which is quicker than exponential then uh you would be able to construct a group which is not loss which is which is not lossless yet so no chance in general even for a large variety of function to say the group is losses but there is one special case if the FA function is exponential.

1:00:32 Here it's an open question is this condition equivalent to to the fact to say that as the dimension is finite and there are open question there are many sort of competing smallness condition for minimal groups that might after all be uh be equivalent. So here Novak uh actually Novak he proves already that if dimension is finite uh his group is lossless but can ask the same very similar question but he we don't know if the FA function grow exponentially is uh the group lossless and uh something just the very last result I want to mention so what we prove that if dimension is finite the group does have what is called shalom's property h ofd I don't have time to explain what is this property but the coral are very easy to to state take aminable group of finite dimension then this group for example cannot be a pure torsion group or it cannot be simple group and here for it's very essential that the group is

1:01:39 aminable and for for the question about simplicity if you take ben and mo simple groups um they have pet dimension and but they could be simple. Now uh about uh about torsion I think it's an open question for non- aminable groups but for aminable groups we prove now it's not possible so it seems to be what so and but the very last question we prove this algebraic consequences before we did not know much how dimension could be used to claim something algebraic now we know at least something but then one can ask is are such groups of finite aluminino groups let's say this finite dimension are they all for example aminable if the answer is Yes, it would be a very very farreaching of polomial growth theorem of growth and which is very very ambitious of course to to get any generalization but one doesn't know count example so far we have this tiny step first step maybe in in this very very long road to to to say the group is

1:02:43 elementary mineral at least we can uh conclude that we have some questions because of shalom's I guess I need to stop here There any questions? Um I guess I'll have one question. So do we know that elongation of snakes can be have any sort of growth?

1:03:18 Yes. Well up to some regularity condition we can compute langational snake for for uh for the groups of bell and check. So we have computed it and as I didn't write it like for any reasonable function of n you have f of thank you for this question. Yes. So, any other questions?

Questions about this episode

Who speaks in "Asymptotic dimension, Isoperimetric Problem, and Traveling Salesman Problem in Groups- Anna Erschler"?

Anna Ursler (Main speaker).

What is discussed in "Asymptotic dimension, Isoperimetric Problem, and Traveling Salesman Problem in Groups- Anna Erschler"?

In order: 0:00 Anna Ursler, Aminability, Growth Function; 10:00 Growth Function, Cost Inequality; 20:00 Growth Function, Cost Inequality; 30:00 Simplicial Dimension; 40:00 Universal Traveling Assessment Problem, Z2; 50:00 Aminability; 1:00:00 Aminability, Shalom's Property.

What is mentioned in this Institute for Advanced Study episode?

9 people, works and ideas are mentioned, including Anna Ursler, Aminability, Growth Function, Polynomial Growth, Universal Traveling Assessment Problem, Z2. Each one on this page links to its own page with every episode that mentions it.

How long is "Asymptotic dimension, Isoperimetric Problem, and Traveling Salesman Problem in Groups- Anna Erschler"?

The episode runs 1 h 4 min; the transcript is about 7,460 words in 60 timestamped sections.

More from Institute for Advanced Study

• All analyzed episodes
• People mentioned on Institute for Advanced Study
• Topics mentioned on Institute for Advanced Study