Dense Subgraphs in Random Graphs
Paul Balister Béla Bollobás Julian Sahasrabudhe Alexander Veremyev




Dense Subgraphs in Random Graphs
    Paul Balister [Department of Mathematical Sciences, University of Memphis, Memphis TN 38152, USA. Partially supported by NSF grant DMS 1600742], Béla Bollobás 
[Department of Pure Mathematics and Mathematical Statistics, University of Cambridge,
Cambridge CB3 0WB, UK and Department of Mathematical Sciences, 
University of Memphis, Memphis TN 38152, USA
and 
London Institute for Mathematical Sciences, 35a South St., Mayfair, London W1K 2XF,
UK. Partially supported by NSF grant DMS 1600742 and MULTIPLEX grant no. 317532.
]
Julian Sahasrabudhe [Instituto Nacional de Matemática Pura e Aplicada (IMPA), 
Estr. Dona Castorina, 110 Jardim Botânico, Rio de Janeiro RJ 22460-320, Brasil and
Peterhouse, University of Cambridge, Cambridge CB2 1RD, UK], 
Alexander Veremyev[Industrial Engineering & Management Systems, University of Central Florida, Orlando, Florida, USA.
Supported, in part, by the AFRL Mathematical Modeling and Optimization Institute]

    December 30, 2023
===========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




For a constant ∈[0,1] and a graph G, let ω_(G) be the largest integer k
for which there exists a k-vertex subgraph of G with at least k2 edges.
We show that if 0<p<<1 then ω_(G_n,p) is concentrated on a set of two integers. 
More precisely, with α(,p)=log/p+(1-)log1-/1-p, we show that 
ω_(G_n,p) is one of the two integers closest to
2/α(,p)(log n-loglog n+logeα(,p)/2)+1/2, with high probability. 
While this situation parallels that of cliques in random graphs, a new technique is required to handle the more complicated ways in which these “quasi-cliques” may overlap.




§ INTRODUCTION


Let G=(V(G),E(G)) be a simple, undirected graph where V(G) denotes the set of vertices of G (sometimes called nodes) and E(G) denotes the set of edges. A graph G is said to be complete if all possible edges are present: if {i,j}∈ E(G) for all i, j∈ V(G) ,  i j. For a subset S⊆ V(G), we denote by G[S] the subgraph of G induced by S: the graph with vertex set S and edge set {{i,j} : i,j ∈ S }∩ E(G). A clique C is a subset of V(G) for which G[C] is a complete graph <cit.>.



Cliques are a indispensable concept in the theory of graphs and have been extensively studied in various contexts, reaching back to the 1930s with the celebrated results of Ramsey <cit.> and Turán <cit.>. In random graphs, cliques have also been a central topic of study 
with its roots in the pioneering work of Erdős <cit.> on the probabilistic method. More recently, the concept of a clique has arisen naturally in sociometry <cit.> to model cohesive subgroups of tightly knit elements in a graph <cit.>. For example, in social networks, where vertices correspond to “actors” and edges indicate relationships between actors <cit.>, a clique represents a group of people any two of which have a certain kind of relationship (friendship, acquaintance, etc.) with each other <cit.>. Some of the earliest work on cliques, in the context of sociometry, is presented in  <cit.>.








However, in real-world applications, the clique is not always the correct concept; often we do not care that all edges are present in a particular subset, but only that the set is very “well connected”, in some appropriate sense. Consequently, a number of relaxations of the notion of “clique” have appeared in the literature in recent years <cit.>.



One of the most popular and widely used clique relaxation models is the -quasi-clique, where γ∈ [0,1] is a parameter <cit.>. In particular, for ∈ [0,1], we say that a subset S ⊆ V(G) of a graph G is a -quasi-clique if the graph G[S], induced by S, has at least |S|2 edges. 


This concept was first defined by Abello, Pardalos & Resende <cit.> who were interested in quasi-cliques in graphs representing telecommunications data. Later, the idea of “dense clusters” (a more general concept which includes -quasi-cliques) were studied in the context of molecular interaction networks described by Hartwell, Leland, Hopfield, John, Leibler, Stanislas, Murray and Andrew <cit.> and further analyzed by Spirin and Mirny <cit.>. They reported that dense subgraphs in molecular interaction networks correspond to meaningful modules or building blocks of molecular networks such as protein complexes or dynamic functional units.
The problem of finding large dense subgraphs have also appeared in a number of other domains including biology <cit.>, social network analysis <cit.>, finance 
<cit.> and data mining <cit.>. 

