2008/05/14 by Martin Nehéz, Martin Nehez, Daniel Olejar +5
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics #cs.IT #math.CO #math.IT
paper · pdf · doi:10.48550/arxiv.0805.2105
to appear in Proc. 2nd Int. Conf. on Math. and Applications in Information Technology, Lahore Univ. of Management, Lahore, Pakistan, 2008
arxiv created 2008/05/14 · openalex publication_date 2008/05/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Emergence of dominating cliques in Erdös-Rényi random graph model \bbbg(n,p) is investigated in this paper. It is shown this phenomenon possesses a phase transition. Namely, we have argued that, given a constant probability p, an n-node random graph G from \bbbg(n,p) and for r= c log1/p n with 1 ≤ c ≤ 2, it holds: (1) if p > 1/2 then an r-node clique is dominating in G almost surely and, (2) if p ≤ (3 - √(5))/2 then an r-node clique is not dominating in G almost surely. The remaining range of probability p is discussed with more attention. A detailed study shows that this problem is answered by examination of sub-logarithmic growth of r upon n.