The distribution of the maximum number of common neighbors in the random graph

2018/04/12 by I. V. Rodionov, Rodionov, Igor, Maksim Zhukovskii +1 · 1 citation
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1804.04430

openalex publication_date 2018/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let Δ_k;n be the maximum number of common neighbors of a set of k vertices in G(n,p). In this paper, we find a_n and σ_n such that \fracΔ_k;n-a_nσ_n converges in distribution to a random variable having the standard Gumbel distribution.

Cited by

• Non-isomorphic subgraphs in random graphs

Related

• Maximum number of symmetric extensions in the random graph
• On the maximum number of common neighbours in dense random regular graphs
• The limit distribution of the maximum probability nearest neighbor ball
• Fluctuations of the connectivity threshold and largest nearest-neighbour link
• Criticality of the Exponential Rate of Decay for the Largest Nearest Neighbor Link in Random Geometric Graph