Given the the myriad of instances for which the notion is useful, one would like to efficiently compute solutions to basic questions about 
quasi-cliques in a given graph: for example, “what is the largest -quasi clique in (a given graph) G”? However, it comes as no surprise that the  computational problem of finding the largest quasi-clique in a given graph (along with many other such questions) is a hard computational problem, in general <cit.> – similar to the sister problem of finding large cliques in graphs <cit.>. Moreover, the literature on exact computational methods for this class of problems is extremely sparse and mostly focuses on the development and application of heuristic methods. It is therefore natural to study quasi-cliques in “random” or “typical” graphs, which may suffice for most applications, while allowing us to avoid the many hard computational barriers blocking the general problem.




To this end, we study the order of the largest -quasi-clique in the binomial random graph, a project initiated in a paper of Veremyev and Boginski  <cit.>. For a graph G, we let ω_(G) be the size of the largest subset of vertices of G that induces a -quasi clique. Of course, ω_1(G) is the classical “clique number” of G, often denoted by ω(G). 

We prove that ω_(G_n,p) is concentrated on two explicitly determined points, with high probability as n →∞, provided 0<p<  <1 are fixed real numbers. See Section <ref> for a more careful statement of this result. 

Although these bounds are asymptotic, computational experiments suggest that they are quite accurate even for relatively small (n=50, 100) graphs generated using the G_n,p model.

For the results of these experiments, see Section <ref>.




§ NOTATION AND STATEMENT OF THE MAIN RESULT
 

As usual write [n] for the set
{1,…,n} and G_n,p for the binomial random graph on vertex set
[n] with edge probability p∈(0,1). We use the notation O_n(1) to denote a quantity that is
bounded by a constant as n tends to infinity and we use o_n(1) to denote a quantity that tends
to zero as n tends to infinity. We say that a sequence of events E_n holds
with high probability (henceforth whp) if (E_n)=1-o_n(1). For a graph G we let e(G) denote the
number of edges in the graph.

A complete subgraph on k vertices will be called a k-clique, and we define the
clique number ω(G) of a graph G to be the largest integer k for which G contains a
k-clique. The study of the clique number of G_n,p was first carefully considered by
Matula <cit.>, who noticed that the clique number of G_n,p is concentrated on a small
set of values. These results were later strengthened by Grimmett and McDiarmid <cit.>
and then Bollobás and Erdős <cit.>, who showed that for fixed 0≤ p≤ 1 the
clique number takes one of only two values, whp (See also Theorem 11.1 in <cit.>). We prove that a similar phenomena persists for -quasi-cliques. However, a significant difficulty arises when controlling the concentration of the count of -quasi cliques directly. We tackle this issue by instead controlling a closely related random variable, which is more naturally handled.

We call n-vertex graph a -quasi-clique if
e(G)≥n2. For a graph G, we define ω_(G) to be the the largest integer
k for which there exists a -quasi-clique subgraph of order k. For 0<p<<1, we show that ω_(G_n,p) is concentrated on two points whp as n →∞.

 Let 0<p<<1 and >0 be fixed and define
 
    α(,p):=log/p+(1-)log1-/1-p.

 Then
 
    ω_(G_n,p)-2/α(,p)(log n-loglog n+logeα(,p)/2)
      ∈ (-,1+),
 whp.
 In particular, ω_(G_n,p) is one of the two integers closest to
 
    2/α(,p)(log n-loglog n+logeα(,p)/2)+1/2,
 whp.


As usual, the binary entropy function for ∈(0,1) is

    h():=log1/+(1-)log1/1-.

We use the following consequence of Stirling's formula. If ∈(0,1) is fixed, we have

    nγ n+O_n(1)=e^nh()-1/2log(n(1-))+O_n(1).







We first set out to give an upper bound for ω_(G_n,p) which holds with high probability. Let X_k=X_k,(G_n,p) be the random variable which counts the number of subgraphs of G_n,p that are -quasi-cliques on k vertices. We easily obtain an upper bound on ω_(G_n,p) by bounding X_k.
In preparation, we state a basic fact about binomial random variables.


 Let 0<p<<1 be fixed and N →∞. We have
 
    ((N,p)= N)=e^-Nα(,p)+O(log N),

 and
 
    ((N,p)≥ N)=e^-Nα(,p)+O(log N).



