So, yeah, Lena Lee is joining us from Waterloo and we'll be speaking today about tilings and vertex ordered graphs. Go ahead when you're ready. Thanks. Thanks for the invitation and thanks everyone for being here. Actually, I've been in the University of South Carolina two or three years ago for a nice conference. So hopefully in the future we have a chance to visit the campus in person again. So today I will talk about the tiling problems for vertex ordered graphs. This is a joint work with my PhD advisor, professors of Bolog from University of Illinois, and also Andrew Tricolo from the University of Birmingham in the UK. Okay, so let's start with a basic thing. What is a tiling problem? Giving two graphs, H and G. So in general it could be graphs, directed graphs, ordered graphs, and even hypergraphs. And H tiling of G is just a collection of vertex disjoint copies of H and G. And we say H tiling is perfect if it covers all the vertices of G. And so the essential problem in the graph tiling is we want to study the sufficient conditions for having a perfect tiling. And a cornerstone result in this area is the Harnel-Samerdy's theorem from 1970, and they proved for a graph G with a minimal degree at least, sorry, my email notification. So with a minimal degree at least one minus one over R times N. And here this condition, this divisibility condition is just the sufficient, a necessary condition for having a perfect tiling. Okay, so once you have this minimal degree, then G will contain some perfect KR tiling. So KR is just a complete graph with R vertices. And moreover, this condition is indeed the best possible because there exists some graph with the slightly less minimal degree that has no perfect KR tiling. So this condition is the best possible. And I would like to spend one minute in here to explain this construction because it was so nice. So the construction is actually pretty easy. We just partition the vertex set into two sets, one set half size and over R plus one. And this set A will be an independent set. And this B will be a complete graph. And in addition, we're going to add all the edges in between. So that is a construction. And you can easily check the minimal degree is exactly this one. Okay, so why it does not have a perfect KR tiling. So let's assume it does have a perfect KR tiling. So this is my perfect KR tiling. And in particular, if you think about a single copy edge, then its intersection with the set A must be at most one. Because if you have two vertices on A, then you have a missing edge, but we want a complete graph. So in sum, if it's perfect tiling, then its intersection with a is at most an over R times one, because what an over R is a number of copies I could have in the perfect title. And this number is strictly smaller than the size of a. So now we have a contradiction because we claim it's a perfect filing, but actually it doesn't cover all the vertices of a. Okay, so that's the harness and ready serum. And for the ease of notation we define this minimal degree threshold, which is the minimum integers, such that for every graph with minimal degree at least K. It contains perfect edge tiling. So roughly speaking the minimal degree threshold describe the worst condition I could have to force a perfect tiling. And the study of the minimal degree threshold for on order graph has been done by cool and all sis. So that's this one. And one of the key parameter here is a so called critical chromatic number. So here F is still on order graph, just the normal simple graph. And the critical command number is defined by this formula. So here, this guy is just a classical command number and the Sigma Sigma here is the size of the smallest cloud or class over all the possible proper in colorings proper colorings with exactly Chi colors. And it's clear this number is not necessary integer because of this fraction, but it's always between the chromatic number and the chromatic number minus one. So it's pretty close to the chromatic number. And what can also prove this for any on order graph as its minimal degree threshold is either determined by this chromatic number for some graphs, or it's determined by this critical command number. And both results are up to some constant. So indeed in their paper they give the food description on the what are the graphs in here, but it's a bit technical so I just ignore the detail here. So anyway, up to here we have a very satisfied results for the on order graph. So it is natural to think about this problem on some other objects. There are some studies on directed graphs and hyper graphs. There are many literatures, but again because of short of time, so I will not mention it. Okay, now it's time to move to our main topic we talk about order graph. In order graph on vertices is just a graph whose vertices has been labeled with this and integers. So naturally those vertices have a linear ordering. And for two order graphs, we say one order graph edge is containing G, if we could find a mapping from h and g such that first, there's two vertices are adjacent, if and only if their pre images are adjacent. And second, I want after the mapping those vertices still keep the same linear ordering. So phi of i is less than phi of j and only i is less than g. And similarly as before we can define this minimal degree threshold for order graph. So let me just repeat the definition here. That is the minimum integers K such that for every graph for every order graph with minimal degree at least K, then it has a perfect order edge tiling. So in order edge tiling just to be careful once you find embedding, we want the vertices to keep the same ordering. So that's the difference. Okay. When we speak of order graphs, there's an important graph parameter called the interval chromatic number. So then this interval chromatic number and the order graph is a minimum number of intervals of the vertex set that edge can be partitioning to such that there's no edge in each interval. So in other words, we want to partition into the independent intervals. So this is kind of variant of the classical chromatic number for order graph. So the classical chromatic number is we just partition the vertex set into independent sets. But here, not only we want the parts to be independent set, but also we want keep them to be interval. So that's the difference. To describe the minimum degree threshold for order graphs. We also introduce a new parameter, this alpha star. The definition is a bit technical that's going to their slowly. First, I will define those alpha parameter iteratively. In this case, by default, we're going to define our for zero plus to be zero. This is just by default. And then our for one, our for one will be the largest integer, such that from one to this number. It is an independent set. So basically we want to take a largest interval here independent interval here. Once you have this alpha one, then you can move on to alpha two, which is the largest independent interval from our for one plus one up to that integer. And you just define the so on. And in the end, when you reach to edge. It will be exactly this alpha Chi plus, because that's the definition of the interval command number I can partition into this many of independent intervals. So that is this set parameter. And similarly we can define this parameter parameter in the reverse ordering. So we start with the largest one. By default, we said our for zero is actually plus one. We define the largest independent interval and denote the endpoints to be alpha one minus. And then you define our for two and so on, until finally we reach this alpha Chi minus. Okay, so we just define this maximum independent intervals iteratively. And then what are my alpha star alpha star is just here you should think about this is an average lens of the first L interval and proportional to H. So we just want the proportion. So this is a ratio which is always between zero and one. So we will take the minimum of this number over both direction. So this is basically the reverse direction, and also over all the L, which is strictly less than Chi. So that is our star. The reason the reason we introduce this parameter is because this actually gives a very nice lower bound for my minimal degree threshold. And that's the next proposition I would say. This result says for any order graph. We could find an ordered graph G with this minimal degree. So slightly less than this one over alpha star times N. And this graph contains no perfect tiling. And in other words, this number would give a lower bound for my minimal degree threshold. The construction is pretty similar to the construction I just mentioned for Harnel's already. So let's just assume this alpha star is actually achieved by some alpha L plus and for minus is pretty similar just symmetric. And we're going to let S equal to this alpha star times N times L, which is equal to this. And now we start to construct the graph in the right side. And so usually when I draw this graph, I really means I would order the graph, I order the vertices in this order, like from bottom to top, that is the increasing order. Okay, so now let's first take the first S plus one vertices, the smallest S plus one vertices. And we're going to partition them into L independent intervals. So each, each interval is independent set, and we will have L intervals and also we want they, we want them to have roughly the equal size. And for the rest of the vertices we just put into one set B. And the edge set will be, we add all the edges between any of the two parts, any of the two, between any of the two sets. And we don't really care about edges inside the B, except we want to satisfy the minimal degree condition. So for simplicity, we just add all the edges in B. So we just add all the edges in here. So you can easily check this actually touch the minimal degree condition. So it remains to discuss why it does not have a perfect hiding. And the reason is also similar as a previous one. So the key is we're going to have this property. That is, if you take a single copy. And this intersection with the first S plus one vertices is at most R for L. The proof used the definition of this parameter. It's easy, but a bit technical, so I just skip the detail. So anyway, we could easily prove this. And then similar as before, if you have a perfect hiding. Then the intersection of this perfect tiling with S plus one will be at most this R for L times a number of copies of edge, which is an over edge, which is strictly less than S plus one. And now we are in the same situation we claim this is a perfect tiling, but it turns out it cannot cover all the vertices in the, in this set. So it's a contradiction. And this type of extremal construction we often call the space barriers. The reason is, you can see here, we fail to have a perfect tiling because we run out of the space for doing for covered this set. So, yeah, so this results gave a general lower bound for this minimal degree threshold for any older graphs. For some older graphs. This is actually the sufficient conditions for having perfect tiling we will talk about that later. But for some graphs, actually they are worse extremal constructions. So it's, it's a behavior is quite complicated. Start from here we're going to focus on the case when the interval chromat number is equal to two, because this case is kind of easier. To before we I state our main result I need the three more definitions. This property ABC. We said a older graph has property a, if it has no edges in the first half of the interval and the second half of the interval. So basically you only have the edges, among those two big half intervals. And it's easy to check once you have this property, my parameter alpha star is strictly greater than one half. property B is for any partition of the vertex set into two non empty intervals. And there's always an edge between them. That's property B and property C. Here this as such is basically the far is the neighborhood of the endpoint edge. And similarly this L will be the far is the neighborhood of endpoint one. So we always take the far is the neighborhood. And in the case that one of those vertices are isolated. So to complete the definition we just define the far is the neighbor to be zero and h plus one for this one. And those property C is actually defined for those two endpoints. And we said, and the points, for example, this, this endpoint edge has property C. If first, it does have a neighborhood. And the second, there is a edge in this interval so from the far is the neighborhood to the edge minus one. This prop three property looks a bit strange right now but it's actually very helpful for us to describe the extremal construction. Okay, next we, that is the main result of our paper. So here for and we determine this minimal degree threshold asymptotically for all the older graph with interval command number two. So that is our main result. I put the result in a diagram form so it's easy to understand the relationship between them. So as you can see here we will have four different situations. So the first case is when this graph has no property a and equivalently this says this alpha star is at most one half. Because if no property a which means I have some edge in the first half of the interval or the second half of the interval. And in this case, this, it is sufficient to having perfect tiling it is sufficient to have minimal degree one minus alpha star plus some error term times that. And this is quite matching to our lower bond because the lower bond is the. So we have this lower bond one minus alpha star times that. So I think totally this is the best possible. And so the extremal construction is just the space barrier I defined before. And the second category is when the graph has property a, but also have property B and also have property B. In this case, the threshold is equal to as a totally equal to one half times and. And the next category is when it has property a, but not have property B. If in addition, one of the end point has property C. Then the threshold is again one half times and. And the remaining case that is when the graph has property a, no property B, and nice of the end points has property C. Then the threshold go back to one minus alpha star. So that is basically this serum give a food description on the minimal degree threshold for this type of graphs. Let's, let's look at this serum for a moment. So first, because of this range of alpha star. That is to say for the first three classes, their threshold they are all above this half of them. But in the last class here because alpha star is greater than one half. So this threshold is actually below the half of them. And for the first class, and the fourth class, and you can easily see this extremal construction, the lower bound is actually comes from the space barrier. But the construction for the middle two cases are different. The reason, so here you can see the threshold is actually same for the middle two cases. The reason I split into two categories because even though they have the same number, but their extremal construction are different. And I will explain extremal construction in a second. Okay. Okay, so first class is when the graph has property a and property B. So, when edge has property B, just to remind you property B is whenever you split into two non empty intervals, there is an edge in between. Okay, so in this situation, the extremal construction will be we take the union of two clicks, and this two clicks has almost the same size. In addition, we require edges not divisible by any of the part size. So that's the only two condition. And that's the union of the clicks. And it's clear the minimum degrees roughly and over to why it does not have a perfect tiling. So if, again, if we have a perfect tiling, then because of this divisibility condition. At least there exists one copy, which must cover vertices from both sets, because it's not divisible by edge. So I must have such a copy. And then because of the property B, I know I should have some edges in here in my copy edge. However, in the construction, there's no edges between here. So it's a contradiction. Okay, and this construction is called the divisibility barrier, because the reason we first have a perfect tiling is this divisibility issue. So that's the second extremal construction. And the third extremal construction is for the graph, which has the property C. Okay, we can just assume edge, the endpoints edge has a property C. And the other one is similar. Okay, and just to remind you property C is this edge does have some neighborhood. And then when you take the forest and neighborhood, and we could find some edge in this interval here. And then the construction will be, we first take interval of this size, and we will keep it to be an independent set. And next we take an independent set of this and over two sides. And because of this the choice of the sizes I still have one vertex left. And I just put it in here. And we will add all the edges between these two sets. And also all the edges between and the second set. So that is all the edges. And you can check the minimum degree is roughly and over two. Okay. And why it does not have a perfect edge tiling. The issue is ended on the single vertex. So if there exists a perfect tiling. And then in particular the end should be covered. And also, in this copy, the end must play the role of edge here, because and is the largest the vertex. So if you want to fit into the ordering it has to be this and has to be this edge. Okay, so the end plays the role of edge, then there should be some vertex place the role of as such. So if you want to find this vertex, the embedding of this vertex, but this is a neighborhood wedge. So the only possibility is this vertex appears in the v2. And now because both you and you prime they have higher ordering than the as edge. So it must be also in the v2. And now the contradiction happens because I know you and you prime there should be edge. But here my v2 is independent set. And this construction is called the local barrier because as you can see, the issue is really for on this single vertex for the single vertex and I don't even have one single copy of edge to cover it. Of course, there's no perfect time. Okay, so now I have described all the extremal constructions. And in the rest of the talk, I will focus on how to prove those conditions are actually sufficient to get the perfect timing. So maybe now it's time to stop for a moment to ask if you have any questions on the statement. And I will take this as no. So I will just continue to the proof strategy. Okay. So, similarly, as many of the previous results in this field, we're going to use absorbing method, which is developed by rhodo routine skin and some ready for finding the expanding in bending and application involves like finding Hamiltonian pass Hamiltonian cycle, and also such graph tiling problems. So the spanning structure. And essential part of this absorbing method is this idea of absorbing set the absorbing set here I denoted by this ABS. And this set has two very nice properties. The first property is itself will have a perfect edge tiling for whatever you actually want you fix in the beginning that you want to study. And also, for any small set L, a very small set, this absorbing set together with. Sorry, again, this absorbing set together with L has a perfect tiling. So that's the two properties of this absorbing set. And also we were uses notion of almost perfect tiling. That is the edge tiling can cover all the vertices, but a very small portion of vertices. So it almost cover all the vertices but not exactly. And typically, the absorbing type of proof will works like this way. So in the step one for giving two graphs. So I choose the thing you want to type into. And G is your ground graph. So for giving two graphs first we want to find this absorbing set in the G and absorbing set should be very small, so that when you delete it. You almost keep the same minimal degree condition. So this is a small set. The step two is, we want to find almost perfect tiling for the remaining graph for G minus the absorbing set. And then in the last step, for whatever leftover vertices from the step two, because here I have almost perfect tiling I would have some leftovers. By the definition of the absorbing set we know the ABS together with L has a perfect tiling. And now if you put the two step the tiling from the two steps together, we will get the perfect tiling for G. So that's the main idea. But as you can see here, this absorbing method is not like a black box theorem you can apply it directly. And indeed majority of the work will be on how to find this absorbing set and how to find the perfect tiling. And the proof for this two step. They are some common techniques you could use in the literature. However, depends on the different action and G the proof often virus. So it's a bit technical and different each time. Okay, so let's first look at the almost perfect tiling part in our application. Back to the literature a little bit for the unorder graph. For unorder graph, this almost perfect tiling has been studied by calm launch going going back to 2000. And calm launch proved that if the graphs has this minimal degree this one minus one over the critical command number, which I define in the very beginning contains an almost perfect tiling. And indeed, this is the reason why this critical command number is important in this minimal degree threshold, because it determine the conditions for almost perfect tiling. That is actually where this definition comes from. The proof, this proof use the regularity llama which is now quite standard in the area. Then the key idea is when we apply the regularity, and we are in a situation that we could have this case set. And they are almost in the equal size. And also each set pair is absent regular pair. So that's the idea situation I just try to sketch the idea. And in this idea situation, we try to apply the regularity. And the first step is, at least we need to find a single copy inside of this graph. And that is easy because by the regularity, indeed, once you have such absolute regular pair, then for any graph with chromatic number K, F is containing GPRI that is ensured by the regularity. And then we can just apply this idea again again, we find one copy we deleted. So we still have absolute regular property. So we do it again, again, until we find an almost perfect tiling. So that is the standard application of the regularity. Okay, now let's try to apply this idea and all the graph and see if it works or some issues arises. So the first problem is, when we try to do the embedding, not only we want to find a relation between the edges, but also we want to keep the same ordering. And this turnouts is easy to overcome. And the way is, let's say I have some graph order of us with interval command number K. What I do will be, I actually first I do some chopping stuff. And after the chopping, I could find some sufficient large subset in each of the A such that those set have a very nice ordering. And here in the nice ordering, I mean, if you look at two set, either one set is they are all greater than the other set, or they are all smaller than the other set. So only have this two cases, either they are all greater, or they are all smaller. So I don't want to interlacing because this kind of make confusing when I try to get the ordering of that. And this step is quite trivial to do. It's kind of elementary. And for example, in the end, we probably in the case that we can find this all during such that all the S1 vertices is strictly less than S2 and less than S3 and so on and onto to ask. Okay, once we had those as set, and now it's easy to the embedding. So because first I claim the set to be sufficient large so I can still use a regularity property. And then the embedding will be for this interval command number K graph, I can just embed its ice interval into the SI. Okay, then, automatically I have I keep the ordering of the graph. And also, because of this is a regular, it's a regular pair. And you can think about it's actually complete bipartite graph between them. So you can find any edges you want. And in particular you will find a copy of judge. So this part is still quite standard as before. So in some it's easy to find a single copy. However, the issue is, you cannot always iterate this process to get almost perfect timing. And for example, so you could have this graph, which is quite simple alternate pass with interval command number two. And we try to apply this idea, we got this epsilon regular pair. And it's easy to find a one copy, which my looks like this. And because my a two might be maybe do this way. So it could be my a two is always higher than a one. That could happen. And then to get this embedding, I always have to take one two vertices from a two and one vertices from a one, because I have to follow relation of the ordering. But now you see the issue is the vertices in a two run out quickly, while they are still a lot of that over in a one. So in and you cannot really reach to the almost perfect tiling. So that's the main issue. And the way we overcome this difficulty is, we use this idea of bottle graph. And the roughly speaking, the bottle graph is we gonna. So this is my bottle graph, I got to put my target graph edge in this bottle. And then my bottle graph is on order graph. So I can apply all this regularity tricks on this bottle graph to get almost perfect tiling. And then inside the each bottle, I asked him to have a perfect tiling. So that's the idea. And let me go to the definition more precisely. First, we had this be, which is some complete multiparty graph. And that is on order as an order graph. And we denote the part size to be you want to UK. And the Sigma is just a permutation of the labels of the parts. And the BT is the standard notion for blow up, which is for each vertex, we blow it up with an independent set of size T. And if there is an edge, then we can add a complete bipartite graph between them. So that's the standard blow up. And the next is a, it's perhaps a quite new definition. We call the interval labeling fight with respect to Sigma. So basically we want to give an ordering on this on order graph. And the way is. So the idea is for each part, we don't really care the ordering inside of the part. It doesn't matter which one is higher, which one is lower. But the most important is, we want the whole parts I is smaller than the whole parts G, if the ordering of I is smaller than the order of G. Basically, you kind of want to group the vertices of the parts together and to order them. And that's why we call the interval labeling because we actually order this piece of intervals. And the order blew up will be we assign this ordering to my blue up copy. And basically, once you took this blew up set. And then you want to group them together to assign the label. So that is the whole set is smaller than the whole set of acts. The whole blow up set of acts is smaller than the whole blue upset of why, if the order of acts is smaller than one. Okay. And finally we reached the definition of the photograph. So what is the photograph for some order graph edge. We said B is a photograph of edge. If for any interval labeling, we can find some constant T such that this order blew up has a perfect edge tiling. So this is what I said before, but once we do almost tiling on the B. And then inside of the B, we want to have a perfect edge tiling. Okay. And, right, so, so once we have this once we find this bottle graph, what are we going to do is we apply the regularity on this on order graph, we get almost perfect tiling. And then by the definition inside of the bottle it has a perfect edge tiling, the older version. And so in put them together we would have a perfect edge tiling. So that is the next theorem. So we showed for any order graph edge. So this is a quite a general theorem for any order graph edge. And if B is a bottle graph of edge, then for any G with this minimal degree. It contains almost perfect tiling. And indeed, this condition comes from the calm large serum. So here you can see calm large says if you have this over this critical number, it has a perfect edge tiling. So basically my condition here is used to ensure my bottle graph does have almost perfect tiling. So that's the usage of this property. So with this serum in the hand. The nice thing is that originally what we need to prove is for every graph. When they satisfy some condition it has the most almost perfect tiling. But now with this serum. The task becomes, we just need to find the optimal bottle graph, because once you find a bottle graph, then automatically you get the lower bound for this minimal degree condition. And you try to search it over all the bottle graph. And once you had the optimal one, and that would be the minimal degree threshold. Okay, so now the task becomes you want to find a bottle graph. However, unfortunately, this theorem does not reduce the difficulty of the problem. Which I really means is that finding the optimal bottle graph is as hard as original problem. So it's, it's kind of the equivalent problem. But, but why we still think the serum is really nice is because, although in general, in general finding the optimal graph is optimal bottle graph is hard. But for the graphs, which was so for the specific graphs. Once you know it's structural properties. Sometimes you might have some intuitive ways to construct this bottle graph directly. So it's hard in general, but for the specific graph you want to study. Perhaps it's much easier to just construct this photograph. So just to show one application here. We actually use it to prove our main results on the graphs with interval command number two. And the way we construct the bottle graph is we're going to use this alpha star. And just recall after star is the minimum of these two parameters. And the way is, we define this P to be alpha star times edge. And edge, we decompose edge into AP plus R. And this R will be the reminder so it's less than P. And the bottle graph will be the complete multi-partile graph with one part of size R and a part of size P. So in total we have edge vertices. And you can easily calculate that the critical command number in this case is exactly one over alpha star. And it still remains to check this P is indeed a bottle graph. But I want to remind you this P now is a fixed graph. We clearly see its structure. And for whatever edge you want to study is also a fixed graph. So two fixed graph, if you want to check if it's a tiling, that is the easy task. You can sometimes you can just do it by observation or when it's too complicated, you can formalize it as a linear optimization problem. So you choose to assign the vertices, you choose to assign a copy of edge to which parts and you just do a little bit of optimization. So it's pretty basic linear algebra stuff. So it's easy to verify the bottle graph is actually a given bottle graph is actually have perfect tidy. Okay, so once you verify it's indeed a bottle graph. And then we apply this and the general theorem here. And we're going to get this is for order graph with interval command number two. Every graph with minimal degree this. So basically here I get it from by plugging critical command number is equal to one over alpha star. So I get one minus alpha star plus a bit error term. And this is enough to have almost perfect tiling. Okay. So that is almost perfect tiling. Absorbing part I try to be a briefing absorbing part, because I don't have enough time and also this part is quite technical. So we had this general absorbing theorem. So although the proof is quite technical but it's actually quite standard in this absorbing method and so there's no new idea, but just you have to do a little bit dirty work. So the absorbing theorem we had is if a graph has the minimum degree, at least one minus one over the interval remember, and then G contains absorbing said we want. Okay, so this is conditions kind of general because we just need this interval command number. Okay, and in particular, in the case that this interval code number is equal to two. We just have this condition delta G is at least one half plus a bit error term time set. So this is a condition for having a absorbing set. Okay, now we try to put the serums AB together to get that one main result. So I just state the main result here. This diagram, and we want to show for this minimal degree, we can find a perfect tiling. Okay, so for the first three cases. In this degree condition, they both satisfy the condition of theorem and B, because this is greater than one half. And this one half is greater than the one minutes of a star when it does not have property a. So basically in this three cases pretty fine the condition and be satisfied we can just apply them directly. So we first get the absorbing and then get the almost perfect tiling and finally using absorbing to polish our almost perfect tiling. The a bit issue is on the last case. In the last case, this minimal degree actually dropped below the N over two. So this means we can no longer use this general absorbing theorem. But the good thing is, in this case, indeed, we know a lot of information on my graph edge. We know a lot on structure property we know it has property a no property B, and neither of the endpoints has property C. And those conditions will be helpful for us to improve absorbing theorem. And indeed, we can have improved absorbing theorem with much less minimal degree condition. And so that's how we solve this case. And I just ignore the detail. Okay, so, so just last a few minutes I will talk about open problems. I will study leaves a lot of interesting open problems. The first natural one is perhaps we. Give a full description on the minimum degree behavior for interval command number two graphs. And it is very natural we think about more autographs like interval criminal number three, or more general interval command number K. To turn out the behavior is actually very complicated. As you can see here, already in this interval criminal number two case, we have three different extremal construction. And I would believe for the remaining graphs the behavior is more complicated. It's a very interesting problem to study. So, can we character characterize the asymptotics of this threshold for all the older graphs. And some tools we can we can still use the our absorbing theorem. Except for some cases we have perhaps need to improve. And still we could use this photograph theorem. To find what is the optimal bottle graph. Okay, and another direction is there are also some studies on determine exact value of this minimal degree threshold. Here we only decided asymptotics, but in did in the literature there for some specific graphs, like the cycles or complete graphs or complete hypergraphs even. And some studies, which care about exact value of the threshold. So, for, I think it will be also interesting problem for all the city. And that's basically all I want to talk today. And thank you for listening and if you have any questions you're welcome. Thanks very much. Thank our speaker in some way. clapping. Yeah, thanks. So, any questions people have. So, a lot of a lot of times there's this phenomenon where if you randomly perturbed the graph suppose you add in like probability and log in over and kind of random edges, then usually the threshold can be lowered into your bank. Do you expect that to happen for this kind of problems. I think it depends on the range of the P. They are actually studies on this tiling problem for random graphs. I know they are some studies and behavior depends on the probability. I guess for some probability, it works pretty similar as this case, but for if you probably drops pretty low then, of course, if you probably is too small you cannot have such spending structure. It depends on the range. It's actually also interesting problem like you think about which range of P have what kind of behavior. So if we add it if we add in like P equals to let's say log and log and over and kind of probability. So, then, is it possible to have like arbitrary small linear, linear, linear minimum degree threshold. Some something like that. I don't know exactly for. I don't know exactly the result but this kind of results in the unordered cases. Yes, there are some sodium random random type you mean the tiling problem right. Yeah, they are there are some things. Okay. Yeah, I can try to find the reference if you want. Other question. I've got one actually. You scroll up to that tree diagram and you have the cases. I don't know the strong sense of how common each of these cases are among the ordered graphs with the chromatic number two, you know, is one of these the more common than others or So, so this case, I think this case is actually the most common case. Because what this really says is in my graph. If you partition the interval into two half intervals of almost equal size, and there's the edge in here. So this is kind of the most common case, but the rest of them they are kind of degenerate sense is because you only have edges between here. Yeah, between us to, and this kind of this case, I would say fewer graphs, I mean, in probability fewer graph is this property but they have more complicated behavior. Thanks. Any other questions. All right, well, in that case, thank you very much for an interesting talk today and we can end it there.


