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

DOI10.1016/J.EJC.2022.103602zbMATH Open1498.05244arXiv1804.04430OpenAlexW2797330704WikidataQ114184712 ScholiaQ114184712MaRDI QIDQ2080227FDOQ2080227

Igor V. Rodionov, M. E. Zhukovskii

Publication date: 7 October 2022

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $Delt{a}_{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 $sigm{a}_n$ such that $fracDelt{a}_{k;n}-a_{n}sigm{a}_n$ converges in distribution to a random variable having the standard Gumbel distribution.

Full work available at URL: https://arxiv.org/abs/1804.04430

zbMATH Keywords

extreme value theorystandard Gumbel distribution

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Extremal problems in graph theory (05C35) Combinatorial probability (60C05)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Statistics of Extremes
• Extremes and related properties of random sequences and processes
• Sur la distribution limite du terme maximum d'une série aléatoire
• Maxima of Poisson-like variables and related triangular arrays
• Asymptotics of maxima of discrete random variables
• A limiting distribution for maxima of discrete stationary triangular arrays with an application to risk due to avalanches
• Counting extensions
• Paths in graphs
• The distribution of the maximum degree of a random graph
• A useful elementary correlation inequality
• Degree sequences of random graphs
• On the Asymptotic Behavior of Degrees of Vertices in a Random Graph
• Families of Non-disjoint subsets
• A useful elementary correlation inequality. II
• The Janson inequalities for general up‐sets

Cited In (3)

• Maximum number of symmetric extensions in random graphs
• Mutual and shared neighbor probabilities: finite- and infinite-dimensional results
• Extremal independence in discrete random systems

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On the distribution of the maximum eigenvalues of graphs 👍 👎
• Estimation of the number of maximal extensions in a random graph 👍 👎
• The degree distribution of the random multigraphs 👍 👎
• The Degree Distribution in Random Intersection Graphs 👍 👎
• The distribution of the number of node neighbors in random hypergraphs 👍 👎
• On the distribution of the maximum \(k\)-degrees of the binomial random graph 👍 👎
• The maximum degree of a random graph 👍 👎
• A concentration inequality for maximum matching size in random graphs¹ 👍 👎

This page was built for publication: The distribution of the maximum number of common neighbors in the random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2080227)