We have

    ((N,p)= N)   =N Np^ N(1-p)^(1-)N
       =e^Nh()-1/2log(N(1-))+N(log p+(1-)log(1-p))+O(logp/1-p)
       =e^-Nα(,p)+O(log N).

The second result follows as, for r≥ N>pN, ((N,p)=r) is decreasing in r,
and hence

    ((N,p)= N)≤((N,p)≥ N)≤ (N+1)((N,p)= N).

























We now may establish an upper bound on ω_(G_n,p), that holds whp, thus proving one of the inequalities implicit in the statement of Theorem <ref>. In the following sections, we go on to show that the distribution of quasi-cliques (actually a subclass of these quasi-cliques) is sufficiently concentrated to prove Theorem <ref>.


Let 0<p<<1 and >0 be fixed. Then as n →∞
 
    ω_(G_n,p)<2/α(,p)(log n-loglog n+loge·α(,p)/2)+1+,

 whp.


With X_k=X_k,(G_n,p) and S=k2 we have

    X_k   =nk((S,p)≥ S)
       ≤n^k/k!e^-Sα(,p)+O(log S)
       =e^k(log n-α(,p)(k-1)/2-log(k/e)+o_k(1))

Let κ=2/α(,p)(log n-loglog n+loge·α(,p)/2)+1+.
If k=κ then

    log n-α(,p)(k-1)/2-log(k/e)+o_k(1)<-·α(,p)/2+o_k(1)

is negative for large enough n, and hence the expectation must tend to zero.
Thus we have (X_k>0)≤ X_k=o_n(1). The existence
of a -quasi-clique on j>k vertices implies, by a simple averaging argument, that there exists
a -quasi-clique subgraph on k vertices. Thus if X_k=0 then X_j=0 for all j>k. Hence
ω_(G_n,p)<κ with high probability.




§ -FLAT SUBGRAPHS


To show that G_n,p contains a -quasi-clique of order roughly
2/α(,p)log n whp, we count a slightly restricted class of subgraphs. The advantage of
working with this restricted class is that the second moment of their count is controlled more naturally. 
Roughly speaking, we say that a -quasi-clique G is -flat if every induced subgraph of G is close to being a -quasi clique.

To make this definition precise, we need a few definitions. First, for a graph G and a subset A of the vertex set of G, let us define e(A) to be the number of edges with both end-points in A.

Now, for ∈(0,1) and ℓ∈[k], we define S=k2, T=ℓ2, and set

    D_k(ℓ)=min(T,S-T)ℓ^-1/2log k.

Call an k-vertex graph G -flat if e(G)=k2 and for all
A⊆ V(G) with ℓ=|A|∈[2,k-1], we have e(A)≤ℓ2+D_k(ℓ).
We note that min(T,S-T) is clearly an upper bound on e(A)-ℓ2 when
e(G)=k2, so this is only a restriction on e(A) when |A|=ℓ>(log k)^2.

We shall show that if a subset of k vertices in G_n,p has k2 edges then
it is reasonably likely that it will also be -flat, and hence the two notions are “typically”
interchangeable. For positive integers n, m, 0≤ m≤n2, we define the
Erdős-Rényi random graph G(n,m) as the uniform probability space that is supported
on all n vertex graphs with exactly m edges.


 Let G=G(k,k2) and let  be fixed and k →∞. Then G is -flat with high probability.


Let G=G(k,k2) be realized on the vertex set [k] and
fix a subset A⊆ [k] with ℓ=|A|∈[2,k-1]. We shall show that

    kℓ(e(A)≥ℓ2+D_k(ℓ))≤ k^-2.

Set S=k2, T=ℓ2, R=S-T, and put C(L)=(e(A)=L). Note that

    C(L)=TLR S-LS S^-1

and for 0≤ L<T, we have

    Q(L):=C(L+1)/C(L)
     =T-L/L+1( S-L/R- S+L+1).

From (<ref>) we see that Q(L) is strictly decreasing as L increases.
Let L= T+r≤ T. Then if r ≥ 0, 

    Q(L)   ≤ Q( T+r)≤((1-)T-r/ T+r+1)( R+1-r/(1-)R+r)
       =(1-r/(1-)T/1+r+1/ T)(1-r-1/ R/1+r/(1-)R)
       ≤min{1-r/(1-)T,1-r-1/ R}≤ e^-c(r-1)/min(R,T),

where c=1/max(,1-)>0 is a constant. Hence 

    C(L) = C( T  + r)  ≤ C( T+1)∏_s=1^r e^-c(s-1)/min(R,T)≤ e^-cr(r-1)/2min(R,T),