The most exclusive, unique, and breathtaking of all United States destination hikes is the wave. A photographer and hiker's dream, the formation of the wave began 190 million years ago when desert sand dunes compacted and solidified into striped sandstone. Millions of years of wind and rain erosion have uncovered and shaped what we see today. I want a permit to hike the wave, and I'll share with you in this video how you could win a permit, what you'll need for the hike, and everything else you need to know about hiking the wave. On the border of Utah and Arizona, the wave is located in the Vermillion Cliffs National Monument between Page, Arizona, and Kanab, Utah. Before we get into the permits and permitting process, it's important to know how and why this remote hike got so popular worldwide. Before the 1990s, the wave was a local secret and mostly unknown. Sometime in the mid-90s, according to the BLM, a European film crew illegally filmed at the wave and after the release of the film in Europe, foreign visitors overwhelmed the BLM with high numbers and demand to see the wave. And then in 2009, Windows added a photo of the wave to their new operating system, Windows 7, as a wallpaper or home screen, and suddenly millions of people around the world were introduced to the wave. From there, the popularity of the wave grew like a wildfire. By then, BLM had already established a permit system. Due to the overwhelming popularity of the wave, the Bureau of Land Management limits foot traffic to 20 people per day. Everyone must have a permit. There are two ways to win a permit to hike the wave. The first is through the internet lottery on the BLM website. The second is in-person lottery held Monday through Friday in Kanab, Utah at the Grand Staircase Escalante National Monument Visitor Center. The 20 permits are split evenly, 10 through the in-person lottery and 10 through the website lottery. To apply for a wave permit online, start at the Coyote Buttes North Lottery page on the BLM website. Applications for the online lottery open at 12 p.m. mountain time on the first of every month for the chance to win a permit four months later. I will throw a link to that site below the video in the description section for you. Feel free to hit the like button on your way by. It's helpful and easy. In this section here, you will have to choose which dates you want for the hike in case you win. While you choose three days, you can only win one of them. In this section here in this table, you'll be able to see four months ahead and you'll be able to see how many people have applied for each day and how many requests for that day. There are allowed groups up to six people per group. Here's the number of requests for each day and there's still some time left in this month and here's the number of people in those groups. So to better your chances, take a look at those dates right there and then pick accordingly. There's a $5 lottery fee and it's non-refundable whether you win or lose. If you win, you still have to pay the $7 for the permit. Here are some tips to increase your chances of winning at the online lottery. Enter at the end of the month. You can see which days have lower or higher applicants by waiting until the end of the month and it's not on a first come first serve basis. Choose the lower sought after days. This will increase your chances of winning. January and February are the least sought after months. Trying for these will increase your chances. Enter often. You can apply every day for the $5 non-refundable application fee. Keep in mind the application process is for hiking dates four months in the future. The best way to get a permit is to go to the live permit drawing in Kanab, Utah, if you can. I was in the area and took the chance when I won. Half of the permits are awarded this way. Arrive before 8.30 a.m. to submit your application. The lottery for the next day's permit takes place at 9 a.m. sharp. On Fridays, they draw for Saturday, Sunday, and Monday. So it's a great day to go because you got a chance at all three days. Only 10 permits are issued each day and only one person from each group is allowed to submit an application. After all the applications are in, the rangers go through the permit lottery process and draw numbers. All right, here we go for Monday. We have 10 spots for Monday. We're narrowing it down, so there is an odd to get a little better for those that are sticking around. Remember that winning the lottery is only about 20% of your whole process to getting out through the wave. Another 20% is the trail getting from the trailhead to the wave. That other like 60% in between there, that's the road. So keep that in mind. Even though you got better odds of winning the lottery, you're not at the wave yet. Number one. Group of two for Joe. All right, so that makes two down eight to go. Number 19. Yeah, this is my second time. It's a group of four. Let's bring the total to six. We have four spots remaining. Same rules apply. If you are a group larger than four, you will only be able to bring four. So keep that in mind. You can't always pass if you don't want to leave people behind. You have an email or anywhere I can send you some questions. I'm heading in Monday, so just a couple questions after you do it would be great. All right. Number 12. They're not here. Thank you. I just want to see how it goes. I got four wheels. Number 29 is pulled out. All right. Number 22. I drive a Jeep at home. That's it. All right. Well, thank you, everyone. If you did win a permit, please stick around. We will collect fees into a short orientation.  Seven dollars per person and per dog. If you're lucky enough to win a permit like I was, after the drawing there's a prolonged orientation. The Rangers will try to scare you in many ways and might talk to you like you were a child. When I was there in March, the Rangers talked about the road being impassable. They promised that people will have huge towing bills. They said many will not make it to the hike and will have to forfeit their permits. One Ranger even bet his life that people would be stuck. They had also said they had not been in for a month and they had not heard from how people did on the road the day before. So I put those together and decided to chance it anyway. While some of their warnings should be heated about the heat and the hike itself, don't be overly scared about the road conditions. After all of their warnings, I drove in with a four-wheel drive vehicle and never took it out of two-wheel drive. I'm sure the road can get bad, but the reporting of the road conditions should be more realistic.  No. Oh no. I was just wondering if the people yesterday made it in and out. It sounded pretty gloomy yesterday. First off, if you haven't seen the photos, this is photos of what the road looks like. Minus the snow. The snow has melted. But imagine the snow melted on top of the water that's already there. And then with a 30% chance of snow pretty much throughout the weekend, you're going to expect that road to get worse. Tomorrow is supposed to be sunny, but it doesn't mean the road is going to get any better. You do have one crossing. You're going to have to cross that is flowing right now. This is buckskin. It can flow anywhere from two and a half to four feet deep. It does have cut banks on both sides of that crossing. So four-wheel drive, high clearance vehicles are recommended to go out to this area. And if you don't have experience driving a four-wheel drive in these conditions, we would recommend you do not attempt to try to go for the lottery. There is no refunds. There is no rescheduling. And if you do win a permit, you cannot apply for two weeks after that. That list also includes four-wheel drive rentals and includes the tow truck numbers if you need that also, which you probably will. Keep in mind with the tow trucks. It is a pretty high fee to come and get your car pulled out, usually about $800 to $1,000. Did anybody get stuck yesterday? I don't know. I went by the road. I chose not to go on it. The drive is going to be your hardest challenge in this adventure. You may not make it to the wave. I would bet my life that one of the groups in here at least will not make it there on the day of your permit. This is our center in Cannab's over here. What you're going to do is you're going to get on 89, like you're heading towards Page. Page is if you follow 89, Page is all the way over here. This is in Arizona. This Cannab is in Utah. But you get on this, I think it's like 38 miles or so. But you see this really large bend in the road right here?  And you're in between two kind of high ridge mountain chains kind of right there.  And I think there's a sign that says like icy road or something like that, usually in the winter, maybe slippery in the summer. But that's actually the start of House Rock Valley Road. And it turns to dirt right there. And what you're going to do is you're going to take your right off that if you were heading to Page. And you're going to follow that road for about eight miles or so. You got a couple, there's like buckskin gulch, I guess, over here, wire pass to buckskin gulch again. And this is where you're going to park for the wave. Just stay right on that road until you see a really nice pull off on your right, a parking area. And this is a bathroom right here. If you need it, it's kind of, you know, some nice, nice facilities to have out in the middle of the desert like that. But this is where you park. You're going to walk across this House Rock Valley Road into Coyote Wash. And this is like super easy to follow. You could drive a Mack truck down that Coyote Wash. And you're going to follow that for a while. Don't fall for a couple of false trails coming off that like in this area right here. And all until you see this really nice beaten down trail right here. And there'll be like a sign somewhere up in this area right here. And this is actually the wave trail. So if you don't have a permit for the wave, there'll be people that are hiking to have permits to go further out in the Coyote Gulch or other areas. But if you have your permit for the wave, this is where you turn off right here. And this is really nicely beaten down from all the people over the years all the way until you hit the rock. So this is all sand right through here. You can't miss it. You can't lose the trail in this section right here. And until you cross this Gulch or we're going to call it a wash or a valley or a vene or whatever we call it right here. But once you cross this, you're into the rocks. Okay. And then it gets really hard to find and follow the trail. It's not quite as easy as this really well beaten down path that you can see from satellite view. Now you could cross right here like most people do just straight across. It's easy. Or you could walk down this ravine and Gulch and then you'll have a little bit steeper climb here. Either way is fine. I came back somewhere through here on the way out to the wave I crossed right here. And then once you cross this, you're going to want to follow the map that they give you at the visitor center because it has some really detailed pictures. It has some GPS waypoints too. I didn't use a GPS. I just use the map with the pictures. And you can kind of see the footprints.  But for the most part, it's a little bit tougher trail to follow from here on in. And once you follow your map, you know, take some pictures on the way out if you have your camera or your phone of some landmark. So when you're heading back out away from the wave back to your vehicle, you'll have something for a reference to check to see where you turn at each time. There aren't a lot of turns, but there are some. So you're going to follow this, keeping this mountain chain on your right as you head into Arizona. You're going to cross this really nice low sandy area right here, another wash. And then before you know it, there you are. You're at the wave. And basically this is the wave right here, right in this sandstone right here. There's some people on the satellite view taking some pictures of that main picture spot that most people take. And then once you're out there, if you have some extra time, there's some other stuff to look at. You know, there's the mini wave. There's a second wave, sand cove. There's dinosaur tracks over here. You can climb up on top of these high 60 footers or whatever they are. I don't know how tall they are, but there's an alcove, melody arch. There's a really pretty arch over here, Big Mac.  If you leave enough time and you have enough energy after you visited the wave. And then of course leaving, you're going to go the same way out and right there in your car. So all in all, that hike's about, I want to say somewhere around six miles. What should you wear? Definitely wear good supporting hiking boots. You're going to be going over sand, gravel and rocks. There is some light climbing involved and make sure you have good hiking footwear. Depending on what time of year your hike is, dress accordingly. It can get over 100 degrees in the summer and can snow in the winter. Pack an extra pair of socks and bring extra clothing so you can change into something dry if you perspire on the way in or if you need another layer as the sun sets. Dress in layers in the winter as there can be 50 degree temperature swings from daylight to dawn. Also wear sunblocker and or a wide brimmed hat to block the sun. There's very little to no shade on this hike. What to carry? Everyone recommends bringing a minimum of three liters of water. Not being used to that climate, I took six and I was glad I did. It's a day trip so pack in some good energy food. Bananas, granola bars, jerky, chocolate are all good examples and also bring in a lunch. Bring in a camera. The views are so amazing in there you will want to have them forever and maybe an extra battery for your camera. Bring a map. The BLM Wave map is excellent. It had stage by stage pictures to follow that were perfect. It's very hard to get lost with a map like that.  Paces to stay. Both Canab and Page are fairly the same distance away from the wave and both have plenty of amenities. There's several hotels, motels, Airbnbs and even camping areas in Canab, Utah and Page, Arizona. Each town is about 45 minutes to an hour drive on 89 to get to the beginning of House Rock Valley Road. When I visited the wave, I was vehicle camping and I actually slept right here a couple nights. This is a pretty cool place to sleep. It's called the Paraya Townsite. It's just a parking area right off the Route 89 and it was fairly close to the mouth of the House Rock Valley Road right here so I got a pretty good start in the morning. No one bothered me there. I stayed a couple nights. The driver's joined in and we had a great time. There are no facilities there. If you are in the area trying to draw a permit or you drew one for the next day or you travel in early after winning an online permit, I will share with you a few of the things you can do. The hikes and views within an hour or two of the wave are endless and amazing. Here are just a couple of things that I checked out. The Toadstool Hoodoos are very close to the intersection of Route 89 and House Rock Valley Road. Amazing formations also created by compacted sand and millions of years of wind and rain erosion. It's a fairly short and easy hike in. The trail is beaten down into the desert and easy to follow. The antelope slot canyons are in Page, Arizona. They are amazing. There's an upper and lower canyon. They are both pay to play. You must have a Navajo tour guide and the cost ranges from $50 to $100 per person. If I had to choose just one between the upper and lower, I would pick the lower antelope canyon. But it's a close choice either way. Also in Page, Arizona is Horseshoe Bend. This is an amazing overlook of a big bend in the Colorado River. The edge is sharp and incredibly steep.  So be careful how close you get to the edge. There is a new parking fee at Horseshoe Bend. $10 per vehicle. Otherwise it's free to hike in at a very short hike to see the bend. Hopefully that answers everything you need to know about hiking the wave. Please feel free to ask any questions in the comments section below and leave a comment. If this video was helpful or enjoyable, please consider hitting the subscribe button. There's loads of information and website links in the video description below. Thanks for watching and happy hiking.


