An attempt to find expected value of clique number of special random graph Let $G(n)=(V,\mathcal{E})$ be a random graph definded as follows:
$V=[n]=\{1,2, ... ,n\}$ and for all $i,j\in V$ so that $i\ne j$ we have $\{i,j\}\in\mathcal{E}$ with probability $p$. Where $p\in[0,1]$
So i was trying to find expected value of a clique number of a $G(n)$:
$X(n,p)=E[\omega(G(n))]$, where $\omega(G)$ is a clique number of a graph $G$
Here is my attempt:
Lets call $G(n)$ a previous graph, we create a new graph by attaching a star to the previous graph.
$\omega(G(n+1))-\omega(G(n))=\begin{cases} 1, & \mbox{when additional star is connected with a clique in previous graph} \\ 0, & \mbox{otherwise} \end{cases}$
Lets denote the first case as a $A$.
So if we put expected value we will get the following: $X(n+1,p)=X(n,p)+P(A)$
The problem is to find $P(A)$.
Here is my idea:
We can associate to the graph $G(n)$ a clique matrix, which is matrix that columns corresponds to vertices of a graph, and rows corresponds to cliques. All the rows has exactly $\omega(G(n))$ ones and $n-\omega(G(n))$ zeros. If we pick some columns (this is attaching our star) then we would choose some rows of this matrix with some probability. This probability is exactly $P(A)$
Any ideas how to find $P(A)$?
Regards.
 A: Not an “answer” in that this post has no original thought, but too long for a comment.
As Yuval Filmus notes, this is in fact the standard (and most studied) model of random graphs, and it’s called the Erd\H{o}s-R\’enyi model.  If you can’t find information on the clique number, then search for the independence number of the Erdos-Renyi graph (which is distributed exactly the same as the clique number of $G(n, 1-p)$).  That might google better for you?
These parameters are now very well understood.  In short, let $k_0$ be the largest value of $k$ for which ${n \choose k} p^{{k \choose 2}} \geq 1.$
Then the clique number of $G(n,p)$ is essentially equal to $k_0$ (so its expected value is also essentially equal to $k_0$).
By “essentially equal to,” I mean this in a very strong sense.  For instance, if $p=1/2$, then with very high probability, the independence number of $G(n,1/2)$ is between $k_0 -3$ and $k_0$.  (So it is very usually equal to one of those four values!  How cool!!!  And in fact, for “most” values of $n$, this result can actually be improved even more, and this has to do with the number theoretic properties of $n$.)
The clique number is also tightly concentrated about its mean for other ranges of $p$.
The above statement is actually relatively easy to prove if you already have a strong background in probability.  See for instance these lecture notes on the subject:
https://people.eecs.berkeley.edu/~sinclair/cs271/n19.pdf
You can also find all of this in Alon and Spencer (The Probabilistic Method), which is one of the most commonly used texts on random graphs.  It’s pretty good for beginners in the subject, but you may want to skip around and also supplement it with lecture notes you find online.