where we have used the (trivial) fact that C( T+1)≤ 1.
Now Tℓ^-1/2log k≥1/2log k and
Rℓ^-1/2log k≥ (k-1)^1/2log k, so D_ℓ(k)→∞ uniformly in ℓ
as k→∞. Thus for large k we have
cr(r-1)/(2min(R,T))≥ c'min(R,T)ℓ^-1(log k)^2
for some c'>0 when r>D_k(ℓ)-1. Hence

    (e(A)≥ T+D_k(ℓ))   =∑_ T+D_k(ℓ)≤ L≤ T C(L)
       ≤ℓ^2 e^-c'min(R,T)ℓ^-1(log k)^2

for large enough k.

Consider the case when R<T. Then R=(k-ℓ)(k+ℓ-1)/2>ℓ(k-ℓ)/2
and so c'min(R,T)ℓ^-1(log k)^2>5(k-ℓ)log k≥ (k-ℓ)log k+4log k
for large enough k. Now kℓ=kk-ℓ≤ k^k-ℓ, so

    kℓ(e(A)≥ℓ2+D_k(ℓ))≤kℓk^2 e^-(k-ℓ)log k-4log k≤ k^-2 ,
 as required. Now suppose R≥ T. Then
c'min(R,T)ℓ^-1(log k)^2>3ℓlog k≥ℓlog k+4log k
when k is large enough. Now kℓ≤ k^ℓ, so

    kℓ(e(A)≥ℓ2+D_k(ℓ))≤kℓk^2 e^-ℓlog k-4log k≤ k^-2,

as required. Hence (<ref>) holds for all ℓ∈[2,k-1].

Now, for 2≤ℓ≤ k-1, let Y_ℓ be the random variable counting the number of subsets
A of order ℓ which induce more than ℓ2+D_k(ℓ) edges.
By (<ref>) we have

    (Y_ℓ>0)≤(Y_ℓ)≤kℓ(e(A)≥ℓ2+D_k(ℓ))
     ≤ k^-2,

for large enough k. So the probability that Y_ℓ>0 for any of the <k choices for ℓ
is at most k^-1=o_k(1).


Let Z_k = Z_k,n be the random variable counting the number of copies of -flat subgraphs of order k in G_n,p, with p fixed and n→∞.
We now easily bound Z_k, by using Lemma <ref>, to relate it to the
quantity X_k.


 Let >0 and k≤2/α(,p)(log n-loglog n+loge·α(,p)/2)+1-
 with k→∞ as n→∞. Then Z_k→∞.


We apply Lemma <ref> to deduce that

    Z_k=nk(G(k,p) is -flat)≥ (1+o_k(1))nk(e(G(k,p))= S).

Now k=O(log n) by assumption, so nk=n^k/k!(1-O(k^2/n))=(1+o_k(1))n^k/k!. Hence

    Z_k   =(1+o_k(1))n^k/k!((S,p)= S)
       =n^k/k!e^-Sα(,p)+O(log S)
       =e^k(log n-(k-1)α(,p)/2-log(k/e)+o_k(1)).

However, the exponent in the last line tends to infinity when k→∞ and
k≤2/α(,p)(log n-loglog n+logeα(,p)/2)+1-.


In the next section we turn to estimate the variance of Z_k.



§ THE SECOND MOMENT


To prove our lower bound on ω_(G_n,p), we count the number of -flat subsets of order k in G_n,p,
where k is roughly 2/α(,p)log n. For k∈ [n], recall that Z_k is the random variable which
counts the number of -flat subsets of G(n,p). To apply Chebyshev's inequality, we aim to
estimate the fraction

    F= Z_k/( Z_k )^2= Z^2_k-( Z_k)^2/( Z_k)^2.

In particular, we shall show F=o(1), as both k and n tend to infinity. Let A,B⊆ [n] with |A|=|B|=k and |A∩ B|=ℓ.
We think of ℓ∈[2,k-1] and treat the degenerate cases ℓ∈{0,1,k} separately.
Put S=k2, T=ℓ2, R=S-T and let g_ℓ(L) denote the probability that
e(A)= S, e(B)= S and e(A∩ B)=L.
We note that

    g_ℓ(L)=TLR S-L^2p^2 S-L(1-p)^2(1-)S-T+L

