The Maximum Block Size of Critical Random Graphs

MaRDI QIDQ4632499zbMATH OpenFDO

Authors Vonjy Rasendrahasina, Andry Rasoanaivo, Vlady Ravelomanana

Publication date 29 April 2019

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

zbMATH Keywords

analytic combinatoricsmaximum block-sizerandom graph

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Distance in graphs (05C12) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Let $G(n,,M)$ be the uniform random graph with $n$ vertices and $M$ edges. Let $B_n$ be the maximum block-size of $G(n,,M)$ or the maximum size of its maximal $2$-connected induced subgraphs. We determine the expectation of $B_n$ near the critical point $M=n/2$. As $n-2Mgg{n}^{2/3}$, we find a constant $c_1$ such that [ c_1 = lim_{n ightarrow infty} left(1 - frac{2M}{n} ight) , E B_n , . ] Inside the window of transition of $G(n,,M)$ with $M=fracn2(1+lambda{n}^{-1/3})$, where $lambda$ is any real number, we find an exact analytic expression for [ c_2(lambda) = lim_{n ightarrow infty} frac{E B_n} {n^{1/3}} , . ] This study relies on the symbolic method and analytic tools coming from generating function theory which enable us to describe the evolution of $n^{-1/3},E{B}_n$ as a function of $lambda$.

Recommendations

• Expected Maximum Block Size in Critical Random Graphs
• On the size of a random maximal graph
• The component sizes of a critical random graph with given degree sequence
• An elementary approach to component sizes in critical random graphs
• The largest component in critical random intersection graphs
• On the largest component of the random graph at a nearcritical stage
• The maximum degree of a random graph
• The maximal length of 2-path in random critical graphs

Cited in

(4)

• A proof of the block model threshold conjecture
• The maximal length of 2-path in random critical graphs
• Expected Maximum Block Size in Critical Random Graphs
• The complexity of the Approximate Multiple Pattern Matching Problem for random strings

This page was built for publication: The Maximum Block Size of Critical Random Graphs

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