Hey guys Shaber 1,000 today. We've got a couple different products. We're going to try out for the chainsaw and I thought You guys can review these items with me Stay tuned. We'll be right back and check these things out. Okay guys First thing we've got here. We've got a multi mix pre-mixed gas and oil it's you It's ethanol free and It's ready to use and it's 40 to 1 and 50 to 1 Two cycle fuel. Okay. Now. I usually mix my saws depending when I was in Ohio. I would mix it 50 to 1 in summer and 40 to 1 in the winter But I'm down here in Florida. So I usually mix them about mix my saws and weed eaters about 40 to 1 So this should be all right We're going to give it a shot and See how it runs with this stuff If you guys remember from the last video on the chainsaw not my very last video But the video on the on the pulling chainsaw You know the chain was really dull on it. I've got this. This is just one cheap tri-link It's a chain sharpener. It's just a file now. I don't really need the guard But I could have got the two files For like four dollars. This was like seven something, but I don't have a handle for the files And they didn't just have a handle so I went ahead and got this I figured it'd be good enough to show you guys How to use this it's not it's not a guard. It's a gauge. I'm sorry It's a gauge. I figured it'd be a good video to show you guys how how to sharpen your chain with one of these Save you a little money from having to have it sharpened all the time or going to buy a new $20 chains all the time so But I prefer a chipper chain on certain things, but we're just going to try these two items and see because I got to cut some legs off of a a Guard like a garden planner thing that I built for monkey So I got to cut the legs off. It's too tall for her. She changed her mind after she told me how tall it was going to be When she saw how tall was she said it was too tall so Which I told her it was going to be but anyway, we're gonna cut the legs off of that and we'll see how well this does All right, so let's get the saw up here and I'll show you how to sharpen these sharpen this chain Looks like we won't have to Just the chain a little bit too now the chain It doesn't look too bad. I think it just needs sharp and it feels pretty good Now on these chains, there's actually two sides, okay?  These look like they may be about Well at 30 degrees 30 degree angle, but what we're going to do is we're going to go ahead We're going to sharpen this chain and then and then I'm going to Let me get this turn around adjust this chain Slide the bar out what you do there As you loosen these two nuts and you take a standard head Screwdriver and you turn it and that pulls that out and it tightens it up Whoever remember if you guys remember when I started working on this thing that thing was way too tight So they may have stretched the chain a little bit, but that's no big deal We'll go ahead and tighten it up. Let me see if I can get you a better angle here first Let's get this opened up There's a pretty good instructions on the back This is for 5 30 seconds chain Now if you don't do a lot of cutting this file Long long time probably life of the the chainsaw and then you just Just put that in there Just like that. Okay now you got all these little marks here of which degrees you want it there's Zero degrees and then you got 25 you got 35 and You got 30 over here's 30 So what you gonna want to do if you want it 30 degrees? See that's 90 Let's see about About right here. Yes. This is a 30 degree So what you gonna want to do? Let me see if I can get you up here a little higher I know this is shiny, but I'll get you up here a little higher and zoom it in Okay, now see right here. You got your 30 degrees. I'm on the wrong Right here, and you got your sawtooth right there right here And what you gonna want to do is you're gonna want to hold this Say at 30 degree mark. You want that 30 degree line to be Even you know like pointing towards the chain.   Some of these chains will have like a green link in it or a yellow link This chain does not But sometimes also you can find Where the chain is put together If not, you can put a mark on it So you know where you started if you do one tooth Say ten times you want to do every every other tooth ten times every tooth on this chain if you go five You know five times then you do every two five times Okay, so what I'm going to do But usually you can see You can see where where you have sharpened it. All right So I'm not gonna bore you with that. I'm not gonna speed it up because that's all I'm gonna do I'm gonna do that then I'm gonna spin it around and then I'm gonna do the other the other teeth And then we'll get back with you. We'll put some of this stuff in And we'll take it outside and see see how well it does as you seen from the clip from the other day It didn't even want to go through that stump out front. I had to I filed each one of them 20 times so next time Maybe 10 maybe five maybe 15. I don't know but There's a couple teeth a little A little shaky on it, but I got them cleaned up so If I'm cutting all day Every tank of gas I'll sharpen my chain Something like this I'll sharpen it The first time I you know when I get it out again I'll check it and if it needs it I'll sharpen it before I even use it.  I forgot to sharpen then you got to stop and sharpen Sharpen it every time you get it out. You should be all right. So There you go kind of a Kind of a product review and a how-to. So the file It's just a file A lot of them wear down quicker than any other ones, but for me. I think it's going to be all right If not, I'm going to buy two more files for four bucks. So The fuel Man, it seems to be running pretty good On that fuel still needed just carburetor a little bit, but it's running so good man. I hate to mess with it. So But you can see it it cut right through them landscaping timbers like there were nothing. So All right guys, I'm going to go for now Thanks for watching. Hope you guys had a great Easter weekend And I'll see you soon. Shea Bear the myth man of legend. I'm gone for now. Bye. Bye guys


Start at the University of Sydney successfully held the first day of their two-day strike on Wednesday. The teaching staff walked off the job and formed picket lines outside campus entrances. They were joined by the students as well. The striking staff received widespread support as most other staff and students did not cross the picket line, resulting in an empty campus and most classes being cancelled. The National Tertiary Education Union or NDEU issued the call for this strike demanding secure jobs for the staff and better working conditions. They have been trying to negotiate a new agreement with the university since August last year. The union said they were not happy about disrupting studies but were forced to take this step as the university management was refusing to concede on important work rights. I'm going on strike because our working conditions, our students learning conditions. I'm going on strike because all of us at this university have been working incredibly hard even outside of the pandemic and we deserve a fair pay rise. I'm going on strike to end wage theft and to stop the exploitation of casual staff. I'm going on strike for academic staff's right to research time so students learn from knowledge creators. I'm striking because management constantly restructures first, ask questions later and that results in out of control workloads. The union said that while some progress had been made the university management was refusing to engage on the most important demands. These demands are an end to forced redundancies, enforceable controls on workload for all staff, preservation of the right to a 40% research component in academic workloads, an end to exploitative long-term casualization, recognition and improvement of work from home rights for professional staff, an end to disruptive change management and performance review practices, enforceable targets for Aboriginal and Torres Strait Islander employment and fair pay rises. The Sydney Conservatorium of Music also joined the protest. Dr. James Humberstone, senior lecturer at the university said this was the first time the traditionally conservative institute had formed ticket lines. He stated that a large number of people had turned out in support of the strike because of the increasingly capitalized workforce. The number of people working here insecurely from semester to semester with no route to permanent employment has gone up, he said. On April 28th, at an NTEU meeting, members of the union voted to start an industrial campaign beginning with this strike. The union has said that if progress is not made in negotiations, the members would organize another strike and pickets on May 24th, just before the conciliation week. This action would be focused on First Nation's employment rights.