and consider the ratio

    R_ℓ(L)   =g_ℓ(L)/(e(A)= S)^2
       =TLR S-L^2S S^-2p^-L(1-p)^L-T.


The following lemma gives us a suitable way of estimating the quantity R_ℓ(L), for our purposes. For the remainder of the section, we maintain the assumption that 0 < p < ≤ 1 and that k →∞.


 Let 2≤ℓ≤ k-1, r≥ 0 be an integer and 
 set λ=2·/1-1-p/p.
 Then
 
    R_ℓ( T+r)≤λ^r e^Tα(,p)+O_k(1)
 and
 
    R_ℓ( T-r)≤ R_ℓ( T).



We first bound R_ℓ( T). Note that R≥ k-1 and hence R^2T=R^2(S-R)≥ S^2
for 2≤ℓ≤ k-1. Since S=k2→∞ and  is fixed,
we may bound line (<ref>) by using equation (<ref>), to obtain

    R_ℓ( T)
        =e^Th()+2(S-T)h()-2Sh()+1/2logS^2/(1-)R^2T+O_k(1)
      p^- T(1-p)^-(1-)T
       ≤ e^-Th()+O_k(1)p^- T(1-p)^-(1-)T
       =e^Tα(,p)+O_k(1).

Now put C(L)=R_ℓ(L+1)/R_ℓ(L) and observe that C(L) can be written as

    1-p/p·T-L/L+1( S-L/R- S+L+1)^2.

From this expression, we see that C(L) strictly decreases as L increases and therefore

    C( T+r)   ≤ C( T)
       ≤1-p/p·/1-(1+1/ R).

Now note that since ℓ<k, by assumption, we have that R≥ k-1 and thus R tends to
infinity with k. Hence, for large k,

    C( T+r)≤ 21-p/p/1-=λ.

We now apply this inequality r times to obtain

    R_ℓ( T+r)≤λ^r R_ℓ( T),

which holds for k sufficiently large, but independently of r. This proves the
inequality (<ref>).

To prove the inequality (<ref>) we note that C(L) is strictly decreasing and

    C( T-1)   ≥1-p/p/1-·(1+1/(1-)T)(1+1/ T)
       ≥1-p/p/1->1.

Thus R_ℓ( T-r)≤ R_ℓ( T).


We are now in a position to show that F=o(1) as n and k tend to infinity.


 Let k≤2/α(,p)(log n-loglog n+logeα(,p)/2)+1-.
 We have
 
    Z_k^2=(1+o_k(1))( Z_k)^2.



We consider the fraction F, from equation (<ref>). We keep with the convention that
S=k2, T=ℓ2, and R=S-T. Let E_A and E_B denote the events
that A, resp. B, induces a -flat subgraph. Let E'_A, resp. E'_B, denote the event
that A, resp. B, induce exactly S edges. Note that E_A⊆ E'_A and
E_B⊆ E'_B. Now write t(ℓ)=t_n,k(ℓ)=kℓn-kk-ℓnk^-1.




We now turn to bound F.
We may expand Z_k as a sum of indicators

    Z_k =  ∑_A ⊂ V(G), |A| = k1(E_A)

Hence Z_k = nk(E_A) thus

    F =  Z_k^2 - ( Z_k)^2/ Z_k = ∑_A,Bnk^-2(E_A ∩ E_B ) - (E_A)(E_B)/(E_A)^2.

We now divide the sum with respect to |A∩ B| = ℓ to obtain

    F   =∑_ℓ=0^knkkℓn-kk-ℓnk^-2(E_A∩ E_B)-(E_A)(E_B)/(E_A)(E_B)
       =∑_ℓ=2^k-1t(ℓ)·(E_A∩ E_B)-(E_A)^2/(E_A)^2+o_n(1),

where we have eliminated the first two terms in the above sum as E_A and E_B are independent
events when |A∩ B|≤ 1. We have also  eliminated the last term in the sum, i.e. when E_A=E_B. This is justified, as this term is at most
(nk(E_A)))^-1=( Z_k)^-1=o_k(1), by Lemma <ref>.
Let us denote the ℓth term in the sum at (<ref>) as F(ℓ).

