Scientific Results

  • ID:
    publications-4687
  • Type:
    article
  • Year:
    1984
  • Authors:
    BollobΓ΅s, BΓ©la and BollobΓ΅s, BΓ©la
  • Title:
    The evolution of random graphs
  • Venue/Journal:
    Transactions of the American Mathematical Society
  • DOI:
    10.1090/s0002-9947-1984-0756039-5
  • Research type:
  • Water System:
  • Technical Focus:
  • Abstract:
    According to a fundamental result of ErdΓ¶s and RΓ©nyi, the structure of a random graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G Subscript upper M"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>M</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{G_M}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> changes suddenly when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M tilde n slash 2"> <mml:semantics> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>∼<!-- ∼ --></mml:mo> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">M \sim n/2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>: if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M equals left floor c n right floor"> <mml:semantics> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>=</mml:mo> <mml:mrow> <mml:mo>β_x008c__x008a_</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>c</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>β_x008c_‹</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">M = \left \lfloor {cn} \right \rfloor</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c greater-than one half"> <mml:semantics> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:mfrac> </mml:mrow> <mml:annotation encoding="application/x-tex">c &gt; \frac {1}{2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> then a.e. random graph of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and since <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is such that its largest component has <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis log n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo><!-- --></mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(\log n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices, but for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="c greater-than one half"> <mml:semantics> <mml:mrow> <mml:mi>c</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:mfrac> </mml:mrow> <mml:annotation encoding="application/x-tex">c &gt; \frac {1}{2}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> a.e. <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G Subscript upper M"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>M</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{G_M}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has a giant component: a component of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 1 minus alpha Subscript c Baseline plus o left-parenthesis 1 right-parenthesis right-parenthesis n"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>Ξ±<!-- Ξ± --></mml:mi> <mml:mi>c</mml:mi> </mml:msub> </mml:mrow> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">(1-{\alpha _c}+o(1))n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha Subscript c Baseline greater-than 1"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>Ξ±<!-- Ξ± --></mml:mi> <mml:mi>c</mml:mi> </mml:msub> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">{\alpha _c} &gt; 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The aim of this paper is to examine in detail the structure of a random graph <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G Subscript upper M"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>G</mml:mi> <mml:mi>M</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{G_M}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M"> <mml:semantics> <mml:mi>M</mml:mi> <mml:annotation encoding="application/x-tex">M</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is close to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n slash 2"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n/2</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Among others it is proved that if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper M equals n slash 2 plus s"> <mml:semantics> <mml:mrow> <mml:mi>M</mml:mi> <mml:mo>=</mml:mo> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> <mml:mo>+</mml:mo> <mml:mi>s</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">M = n/2 + s</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s equals o left-parenthesis n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>=</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">s = o(n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s greater-than-or-equal-to left-parenthesis log n right-parenthesis Superscript 1 slash 2 Baseline n Superscript 2 slash 3"> <mml:semantics> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>≥<!-- ≥ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo><!-- --></mml:mo> <mml:mi>n</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">s \geq {(\log n)^{1/2}}{n^{2/3}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> then the giant component has <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis 4 plus o left-parenthesis 1 right-parenthesis right-parenthesis s"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mn>4</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mi>s</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">(4 + o(1))s</mml:annotation> </mml:semantics> </mml:math> </inline-formula> vertices. Furthermore, rather precise estimates are given for the order of the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula>th largest component for every fixed <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r"> <mml:semantics> <mml:mi>r</mml:mi> <mml:annotation encoding="application/x-tex">r</mml:annotation> </mml:semantics> </mml:math> </inline-formula>.
  • Link with Projects:
  • Link with Tools:
  • Related policies:
  • ID: