Record number :
1455834
Title of article :
On induced acyclic subgraphs in sparse random digraphs
Author/Authors :
Dutta، نويسنده , , Kunal and Subramanian، نويسنده , , C.R.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2011
Pages :
6
From page :
319
To page :
324
Abstract :
Given a simple directed graph D = ( V , A ) , let the size of the largest induced directed acyclic subgraph (dag) be denoted by mas(D). Let D ∈ D ( n , p ) be a random instance, obtained by choosing each of the ( n 2 ) possible undirected edges independently with probability 2 p and then orienting each chosen edge independently in one of two possible directions with probabibility 1/2. We obtain improved bounds on the concentration width and lower bound of mas(D). Our main result is that there exists C ∈ R + such that for all p ⩾ C / n m a s ( D ) ⩾ ⌊ 2 log q d − X ⌋ where q = ( 1 − p ) − 1 , d = n p , X = W / ( ln q ) and W is a suitably large positive constant. In the case p ⩽ n − 1 / 2 , this improves the previously known lower bound of [Spencer, J. and Subramanian, C.R., (2008). “On the size of induced acyclic subgraphs in random digraphs”, Disc. Math. and Theoret. Comp. Sci., 10:2, 47–54], which had an O ( ln ln d / ln q ) term instead of X.
Keywords :
Random digraph , induced acyclic subgraph , Second Moment method , Talagrand?s inequality
Journal title :
Electronic Notes in Discrete Mathematics
Link To Document :