Tip:
Highlight text to annotate it
X
Welcome to 37 lecture of graph theory, in the last class we were trying to prove a theorem
of Erdos saying that, given an integer k, positive integer k greater than equal to 3
we can construct.. We can get graphs, there exist graphs with chromatic number greater
than equal to k and girth greater than equal to k. There are not short cycle at the same
time, chromatic number is high. So, as we explained in the last class these two requirements
are somewhat contradictory to each other, because when you say there are no short cycles
at least, when we look from a single vertex, select a vertex and look around it look like
a tree to some distance and it may seem that you can color it color it with very small
number of colors. So, the.. it is a natural question to think
whether, we can have all the cycles greater than or equal to some number k. given number,
you can fix a number k may be thousand or something like that. And then ask, can I also
have the chromatic number high? Typically dens graphs are high chromatic number so,
it may look like there are small cycles in it. To begin with, one may see that, see,
one may feel that how do you make a graph with high chromatic number? So, we will say
that if there is a big clique in it clique in it then you can have chromatic number high,
because the chromatic number is always greater than equal to that clique size, maximum clique
size. But, then if someone asks suppose I want to make sure that, there are no big cliques
in fact, there are not even triangles. Three cycles themselves are not there triangles,
three cliques themselves are not there, then, can we still have the chromatic number high?
So, it happens that, there are some constructions you have seen earlier, construction and some
examples we have seen, where how we can get such graphs.
After that, of case it may look like it is, the cycles it is not just three cycles may
be five or four cycles also, five cycles also, some up to k minus one length cycles I avoid,
make all cycles large. Then, it is it possible that I can always color the graph with few
number of colors like a constant number of colors, or something like that but, it so
happens that however large case you can get a graph with the chromatic number also greater
than k, you can always make it large, both of them together large, this is what we are
trying to prove. So, our approach was to use the probabilistic
method, as we discussed in the last class so, it was not so straight forward it is not
so straight forward to use probabilistic method here, because our strategy for showing that
the chromatic number of a graph is high is by showing that, there are no large independent
sets. So, for instance if you want to show that the chromatic number of a graph is greater
than equal to k, we will show that, there are no independent set in the random graph
or there exist a graph that, we will say that there exist a graph that, with the biggest
independent set size less than equal to n by k so that, the chromatic number becomes
n by n by k, that means k greater than equal to k.
To show that the typical strategy is to pick up a random graph, so from the g n b, g n
P distribution one picks up a graph, and then one probability that, there exist is an large
independent set independent set of cardinality greater than equal to n by k in it, and then
we show that the probability is very low, tends to zero, tends to infinity, very low
less than.. we need only less than half for our purpose. So this is what, so but, then
we have to fix the probability P correctly, that the intension here is to fix the probability.
You know If the fix this, if you fix this probability high like half or something like
that, it would be easy to prove the statement but, then you want to keep it low why, because
if you put half, or one by four, or some constant it is likely that the graph we draw is from
the distribution is dens the excepted number of edges is half of in choose to.
So therefore, it is like it to be dens but, here we cannot have cycles so, if you want
avoid cycles the probability of picking an edge has to be kept quite small. And if you
if you work with it, you will see that the probability has to be quite small about constant
by n, so we have to keep this probability so low like a constant by n but, then it show
happen that if you pick up this probability to be g n P, that P is to some constant by
n, this will not happen, we cannot make sure that, there is there are no independent set
of cardinality at least n by k. So, this range of probability for this for
one of the things happen with high probability, does not match with or does not intersect
with the range of probability for with the other requirement happens with high probability,
with some reasonable probability so that we can add the bad probability together and show
that it is less than one, that is our strategy. Now, so that here we need a little trick rather
than directly attacking, getting the requirement we would rather get a requirement, get a condition
which is very close to the requirement of having no short cycles, and then we will make
some corrections that is our plan.
So that, yesterday we proved, we accessed it access it clearly what should be the probability,
how small I can make the probability so that, I can make sure that, there are no large independent
sets. For instead, instead of asking for independent sets of n by k, should not be there we ask
n by 2 k, should not be there, that is little technicality we will understand it latter.
So, we were rather ask for I want the probability that the randomly selected graph contains
an independent set of cardinality greater than equal to n by 2 k, should be quite small.
So if you take any probability value greater than or equal to 6 k log n by n, then we can
easily show that sentence to infinity this probability that we do not like, this event,
probability of this bad event will tends to zero, this will becomes zero. In other words
if you take n large enough, we can make the probability of alpha being greater than equal
to n by k, to be less than say half, that that is what will need latter.
So, this is the key point the probability that.. yes, if you keep the probability high
this will definitely be happening that means, this probability will indeed tends to zero
but, then there would not be any large independent sets but, we are exploring how small you can
make it, the probability value. So, we see that 6 k log n by n, is a is the smallest
we can count, so with respect to this calculations without so assuming that, this is the kind
of sophistication that we can go with the calculations involved. So but, unfortunately
if you fix this probability P equal to this, there are short cycles, there will be short
cycles the probability has to be even less to avoid short cycles so, our technique is
this, is what we are going to prove this statement, the technique is this, so what will do? We
fix the probability a little higher that means (of case) higher than, this probability here
the 6 k log n by n but, little higher.
So, how we select this little higher is u of k, the k is given with the problem, we
want to avoid cycles of length less than k and have chromatic number greater than k.
So, what we do is we fix on epsilon in between zero and one by k, in between zero and one
by k, and then we will fix the probability to be P equal to n, raise to epsilon minus
1, so that is our probabilities taken to be in between zero and one by epsilon to be..
epsilon to be, some epsilon value to be less than in between this and then probability
value P is equal to one by n raise to 1 minus epsilon, you can also write it n raise epsilon
minus one, because so, this is the value. One good thing about selecting this probability
is this probability is bigger than the 6 k log n by n value that we found for the other
event happens, that means; there are no independent set of cardinality at least 2 n by n by 2
k. So, this is bigger so this will happen if
you.. with high probability. So, the with high probability they would not be any independent
sets of set of cardinality 6 k by n, cardinality n by 2 k. Now, we see what we achieve by this
things is as we, I have already discussed if you fix this probability is already too
high we cannot avoid all short cycles but, we would rather make sure that the number
of short cycles, if you take this probability would be small enough, how small? We will
show that the number of short cycles can be made less than n by 2, with high probability
less than equal to n by 2, n being the number of vertices this is what we are going to do.
So, how do we do this things? So, let us look.
So, will define like we are going to use the concept of expectation here therefore, we
need a random variable. What is the random variable? Let X of G, denote the number of
short cycles of length at most k, so length at most k means it can be 3, 4, 5, 6 up to
k minus 1, k also let us say at most k. So, k of G denote the number of short cycles in
a randomly non graph G element of G n p.
Now, we had done this exercise in the last class, how much would be the expectation?
We had seen that, if we are looking at the expectation of I length cycles, if we looking
at the expectation of I length cycle that will be n P i into n P i by 2 i, 2 i into
P raise to i, this what we had seen so, we can we can make a comfortable, so we can write
it this n P i can be written as n i, is another notation find P i, n i by 2 i into P raise
to i be that probability of G n P, this is, this P, P raise to i is in it so, because
you know to remind how it was done, the expectation of X is calculated by observing that, this
random variable X can be seen as the sum of several indicator, random variables there
each of this X i will correspond to an indicator random variable which says one or zero depending
on whether the possible cycle will occur or not, we had discussed it in the last class,
we would not repeat it.
So this therefore, and, because each of this expectations by linearity of expectation,
because there are n, n P i by 2 i of n here, and then P i, P raise to i was the probability
of this being one therefore, the expectation of X i was P i, P raise i, so when you some
up you got this things, this is what we did in the last class so, I would not repeat it
now. But, the only difference is here we have to consider all lengths from 3 to k, it is
not just one possible length, we have to consider all the lengths up to k that means 3, 4 up
to k, so that is why we are summing up again, because as we can see we can, we have all
kinds of.. so, we can see that it is takes expectation for the number of i length cycles,
i equal to 3, i equal to 4, i equal to k. So, k different random variables are defined
and then if you some of this those things to will get this.
So therefore, to get the expectation of this you can some of the expectation of this separate
random variables for each i, and then, that is why we get this. And then in you some of
these things what will you get? Because this n choose i, is actually can be upper bond
by n raise i, n raise i and this is P raise to i, 2, 1 by 2 is 2 is taken out, and this
i can be discarded, because we are just taking upper bound so it is at least three on words,
so we can discard it, so this is at most half of sigma i equal to 3 to k, n raise into P
raise to i, and this n raise to.. there are how many terms here, because we are going
from i equal to 3 to k, there are k minus 2 terms here and each of this term is upper
bound by biggest such term say, namely n raise to k, P raise to k, because you see this we
can see that n raise to k, P raise to k will be greater than or equal to n raise to i,
P raise to i for i less than equal to k, less than equal to 3. Why is it so? Is it is it
possible that, this somehow decreases in after some, at some point. So, for instance i somehow
thing were whereas, we increase i this should be, this should grow that will grow, because
this n P is equal to n into 1 by n raise to 1 minus epsilon is equal to n raise to epsilon,
is greater than 1, this is quantity greater than one by assumption therefore, so we are
assuming in this large enough so that, this is greater than one and so this will grow
so therefore, n raise to k, P raise to k is indeed the biggest term among the n raise
to I, P raise twice, n raise to i into P raise to i, therefore, we can substitute it with
that, half of k minus 2 into n raise to k times P raise to k, will be the upper bound
for this.
Now, we ask what is the probability that the random variable gets a value greater than
equal to n by 2, here so, here is an equality so, this X is a random variable with all positive
values, because this is the number of cycles it can be 0, 1, 2, 3 up to all positive, no
negative values so we can use that Markov inequality. In the last class we had just
discussed the Markov inequality, what was that? It was, we told when this random variable
is positive then the probability of this being greater than equal to a, is less than equal
to expectation of X divided by a. We can use the expectation to get a upper bound for the
probability that, X is greater than equal to a. We just it is very easy inequality so
last time we discussed the proof of there also.
So, and then now, we can use it here a becomes n by 2 therefore, expectation of X by n by
2, what you do is? You substitute for the expectation here namely k minus 2 into n raise
k minus k divided by n, because n minus k by 2, this half will cancel with half here
n by 2, and then P raise to k is here, so that is k minus 2 into substitute for P is
equal to n raise to 1 minus epsilon, so we can calculate that so here.
So, let us k minus 2 into, n raise to k minus 1 into, P raise to k equal to k minus 2 into n raise to k minus 1 into
P is essentially 1 by n raise to 1 minus epsilon, when a multiply by this k into k minus epsilon,
so this n raise to k will cancel there is a minus one here, so this minus k epsilon
goes up so, that is k minus 2 into n raise to k epsilon minus 1. Now, this epsilon was
less than 1 by k therefore, this quantity is going to be less than 1, so this is k minus
2 into some quantity which is which is n raise to some negative quantities say 1 by n raise
to something here suppose to quantity. So s n tends to infinity definitely this will
tend to zero.
So therefore, we assume that limiting value and n tends to infinity, probability there
X greater than equal to n by 2 zero. Now, which means that if n is large enough, you
can get there this probability is less than equal to half, less than, strictly less than
half. Similarly, the earlier probability namely the probability of having an independent set
of cardinality greater than n by 2 k also can also tends to zero, tends to infinity
so, as if n is taken sufficient large you can make it less than half their. So, without
difficulty we see that for sufficiently large n the probability that, there exists a independent
set of cardinality greater than or equal to 1 by 2 k, is can be made, the probability that, this happens
can be made less than half and also the probability that our X being greater than equal to n by
2 can be made less than half. So, when you sum up these probabilities that
is; we will get the probability that, at least this or this one either this event or even
this even happens one of them happens. So, that will be strictly less than one the probability
therefore, there exist probability non zero probability that we get a graph there exists
non zero probability that, we our randomly drawn graph has at most n by 2 short cycles,
and there are no independent set of size cardinality strictly greater than equal to n by 2 k, so
that means chromatic say n by 2 k the independent set is set size is small.
Now, what we do is? We take this graph there exist one so we can take of that graph, so
there exists a graph we are not looking for efficient algorithm but, there exits one therefore,
suppose we take it we get it and then we know that, there only n by 2 cycles. If you remove
one vertex from each of these cycles, all the cycles will be broken, all the short cycles
will be broken, there would not be any more short cycles but, the number of vertices in
the graph will reduced known now to n by 2, because you are you may remove n by 2 vertices
in this process, you may remove 1 vertex from each of the at most n by 2 cycles, so you
may remove the maximum n by 2 vertices so you will have n by 2 vertices left.
Now, because you remove vertices you would not increase the independent set size, it
is still less than equal to n by 2 k so but, the number of vertices have reduced so the
chromatic number of this graph is greater than equal to n by 2, by n by 2 k which is
greater than equal k, as we want it. So, we got a graph without short cycles, whichever
short cycles were there in the graph destroyed by carefully removing 1 vertex each from each
of them, because we could do this, because the number of short cycles were only less
less than n by 2 that is why we could do that. And then, because we did not have any large
independent sets even n by 2 k sized, n by 2 k sized therefore, even if the number of
vertices of reduced little bit, chromatic number has still to be high, because you remove
divide by this then we get lower bound. So, we got a graph with both the required
property, this is what the key thing to observe in the proof is that it is even if we wanted
two properties to happen but, then there was not probability range which would ensure that
with high probability or with some probability both of them will happen, it was, which was
not possible able to do by the calculation that we do therefore, we allowed a little
bit that means; we told I am looking for graph without short cycle but, I will allow if you
short cycle so happens, as long as the number of short cycles are small, here at most n
by 2 and that was possible in the in a range we could find a probability range both of
these happens independent set size are also not big, and also the number of short cycles
are small enough. And then we processed it, because the small errors in the kind of the
property we are looking for it is deviating it from in a small way so, we corrected it
by breaking all the short cycles and then, we still had the property of no big independent
sets the number of vertices have reduced little bit but, still, because the independent set
sizes were quite small the chromatic number of the graph has to be still big that was
the argument, that is the argument.
So now, we will consider so, that is so, this is enough for introducing the probabilistic
method. So, we first problem was about the.. about getting lower bound for the Ramsey number
it was very straight application, we just want 2 proper properties, 1 was to avoid large
independent sets and the other was to avoid large cliques so, we found the bad events
namely there exists independent set, we found the bad event the other bad event namely there
exist large clique, and then we found the probabilities of that and then we added the
these probabilities together to get an upper bound for the probability that one of these
bad events occur, and then, because we could show that, this probabilities together will
be still less than one, because each of them were less than half we inferred that, there
exist probability for the good event to happen that means; none of the bad events occur,
that was a very straight forward applications. Now, this previous example was more tricky,
because we could not make that happen directly so, we rather changed the property that we
will looking for little bit assuming that somehow, planning that later we will we will
correct for the change, that was it is a trick there so, that was a tricky applications of
probabilistic method. Now, we will quickly look at some other aspects of random graphs,
rather than proving some structural theorems we will look at some.. How.. Some results..
regarding random graphs themselves can be obtained without here, we proved the G n P
model to proves some theorems which essentially as nothing to do with randomness, it was finally,
when the results did not have any randomness in it but, here we are going to say something
very different this about the random graphs itself the probability distribution itself
here. Let us look at what a graph properties, let
P be a graph property, when I say P it is a class of graphs closed under isomorphism
that means; if a graph is there all the graphs are isomorphism also there in the set, so
any usual property that we are considering for instance the property of being connected
is a, you can see as the set of graphs which are connected, all graphs, if a graph is connected
all graphs which isomorphic to it or also connect therefore, that is what a graph property
we can say that, a graph property is just a class of graphs closed under isomorphism.
Now, you take any function P of n, if G element of P tends to 1, as n tends to infinity for
instance you just consider G and P model, and then suppose you have P, some P of n some
functions fix it, and then if it so happens that the probability that, that the randomly
drawn graph has the property desired property P, that tends to one as n tends to infinity,
one large number of vertices then we will say that, this property is there for almost
all graphs so, g element of this property for almost all graphs, for almost surely g
has this property like that. And the equivalently the other terminologies also used namely suppose,
the probability that G has this property when graph is randomly taken from the G and P distribution
probably see space so, then you if this probability tends to zero as n tends to infinity, we will
say that almost no graph element of G element of G and P has property P, are almost surely
G does not have the property.
So therefore, this is the common this is the common terminology that we use within this
area of random graphs, almost surely some properties there, almost surely does not have
the property like that. Now, for every constant.. So we will we will considered an example some
easy example for this, thing so it is show, it show though it is almost intuitive obvious
we will take a smaller example, for every constant P element of zero you take a fix
a constant and every graph H, almost every graph G and P contains an induced copy of
H, how do we prove this? So, you can fix a H, so H may have say cardinality k, k vertices
in it. Now, n is taken large compared to k, now you
can, what you can do this is the randomly drawn graph, what you do is can think of it
as several group of n by k vertices, this, there are n by k vertices here, you can even
this n by k vertices here, we will say k vertices here, k vertices here, k vertices here so
these are disjoint. We partition the n vertices into several k groups, we get around n by
k, we can get at least n by k disjoint such collections now we say that, what is the probability
that, this k vertices contains H that means there exist in graph here this graph is isomorphic
H, that probability is of case you can match an all possible ways so there are, we can
map there are the vertices of these 1, 2, 3, 4 on it can map to this in say k factorial
ways.
So, and then, for each of them you can see whether isomorphic or not, some so though
all the cases so we can count, whatever it is the you can see that the probability will
not depend on n, whether this has appeared it or not. So, this is some function are which
only depends on the probability will be some r which only depends on k does not depend
on r, so the probability that, this does not have an isomorphic copy of H will be at most
1 minus r now, what is the probability that, this does not have, this also does not have,
this also does not have, this also does not have, none of them has so these are all independent
events, because this is one.. What is happening here will not affect what is happening here
in the sense that, the edges here are totally different from the edges here.
So, we can multiply this probabilities so it will become n by k, this will be the probability.
And as we can easily see this probability will tend to zero, as n tends to infinity
if we take, because is a r is a number which is less than one anyway, because it is a probability
that is therefore, and therefore, you can see that as n tends to infinity the probability
that H is not isomorphic to any sub graph of G, will tend to zero, any sub graph of
G, will tend to zero. So therefore, we can say that almost surely G a randomly drawn
graph G will have the property that, a fixed graph H is as occurred as a sub graph of G
so, contain such as sub graph this is just to illustrate that terminology that almost
surely some property occurs, almost surely some property does not occur that is all.
We just want the probability to tend to zero as n tends to infinity so nothing more than
that random. And now, see the.. now there is a this interesting concept of threshold
functions that we want to introduce, some properties or such that, the there are certain
threshold that means if the probability we select P is a little above the threshold and
then almost surely the graph will have that property, and if the probability that we select
for G n P is little below the threshold then almost surely the graph will not have that
property, the graph will not have that property so the, so, more formally I have written here.
So let say t equal to t of n is function of n, and t of n is not equal to zero for any
of n, and we say the threshold function for a graph property P if the following holds
for all P equal to P of n, and G element of G n P. So, what should happen? See, if P by
t tends to zero so, this is a way of formalizing, when I say P is a little above t so, when
I.. I can say that by saying that P by t the function P, such that; P by t tends to zero
as n tends to infinity. Which means, is not exactly this more than but, it is a little
is a function wise little more than, that the t is the function of n, P is also a function
of n, if n tends to infinity is will tends to zero so, here if tends to zero it means
that, this is smaller than, this this slightly smaller than, this some this formal way of
telling if limiting value of n tends to infinity this, if this happens it means that P of n
is slightly, it qualitatively intuitively slightly smaller than t of n.
So, small below threshold, if this happens our property should be, should not be there.
So, that means G should not be should not belong to this thing with high probability,
the probability that G does not belong to see should be one, our probability that G
belongs to P should in to one, it tends to infinity or tends to zero this is what we
want so, that what we are saying. On the other hand if P by t tends to one as n tends to
infinity that means; P is above the threshold function then we want the limiting value of
G element of P to be one as n tends to infinity, the probability that G elements of P should
element of P that means G has the probability, G has that property should tend to one as
n tends to infinity then, this is called a threshold function.
So, this is interesting phenomena that occurs in the context of random graphs, it so happens
that several properties have this a feature that means, it has a threshold function in
the change from almost all graphs not having that property, to almost all graphs having
that property is abrupt. So, it is not that very specific value but, it is a you can capture
it this way like P by t tends to zero as, that P is above t, P by tends to below t,
P by tends to P by t tends to one, as n tends to infinity means it is above t, this way
we get a let get a threshold function for many of this interesting properties for connected
as for most of the properties that we studying. So, especially the there is a theorem that
if the property monotony and it will it will there will always be the threshold function.
So, we will quickly see, so our, because we do not have much time to spend on random graphs
maybe we can maximum spend one more hour therefore, we will quickly see one example, because we
are interested now how to show some threshold function for certain properties. What are
the techniques? So, today a today our intension is to introduce one method to prove the threshold
functions. So, the therefore, we will.. this is called a, we will introduce this method
is called second moment method so, for instance we consider a graph property of the form G,
such that a random variable X of G is greater than equal to one, for X of X is greater than
equal to zero is a random variable. So we see, when we say random variable on graph
most of the time we consider a positive integer values, non negative integer value, random
variables for instance in the case of connectedness it can be the number of spanning trees, if
it is a disconnected graph there is the number of spanning trees as zero, if it is a connected
graph the number of spanning tree is a greater than or equal to one, one or more can be many
more but, this this zero or not will decide whether connected or not similarly, we can
we can have many other possibilities. So, you can define the random variable accordingly
and make sure that the property that we are looking for is captured by whether the random
variable is zero or one or more. So, because I am saying if it is one or more then the
property is existing, if it is less than one that means zero, equal to zero then the property
is not existing so, this this way many property can be captured. So, we will look at this
kind of properties now so we told one example connectedness so similarly, other examples
can be cooped up so can be seen. So, the question here is, because quickly
looking how will we prove that such a property has a threshold function? This is what can
be an approach, what can what can be an approach so, this is.. What this is where we use the
second moment method. See, one easy observation is that you can use this expectation suppose,
if we can somehow show that the expectation of X this random variable will tend to zero
as n tends to infinity, if n becomes large, if the expectation tends to zero then it definitely
means that the almost all graphs have the property P, because the property P is captured..
if the property, almost so, I should say if the property P capture is captured when g
of G is random variable has value greater than one, then we should say that almost no
graphs or the other way, as we define almost no graph have property P that is, because
of the Markov in equality, because the probability that X greater than equal to one is less than
equal to expectation of X by one by Markov inequality, as we have seen so this will immediately
tell us that.. yes, this will immediately tell us that so, if e of X is tending to zero
then, this probability that X greater than equal to 1 will also tend to zero, because
this is even less than that let as n tends to infinity.
So, that is one way of showing that so, if you take a certain G n P may be P by t is
less than it tends to zero, n tends to zero this is one way you can try to show, we just
try that then expectation of X also will tend to zero then immediately there but, on the
other hand can we use the same technique show that the probability of X equal to zero, tend
to zero that means; when you want to show that this this probability is high that means,
small it is approaching one we may want to show that the probability of X equal to zero,
tends to zero but, if you simply show we should take the expectation, and show that with the
some lower bound and very high probability that want be enough, because it is possible
that some random values, some this random variable will may take some very high values
for certain things, and then almost all the time it may be zero but, when it is taking
some other values it may be taking very high values therefore, that may be the reason why
the expectation is has lower bound, because expectation is summing over all possible values
and multiply with probabilities.
So, that is not enough that way so that is what so, the we need some other technique
to do this thing, for that purpose we need some tools from some more information from
the probability theory so to show this thing so, to repeat what we have told now is that
when we want to consider this case the probability of X great than or equal to 1 tends to zero,
if P such that P by t tends to zero, that means P below threshold then the technique
one technique if at all it works, it can be to make use of the Markov’s inequality,
because this less than equal to expectation of X by one, that is expectation of X. And
you try, because this here expectation of X gives a upper bound for this thing you try
to prove that if this happens this will tends to zero then this will tends to zero.
So, on the other hand we will have to, if t is threshold will have to prove that when
P of P by t tends to one, the probability that X great then equal to 1 tends to 1. That
means probability that X equal to zero tends to zero. Here, as we told expectation will
not work, because just showing that expectation is will not work so, this is this need more
ideas so what we going to do is to use something called the variance. So, let us define the
variance sigma square of X, sigma square is equal to expectation of X minus mu whole square,
somehow some sense we have this expectation for random variable each value the minus in
mu so you will get a different random variable X minus mu there, and it was squaring these
things and then taking the expectation again that is, that is the this thing it is a quadratic
measure of how much the random variable X deviates from mean.
So, the another thing so very easy, easily you can derive that sigma square is equal
to expectation of X square minus mu square. How you do that? So, this is easy because
expectation of a sigma square is essentially expectation of X minus mu whole square, so
you can expand it if this is X square plus mu square minus 2 X mu so, because of linearity
of expectation this becomes expectation of X square plus expectation of mu square will
be mu square, because constant minus two times expectation of x into mu, that is expectation
of X square plus mu square minus 2 mu, that is expectation of x square minus mu square,
this is what. So, this is an easy thing so, this will be useful in calculations and now
another thing regarding expectation the variance sigma is another inequality which becomes
very useful the chebyshev’s inequality.
So, say this deviation the absolute value of the deviation x minus mu, going greater
than or equal to, that means it deviating too much from the mean is mu greater than
or equal to lambda is less than equal to sigma square by lambda square, the proof of thing
is also like Markov’s inequality this very easy, because so, because if you want to look
at the probability of X minus mu, absolute value being great than lambda definitely you
can see that, this is equal to so, if you just square it so this is, this now, this
is less than the expectation of X minus mu whole square this being considering this has
a different random variable say y, this is expectation of y divide by this quadratic
a lambda square but, this is part this is essentially sigma square so, we get this sigma
square by lambda square so this is immediately following from the Markov’s inequality just
substituting.
So, we just considering the new random variable inside of expand X, we just taking a X minus
mu whole square so this is, becomes lambda square and, because the expectation of X minus
mu all square sigma square this will come anyway. So, this is all tools from the probability
theory and then now, here this statement this this small lima help us to do the trick. So,
you want when you want to say that see the probability that X G zero, indeed tends to
zero, what essentially we want to say, because whenever to a graph has is equal to 0 and
the random variable takes value 0, it means that difference absolute difference from mean,
absolute value of the difference it mean is equal to mu, because it is zero, zero minus
mu absolute value is mu only so, the probability that X equal to zero is definitely less than
equal to probability that absolute value of X minus mu great than equal to mu, again you
can use the Markov ’s inequality here once again. So, that will be sigma square by mu
square if this tends to the sigma square by mu square tends to zero, as n tends to zero
then, this will this will also tends to zero, and then therefore, probability X equal to
zero also will tends to zero. So, instead of directly attacking probability
of X equal to zero, we notice that, this X equal to zero corresponds to X minus mu absolute
value equal to mu, so this probability should be definitely at most a absolute value of
X minus mu great than equal to mu, so this in the chebyshev’s inequality so we, in
the chebyshev’s inequality we have to take the take lambda for mu here, instead of lambda
we have to put mu so sigma square by mu square, that will, that is why sigma square lambda
square instead of lambda we are putting mu here, So, that is why now the good thing about
this inequality that we just have to check to prove this the probability that X equal
to zero, tends to zero we just have to verify whether this tends to zero, so the for our
case where the random variables are greater than equal to zero any way.
. So, this as we just have to verify sigma square
by mu square whether, sigma square by mu square will tends to zero. So, this is this is the
technique so, this is second moment method so we will illustrate it with one example
namely the next one example, will so this is, lets again consider the property of so,
where H is a fixed graph P H be the property of containing a copy of H as a sub graph that
means, randomly drawn graph what is the probably H is a contained as a sub graph, that is the
that is the property we are interested in H should be present as a sub graph in g. So,
and we can take a special kind of edge H is called balanced if this epsilon of H dash
is less than equal to epsilon of H 4, all sub graphs H dash of that what is this epsilon
of H? When I say epsilon of H that is the number of edges in H E of H cardinality, divided
by the number of vertices in it n, the number of edges divided by the number of vertices
in it H this is epsilon. Suppose, if you take any a sub graph of H
if it so happens that every sub graph has this epsilon value lesser or equal, that means
it is a kind of this will be less than or equal to epsilon of H, in that case we will
say that it is a balance some sense says that, the they are no very concentrate it portion
inside the graph so, the biggest graph captures the maximum edge density so, all smaller graph
to have at most edge density will be at most as much as the graph this is the property
of being balanced.
Now, let say property of being balanced and now, see to understand what is this balance
why we are considering balance graphs that is, because many of the simple graph are balanced
for instance you can think of a cycle so, if we consider a cycle so you how many simple
cycle 1 k l, k l link cycle C k so, there are k edges and then, there are any sub graph
if you consider so the epsilon will be k by k one, any sub graph if you take it will be
maximum of path or collection of paths therefore, definitely the epsilon the edge density that
is smaller, because the edges are less than the number of vertices there therefore, that
is some example so when we can see that it is not very surprising that, this balance
graphs is considered, because many graphs are already captured by that.
Now, we will prove a theorem that if H is a balance graph with k vertices, and l greater
than equal to one edges, there l edges and k vertices in it then the threshold function
for it is n to the power minus k by l. This is what will prove for incense if it is a
cycle then it will become n to the power k by k, that is n to the power minus one. If
it is a small tree on k vertices there are k edges, and k minus.. k vertices, and k minus
1 edges so n to the power k by k minus 1 will be a threshold function for the property of
as thing.
So similarly, if you consider a complete graph what will happen there are k vertices k, k.
k vertices and k choose to k into k minus 1 by 2 edges, this is by after cancelling
this is 2 by k minus 1 so, we will we will we can put it as threshold function as t of
n is equal to n to the power 2 by k minus 1. So we will prove this thing as so we told
2, 3 example to illustrate that this is a useful theorem, because many of this cases
it simple cases like trees a cycles, complete graphs all are balance graphs therefore, when
they are coming as a fixed graphs, then we get the threshold function easily using plugging
in this formula, because k and l can be valued and substitute so, this general statement
we will proof tomorrow in the next class, so that is.
Thank you.