The sharp threshold for making squares

Abstract

Consider a random sequence of $N$ integers, each chosen uniformly and independently from the set $\{1,…,x\}$. Motivated by applications to factorization algorithms such as Dixon’s algorithm, the quadratic sieve, and the number field sieve, Pomerance in 1994 posed the following problem: how large should $N$ be so that, with high probability, this sequence contains a subsequence, the product of whose elements is a perfect square? Pomerance determined asymptotically the logarithm of the threshold for this event and conjectured that it in fact exhibits a \emph sharp threshold in\nonbreakingspace $N$. More recently, Croot, Granville, Pemantle and Tetali determined the threshold up to a factor of $4/\pi + o(1)$ as $x \to \infty $ and made a conjecture regarding the location of the sharp threshold. \par In this paper we prove both of these conjectures by determining the sharp threshold for making squares. Our proof combines techniques from combinatorics, probability and analytic number theory; in particular, we use the so-called method of self-correcting martingales in order to control the size of the 2-core of the random hypergraph that encodes the prime factors of our random numbers. Our method also gives a new (and completely different) proof of the upper bound in the main theorem of Croot, Granville, Pemantle and Tetali.

Note: To view the article, click on the URL link for the DOI number.

  • [Azuma] Go to document K. Azuma, "Weighted sums of certain dependent random variables," Tôhoku Math. J. (2), vol. 19, pp. 357-367, 1967.
    @ARTICLE{Azuma,
      author = {Azuma, Kazuoki},
      title = {Weighted sums of certain dependent random variables},
      journal = {Tôhoku Math. J. (2)},
      fjournal = {The Tohoku Mathematical Journal. Second Series},
      volume = {19},
      year = {1967},
      pages = {357--367},
      issn = {0040-8735},
      mrclass = {60.40},
      mrnumber = {0221571},
      mrreviewer = {Bernard Harris},
      doi = {10.2748/tmj/1178243286},
      zblnumber = {0178.21103},
      }
  • [BBLM] P. Balister, P. Bollobás, J. Lee, and R. Morris, On the 2-core of a random set of numbers.
    @MISC{BBLM,
      author = {Balister, P. and Bollobás, P. and Lee, J. and Morris, R.},
      title = {On the 2-core of a random set of numbers},
      note = {in preparation},
      zblnumber = {},
      }
  • [BBDM] Go to document J. Balogh, B. Bollobás, H. Duminil-Copin, and R. Morris, "The sharp threshold for bootstrap percolation in all dimensions," Trans. Amer. Math. Soc., vol. 364, iss. 5, pp. 2667-2701, 2012.
    @ARTICLE{BBDM,
      author = {Balogh, József and Bollobás, Béla and Duminil-Copin, Hugo and Morris, Robert},
      title = {The sharp threshold for bootstrap percolation in all dimensions},
      journal = {Trans. Amer. Math. Soc.},
      fjournal = {Transactions of the American Mathematical Society},
      volume = {364},
      year = {2012},
      number = {5},
      pages = {2667--2701},
      issn = {0002-9947},
      mrclass = {60K35 (05C80 60C05)},
      mrnumber = {2888224},
      mrreviewer = {Anatoly Yambartsev},
      doi = {10.1090/S0002-9947-2011-05552-2},
      zblnumber = {1238.60108},
      }
  • [BK] Go to document T. Bohman and P. Keevash, "Dynamic concentration of the triangle-free process," in The Seventh European Conference on Combinatorics, Graph Theory and Applications, Ed. Norm., Pisa, 2013, vol. 16, pp. 489-495.
    @INCOLLECTION{BK,
      author = {Bohman, Tom and Keevash, Peter},
      title = {Dynamic concentration of the triangle-free process},
      booktitle = {The {S}eventh {E}uropean {C}onference on {C}ombinatorics, {G}raph {T}heory and {A}pplications},
      series = {CRM Series},
      volume = {16},
      pages = {489--495},
      publisher = {Ed. Norm., Pisa},
      year = {2013},
      mrclass = {05C85 (05C80)},
      mrnumber = {3185850},
      doi = {10.1007/978-88-7642-475-5_78},
      zblnumber = {1291.05183},
      }
  • [BFL1] Go to document T. Bohman, A. Frieze, and E. Lubetzky, "A note on the random greedy triangle-packing algorithm," J. Comb., vol. 1, iss. 3-4, pp. 477-488, 2010.
    @ARTICLE{BFL1,
      author = {Bohman, Tom and Frieze, Alan and Lubetzky, Eyal},
      title = {A note on the random greedy triangle-packing algorithm},
      journal = {J. Comb.},
      fjournal = {Journal of Combinatorics},
      volume = {1},
      year = {2010},
      number = {3-4},
      pages = {477--488},
      issn = {2156-3527},
      mrclass = {05C85 (05C80)},
      mrnumber = {2799220},
      mrreviewer = {Nikolaos Fountoulakis},
      doi = {10.4310/JOC.2010.v1.n4.a5},
      zblnumber = {1244.05213},
      }
  • [BFL2] Go to document T. Bohman, A. Frieze, and E. Lubetzky, "Random triangle removal," Adv. Math., vol. 280, pp. 379-438, 2015.
    @ARTICLE{BFL2,
      author = {Bohman, Tom and Frieze, Alan and Lubetzky, Eyal},
      title = {Random triangle removal},
      journal = {Adv. Math.},
      fjournal = {Advances in Mathematics},
      volume = {280},
      year = {2015},
      pages = {379--438},
      issn = {0001-8708},
      mrclass = {05C80 (60G99)},
      mrnumber = {3350225},
      mrreviewer = {Jonathan Henry Jordan},
      doi = {10.1016/j.aim.2015.04.015},
      zblnumber = {1312.05123},
      }
  • [BP] Go to document T. Bohman and M. Picollelli, "SIR epidemics on random graphs with a fixed degree sequence," Random Structures Algorithms, vol. 41, iss. 2, pp. 179-214, 2012.
    @ARTICLE{BP,
      author = {Bohman, Tom and Picollelli, Michael},
      title = {S{IR} epidemics on random graphs with a fixed degree sequence},
      journal = {Random Structures Algorithms},
      fjournal = {Random Structures \& Algorithms},
      volume = {41},
      year = {2012},
      number = {2},
      pages = {179--214},
      issn = {1042-9832},
      mrclass = {05C80 (05C07 60J80 92D30)},
      mrnumber = {2956054},
      mrreviewer = {Peter Windridge},
      doi = {10.1002/rsa.20401},
      zblnumber = {06099390},
      }
  • [BelaRG] Go to document B. Bollobás, Random Graphs, Second ed., Cambridge University Press, Cambridge, 2001, vol. 73.
    @BOOK{BelaRG,
      author = {Bollobás, Béla},
      title = {Random Graphs},
      series = {Cambridge Stud. Adv. Math.},
      volume = {73},
      edition = {Second},
      publisher = {Cambridge University Press, Cambridge},
      year = {2001},
      pages = {xviii+498},
      isbn = {0-521-80920-7; 0-521-79722-5},
      mrclass = {05C80 (60C05)},
      mrnumber = {1864966},
      doi = {10.1017/CBO9780511814068},
      zblnumber = {0979.05003},
      }
  • [Bru51] Go to document N. G. de Bruijn, "On the number of positive integers $\leq x$ and free of prime factors $>y$," Nederl. Acad. Wetensch. Proc. Ser. A., vol. 54, pp. 50-60, 1951.
    @ARTICLE{Bru51,
      author = {de Bruijn, N. G.},
      title = {On the number of positive integers {$\leq x$} and free of prime factors {$>y$}},
      journal = {Nederl. Acad. Wetensch. Proc. Ser. A.},
      volume = {54},
      year = {1951},
      pages = {50--60},
      mrclass = {10.0X},
      mrnumber = {0046375},
      mrreviewer = {P. T. Bateman},
      zblnumber = {0042.04204},
      doi = {10.1016/S1385-7258(51)50008-2},
      }
  • [Bru66] Go to document N. G. de Bruijn, "On the number of positive integers $\leq x$ and free prime factors $>y$. II," Nederl. Akad. Wetensch. Proc. Ser. A., vol. 69, pp. 239-247, 1966.
    @ARTICLE{Bru66,
      author = {de Bruijn, N. G.},
      title = {On the number of positive integers {$\leq x$} and free prime factors {$>y$}. {II}},
      journal = {Nederl. Akad. Wetensch. Proc. Ser. A.},
      volume = {69},
      year = {1966},
      pages = {239--247},
      mrclass = {10.42 (10.43)},
      mrnumber = {0205945},
      mrreviewer = {S. Chowla},
      zblnumber = {0139.27203},
      doi = {10.1016/S1385-7258(66)50029-4},
     }
  • [CEP] Go to document E. R. Canfield, P. ErdHos, and C. Pomerance, "On a problem of Oppenheim concerning “factorisatio numerorum”," J. Number Theory, vol. 17, iss. 1, pp. 1-28, 1983.
    @ARTICLE{CEP,
      author = {Canfield, E. R. and Erdős, Paul and Pomerance, Carl},
      title = {On a problem of {O}ppenheim concerning ``factorisatio numerorum''},
      journal = {J. Number Theory},
      fjournal = {Journal of Number Theory},
      volume = {17},
      year = {1983},
      number = {1},
      pages = {1--28},
      issn = {0022-314X},
      mrclass = {11A51},
      mrnumber = {0712964},
      mrreviewer = {Mohan Nair},
      doi = {10.1016/0022-314X(83)90002-1},
      zblnumber = {0513.10043},
      }
  • [Chernoff] Go to document H. Chernoff, "A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations," Ann. Math. Statistics, vol. 23, pp. 493-507, 1952.
    @ARTICLE{Chernoff,
      author = {Chernoff, Herman},
      title = {A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations},
      journal = {Ann. Math. Statistics},
      fjournal = {Annals of Mathematical Statistics},
      volume = {23},
      year = {1952},
      pages = {493--507},
      issn = {0003-4851},
      mrclass = {62.0X},
      mrnumber = {0057518},
      mrreviewer = {H. Teicher},
      zblnumber = {0048.11804},
      doi = {10.1214/aoms/1177729330},
      }
  • [CGPT] Go to document E. Croot, A. Granville, R. Pemantle, and P. Tetali, "On sharp transitions in making squares," Ann. of Math. (2), vol. 175, iss. 3, pp. 1507-1550, 2012.
    @ARTICLE{CGPT,
      author = {Croot, Ernie and Granville, Andrew and Pemantle, Robin and Tetali, Prasad},
      title = {On sharp transitions in making squares},
      journal = {Ann. of Math. (2)},
      fjournal = {Annals of Mathematics. Second Series},
      volume = {175},
      year = {2012},
      number = {3},
      pages = {1507--1550},
      issn = {0003-486X},
      mrclass = {11Y05},
      mrnumber = {2912710},
      mrreviewer = {Andrew V. Sutherland},
      doi = {10.4007/annals.2012.175.3.10},
      zblnumber = {1321.11122},
      }
  • [Dickman] K. Dickman, "On the frequency of numbers containing prime factors of a certain relative magnitude," Ark. Mat. Astron. Fys., vol. 22, pp. 1-14, 1930.
    @ARTICLE{Dickman,
      author = {Dickman, K.},
      title = {On the frequency of numbers containing prime factors of a certain relative magnitude},
      journal = {Ark. Mat. Astron. Fys.},
      volume = {22},
      year = {1930},
      pages = {1--14},
      zblnumber = {56.0178.04},
      }
  • [Dixon] Go to document J. D. Dixon, "Asymptotically fast factorization of integers," Math. Comp., vol. 36, iss. 153, pp. 255-260, 1981.
    @ARTICLE{Dixon,
      author = {Dixon, John D.},
      title = {Asymptotically fast factorization of integers},
      journal = {Math. Comp.},
      fjournal = {Mathematics of Computation},
      volume = {36},
      year = {1981},
      number = {153},
      pages = {255--260},
      issn = {0025-5718},
      mrclass = {10A30 (10A25)},
      mrnumber = {0595059},
      mrreviewer = {H. L. Abbott},
      doi = {10.2307/2007743},
      zblnumber = {0452.10010},
      }
  • [FGM] G. Fiz Pontiveros, S. Griffiths, and R. Morris, The triangle-free process and the Ramsey numbers $R(3,k)$.
    @MISC{FGM,
      author = {Fiz Pontiveros, G. and Griffiths, S. and Morris, R.},
      title = {The triangle-free process and the {R}amsey numbers {$R(3,k)$}},
      note = {\emph{Mem. Amer. Math. Soc.},
      to appear},
      arxiv = {1302.6279},
      }
  • [H86] Go to document A. Hildebrand, "On the number of positive integers $\leq x$ and free of prime factors $>y$," J. Number Theory, vol. 22, iss. 3, pp. 289-307, 1986.
    @ARTICLE{H86,
      author = {Hildebrand, Adolf},
      title = {On the number of positive integers {$\leq x$} and free of prime factors {$>y$}},
      journal = {J. Number Theory},
      fjournal = {Journal of Number Theory},
      volume = {22},
      year = {1986},
      number = {3},
      pages = {289--307},
      issn = {0022-314X},
      mrclass = {11N25},
      mrnumber = {0831874},
      mrreviewer = {T. M. Apostol},
      doi = {10.1016/0022-314X(86)90013-2},
      zblnumber = {0575.10038},
      }
  • [HT] Go to document A. Hildebrand and G. Tenenbaum, "On integers free of large prime factors," Trans. Amer. Math. Soc., vol. 296, iss. 1, pp. 265-290, 1986.
    @ARTICLE{HT,
      author = {Hildebrand, Adolf and Tenenbaum, Gérald},
      title = {On integers free of large prime factors},
      journal = {Trans. Amer. Math. Soc.},
      fjournal = {Transactions of the American Mathematical Society},
      volume = {296},
      year = {1986},
      number = {1},
      pages = {265--290},
      issn = {0002-9947},
      mrclass = {11N25},
      mrnumber = {0837811},
      mrreviewer = {Aleksandar Ivić},
      doi = {10.2307/2000573},
      zblnumber = {0601.10028},
      }
  • [HTS] Go to document A. Hildebrand and G. Tenenbaum, "Integers without large prime factors," J. Théor. Nombres Bordeaux, vol. 5, iss. 2, pp. 411-484, 1993.
    @ARTICLE{HTS,
      author = {Hildebrand, Adolf and Tenenbaum, Gérald},
      title = {Integers without large prime factors},
      journal = {J. Théor. Nombres Bordeaux},
      fjournal = {Journal de Théorie des Nombres de Bordeaux},
      volume = {5},
      year = {1993},
      number = {2},
      pages = {411--484},
      issn = {1246-7405},
      mrclass = {11N25 (11N37)},
      mrnumber = {1265913},
      mrreviewer = {Pieter Moree},
      doi = {10.5802/jtnb.101},
      zblnumber = {0797.11070},
      }
  • [H] Go to document W. Hoeffding, "Probability inequalities for sums of bounded random variables," J. Amer. Statist. Assoc., vol. 58, pp. 13-30, 1963.
    @ARTICLE{H,
      author = {Hoeffding, Wassily},
      title = {Probability inequalities for sums of bounded random variables},
      journal = {J. Amer. Statist. Assoc.},
      fjournal = {Journal of the American Statistical Association},
      volume = {58},
      year = {1963},
      pages = {13--30},
      issn = {0162-1459},
      mrclass = {60.20},
      mrnumber = {0144363},
      mrreviewer = {E. H. Lehman, Jr.},
      doi = {10.1080/01621459.1963.10500830},
      zblnumber = {0127.10602},
      }
  • [JLTV] Go to document S. Janson, T. Łuczak, T. Turova, and T. Vallier, "Bootstrap percolation on the random graph $G_{n,p}$," Ann. Appl. Probab., vol. 22, iss. 5, pp. 1989-2047, 2012.
    @ARTICLE{JLTV,
      author = {Janson, Svante and {\L}uczak, Tomasz and Turova, Tatyana and Vallier, Thomas},
      title = {Bootstrap percolation on the random graph {$G_{n,p}$}},
      journal = {Ann. Appl. Probab.},
      fjournal = {The Annals of Applied Probability},
      volume = {22},
      year = {2012},
      number = {5},
      pages = {1989--2047},
      issn = {1050-5164},
      mrclass = {05C80 (60C05 60K35)},
      mrnumber = {3025687},
      mrreviewer = {Elisabetta Candellero},
      doi = {10.1214/11-AAP822},
      zblnumber = {1254.05182},
      }
  • [768bit] Go to document T. Kleinjung, K. Aoki, J. Franke, A. K. Lenstra, E. Thomé, J. W. Bos, P. Gaudry, A. Kruppa, P. L. Montgomery, D. A. Osvik, H. te Riele, A. Timofeev, and P. Zimmermann, "Factorization of a 768-bit RSA modulus," in Advances in Cryptology—CRYPTO 2010, Springer, Berlin, 2010, vol. 6223, pp. 333-350.
    @INCOLLECTION{768bit,
      author = {Kleinjung, Thorsten and Aoki, Kazumaro and Franke, Jens and Lenstra, Arjen K. and Thomé, Emmanuel and Bos, Joppe W. and Gaudry, Pierrick and Kruppa, Alexander and Montgomery, Peter L. and Osvik, Dag Arne and te Riele, Herman and Timofeev, Andrey and Zimmermann, Paul},
      title = {Factorization of a 768-bit {RSA} modulus},
      booktitle = {Advances in Cryptology---{CRYPTO} 2010},
      series = {Lecture Notes in Comput. Sci.},
      volume = {6223},
      pages = {333--350},
      publisher = {Springer, Berlin},
      year = {2010},
      mrclass = {94A60 (11T71)},
      mrnumber = {2725602},
      doi = {10.1007/978-3-642-14623-7_18},
      zblnumber = {1196.11167},
      }
  • [Lc] Go to document L. Le Cam, "An approximation theorem for the Poisson binomial distribution," Pacific J. Math., vol. 10, pp. 1181-1197, 1960.
    @ARTICLE{Lc,
      author = {Le Cam, Lucien},
      title = {An approximation theorem for the {P}oisson binomial distribution},
      journal = {Pacific J. Math.},
      fjournal = {Pacific Journal of Mathematics},
      volume = {10},
      year = {1960},
      pages = {1181--1197},
      issn = {0030-8730},
      mrclass = {62.15 (60.30)},
      mrnumber = {0142174},
      mrreviewer = {F. L. Spitzer},
      zblnumber = {0118.33601},
      doi = {10.2140/pjm.1960.10.1181},
      }
  • [K] Go to document T. G. Kurtz, "Solutions of ordinary differential equations as limits of pure jump Markov processes," J. Appl. Probability, vol. 7, iss. 1, pp. 49-58, 1970.
    @ARTICLE{K,
      author = {Kurtz, Thomas G.},
      title = {Solutions of ordinary differential equations as limits of pure jump {M}arkov processes},
      journal = {J. Appl. Probability},
      fjournal = {Journal of Applied Probability},
      volume = {7},
      number = {1},
      year = {1970},
      pages = {49--58},
      issn = {0021-9002},
      mrclass = {60.60},
      mrnumber = {0254917},
      mrreviewer = {J. A. Beekman},
      zblnumber = {0191.47301},
      doi = {10.2307/3212147},
      }
  • [LL] Go to document H. W. Lenstra Jr., "The number field sieve: an annotated bibliography," in The Development of the Number Field Sieve, Springer, Berlin, 1993, vol. 1554, pp. 1-3.
    @INCOLLECTION{LL,
      author = {Lenstra, Jr., H. W.},
      title = {The number field sieve: an annotated bibliography},
      booktitle = {The Development of the Number Field Sieve},
      series = {Lecture Notes in Math.},
      volume = {1554},
      pages = {1--3},
      publisher = {Springer, Berlin},
      year = {1993},
      mrclass = {11-00},
      mrnumber = {1321217},
      doi = {10.1007/BFb0091535},
      zblnumber = {0806.11065f},
      }
  • [McNew] Go to document N. McNew, "The most frequent values of the largest prime divisor function," Exp. Math., vol. 26, iss. 2, pp. 210-224, 2017.
    @ARTICLE{McNew,
      author = {McNew, Nathan},
      title = {The most frequent values of the largest prime divisor function},
      journal = {Exp. Math.},
      fjournal = {Experimental Mathematics},
      volume = {26},
      year = {2017},
      number = {2},
      pages = {210--224},
      issn = {1058-6458},
      mrclass = {11N37},
      mrnumber = {3623870},
      mrreviewer = {Y.-F. S. Pétermann},
      doi = {10.1080/10586458.2016.1155188},
      zblnumber = {06752333},
      }
  • [PS] Go to document B. Pittel and G. B. Sorkin, "The satisfiability threshold for $k$-XORSAT," Combin. Probab. Comput., vol. 25, iss. 2, pp. 236-268, 2016.
    @ARTICLE{PS,
      author = {Pittel, Boris and Sorkin, Gregory B.},
      title = {The satisfiability threshold for {$k$}-{XORSAT}},
      journal = {Combin. Probab. Comput.},
      fjournal = {Combinatorics, Probability and Computing},
      volume = {25},
      year = {2016},
      number = {2},
      pages = {236--268},
      issn = {0963-5483},
      mrclass = {68Q87 (05A16 60B20)},
      mrnumber = {3455676},
      mrreviewer = {Christian Lavault},
      doi = {10.1017/S0963548315000097},
      zblnumber = {1372.68193},
      }
  • [P82] C. Pomerance, "Analysis and comparison of some integer factoring algorithms," in Computational Methods in Number Theory, Part I, Math. Centrum, Amsterdam, 1982, vol. 154, pp. 89-139.
    @INCOLLECTION{P82,
      author = {Pomerance, C.},
      title = {Analysis and comparison of some integer factoring algorithms},
      booktitle = {Computational Methods in Number Theory, {P}art {I}},
      series = {Math. Centre Tracts},
      volume = {154},
      pages = {89--139},
      publisher = {Math. Centrum, Amsterdam},
      year = {1982},
      mrclass = {10A25 (10-04)},
      mrnumber = {0700260},
      mrreviewer = {H. London},
      zblnumber = {0508.10004},
      }
  • [Picm] C. Pomerance, "The role of smooth numbers in number-theoretic algorithms," in Proceedings of the International Congress of Mathematicians, Vol. 1, 2, 1995, pp. 411-422.
    @INPROCEEDINGS{Picm,
      author = {Pomerance, Carl},
      title = {The role of smooth numbers in number-theoretic algorithms},
      booktitle = {Proceedings of the {I}nternational {C}ongress of {M}athematicians, {V}ol. 1, 2},
      venue = {{Z}ürich, 1994},
      pages = {411--422},
      publisher = {Birkhäuser, Basel},
      year = {1995},
      mrclass = {11Y05 (11A51 11Y16)},
      mrnumber = {1403941},
      mrreviewer = {Oliver Schirokauer},
      zblnumber = {0854.11047},
      }
  • [Pnotices] C. Pomerance, "A tale of two sieves," Notices Amer. Math. Soc., vol. 43, iss. 12, pp. 1473-1485, 1996.
    @ARTICLE{Pnotices,
      author = {Pomerance, Carl},
      title = {A tale of two sieves},
      journal = {Notices Amer. Math. Soc.},
      fjournal = {Notices of the American Mathematical Society},
      volume = {43},
      year = {1996},
      number = {12},
      pages = {1473--1485},
      issn = {0002-9920},
      mrclass = {11Y05 (11N35)},
      mrnumber = {1416721},
      mrreviewer = {G. Greaves},
      zblnumber = {1042.11529},
      }
  • [P96] C. Pomerance, "Multiplicative independence for random integers," in Analytic Number Theory, Vol. 2, Birkhäuser Boston, Boston, MA, 1996, vol. 139, pp. 703-711.
    @INCOLLECTION{P96,
      author = {Pomerance, Carl},
      title = {Multiplicative independence for random integers},
      booktitle = {Analytic Number Theory, {V}ol. 2},
      venue = {{A}llerton {P}ark, {IL},
      1995},
      series = {Progr. Math.},
      volume = {139},
      pages = {703--711},
      publisher = {Birkhäuser Boston, Boston, MA},
      year = {1996},
      mrclass = {11Y16 (11N25 11Y05 68Q25)},
      mrnumber = {1409387},
      mrreviewer = {Joe P. Buhler},
      zblnumber = {0865.11085},
      }
  • [Rankin] Go to document R. A. Rankin, "The difference between consecutive prime numbers," J. London Math. Soc., vol. 11, iss. 4, pp. 242-245, 1936.
    @ARTICLE{Rankin,
      author = {Rankin, R. A.},
      title = {The difference between consecutive prime numbers},
      journal = {J. London Math. Soc.},
      fjournal = {The Journal of the London Mathematical Society},
      volume = {11},
      year = {1936},
      number = {4},
      pages = {242--245},
      mrclass = {DML},
      mrnumber = {1574971},
      doi = {10.1112/jlms/s1-13.4.242},
      zblnumber = {},
      }
  • [TWZ] Go to document A. Telcs, N. Wormald, and S. Zhou, "Hamiltonicity of random graphs produced by 2-processes," Random Structures Algorithms, vol. 31, iss. 4, pp. 450-481, 2007.
    @ARTICLE{TWZ,
      author = {Telcs, András and Wormald, Nicholas and Zhou, Sanming},
      title = {Hamiltonicity of random graphs produced by 2-processes},
      journal = {Random Structures Algorithms},
      fjournal = {Random Structures \& Algorithms},
      volume = {31},
      year = {2007},
      number = {4},
      pages = {450--481},
      issn = {1042-9832},
      mrclass = {05C80 (05C40 05C45 60C05)},
      mrnumber = {2362639},
      mrreviewer = {Edward A. Bender},
      doi = {10.1002/rsa.20133},
      zblnumber = {1129.05026},
      }
  • [DW] Go to document D. Williams, Probability with Martingales, Cambridge University Press, Cambridge, 1991.
    @BOOK{DW,
      author = {Williams, David},
      title = {Probability with Martingales},
      series = {Cambridge Math. Textbooks},
      publisher = {Cambridge University Press, Cambridge},
      year = {1991},
      pages = {xvi+251},
      isbn = {0-521-40455-X; 0-521-40605-6},
      mrclass = {60-01 (60G42)},
      mrnumber = {1155402},
      mrreviewer = {Jia Gang Wang},
      doi = {10.1017/CBO9780511813658},
      zblnumber = {0722.60001},
      }
  • [W] N. Wormald, "The differential equation method for random graph processes and greedy algorithms," in Lectures on Approximation and Randomized Algorithms, PWN, Warsaw, 1999, pp. 73-155.
    @INCOLLECTION{W,
      author = {Wormald, N.},
      title = {The differential equation method for random graph processes and greedy algorithms},
      booktitle = {Lectures on Approximation and Randomized Algorithms},
      note = {Karonski, M. and Prömel, H. J., eds.},
      pages = {73--155},
      publisher = {PWN, Warsaw},
      year = {1999},
      zblnumber = {0943.05073},
      }

Authors

Paul Balister

Department of Mathematical Sciences, University of Memphis, Memphis, TN, USA

Béla Bollobás

Department of Pure Mathematics and Mathematical Statistics, Cambridge, United Kingdom and Department of Mathematical Sciences, University of Memphis, Memphis, TN, USA and London Institute for Mathematical Sciences, London, United Kingdom

Robert Morris

IMPA, Rio de Janeiro, Brazil