Lemma <ref> implies that

    (E_A∩ E_B)-(E_A)^2/P(E_A)^2≤(1+o_k(1))(E_A∩ E_B)/(E'_A)^2.


For ℓ∈ [2, k-1], our “flatness condition” on subsets of A applies and hence

    (E_A∩ E_B)/(E'_A)^2   =(E'_A)^-2∑_0≤ L≤ T+D_k(ℓ)(E_A∩ E_B| e(A∩ B)=L)(e(A∩ B)=L)
       ≤(E'_A)^-2∑_0≤ L≤ T+D_k(ℓ)(E'_A∩ E'_B| e(A∩ B)=L)(e(A∩ B)=L)
       =∑_0≤ L≤ T+D_k(ℓ)R_ℓ(L)
       =∑_0≤ L < TR_ℓ(L)+∑_ T≤ L≤ T+D_k(ℓ) R_ℓ(L)
       ≤ Tλ^D_k(ℓ)e^Tα(,p)+O_k(1).

This last inequality follows from applying the inequality (<ref>)
(from Lemma <ref>) to each term in the right sum and applying the
inequality (<ref>) (again from Lemma <ref>) to the left sum.
So we may bound the ℓth term in the sum (<ref>)
as

    F(ℓ)≤ t(ℓ)Tλ^D_k(ℓ)e^Tα(,p)+O_k(1).

We first consider the case when R<T. Write δ:=k-ℓ.
Now

    t(ℓ)=kδn-kδnk^-1≤ (kn)^δnk^-1

and Z_k=nke^-Sα(,p)+O(log k)→∞.
Also D_k(ℓ)=Rℓ^-1/2log k=o_k(R) as R<T implies ℓ≥ k/2.
Thus

    F(ℓ) Z_k≤ e^δlog(kn)-Rα(,p)+o_k(R)

But R=δ(k+ℓ-1)/2≥ 2kδ/3 and kα(,p)∼ 2log n. Thus
F(ℓ)≤ ( Z_k)^-1e^-(1/3-o_k(1))δlog n.
In particular, ∑_ℓ R<TF(ℓ)=o(1).

Now consider the case when R≥ T. In this case we use the bound
t(ℓ)≤ (1+o_k(1))(k^2/n)^ℓ to deduce that

    F(ℓ)≤ e^Tα(,p)+ℓlog(k^2/n)+O_k(T ℓ^-1/2log k)+O_k(log k)
     =e^ℓ((ℓ-1)α(,p)/2-log(n)+O_k(k^1/2log k)).

Now k=O(log n) and ℓ<3k/4. Thus (ℓ-1)α(,p)/2≤ (3/4+o_k(1))log n.
Hence F(ℓ)≤ e^-(1/4-o(1))log n and so ∑_ℓ R≥ TF(ℓ)=o(1).























After these preparations, it is only a small step to finish the proof of Theorem <ref>.



Let >0 be given. The upper bound on ω_(G_n,p) follows from Lemma <ref>.
For the lower bound, assume k≤2/α(,p)(log n-loglog n+logeα(,p)/2)+1-.
From Lemma <ref> we know that Z_k→∞, so for sufficiently large n we
have Z_k>0 and thus we may apply Chebyshev's inequality to show that the quantity (X_k=0) is small. We have

    (X_k=0)≤(Z_k=0)≤(|Z_k- Z_k|≥ Z_k)≤(Z_k)/(Z_k)^2=F=o(1),

where we have used the fact that every -flat set is a -quasi-clique for the first inequality.
The third inequality is Chebyshev's inequality and the bound on F is the content
of Lemma <ref>.




§ COMPUTATIONAL EXPERIMENTS
 

Here, we note the bounds obtained from Theorem <ref> are actually quite accurate in practice, even for relatively small values of n.
To illustrate, we performed a small set of computational experiments for graphs of size n=50 and n=100 and different values of p. For each pair n,p we generated 100 instances of graphs sampled according to the corresponding G_n,p model. We have also selected various values of  ranging from 0.3 to 0.9. 

For each , n, p in Table <ref> we report the minimum ω_min^, maximum ω_max^ and average ω_avg^ cardinalities of the largest -quasi-cliques and compare this to ω_th^, the “theoretical” value obtained from the formula in Theorem <ref>. That is, 


    ω^_th(n) = 2/α(,p)(log n-loglog n+logeα(,p)/2) + 1/2 .


Observe that the obtained formula provides an accurate estimate of γ-quasi-clique
number ω_γ(G) in graph instances generated according to the binomial random graph G_n,p, even for relatively small values of n.

To identify the largest -quasi-clique in these experiments, we used the so-called feasibility check version of
formulation F4 in <cit.> (or AlgF4). Previous experimental work has suggested this algorithm to be the best performing on instances generated from G_n,p. 






