首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A scaling limit for the length of the longest cycle in a sparse random digraph
Authors:Michael Anastos  Alan Frieze
Abstract:We discuss the length urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0001 of the longest directed cycle in the sparse random digraph urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0002, urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0003 constant. We show that for large urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0004 there exists a function urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0005 such that urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0006 a.s. The function urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0007 where urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0008 is a polynomial in urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0009. We are only able to explicitly give the values urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0010, although we could in principle compute any urn:x-wiley:rsa:media:rsa21030:rsa21030-math-0011.
Keywords:longest cycle  random digraphs  scaling limit
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号