Bound on the number of unlabeled cographs on n vertices - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T08:28:36Z http://mathoverflow.net/feeds/question/37875 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices Bound on the number of unlabeled cographs on n vertices Bart Jansen 2010-09-06T12:17:49Z 2010-09-06T16:28:42Z <p>A cograph is a graph without induced $P_4$ subgraphs. I am looking for a reference for a simple exponential bound on the number of distinct unlabeled cographs on $n$ vertices. By <a href="http://mathworld.wolfram.com/Cograph.html" rel="nofollow">the Mathworld article on cographs</a> this is the same as the number of series-parallel networks with $n$ unlabeled edges. Judging from the first couple of terms in the list, the bound should be something like $3^n$. Any reference to a simple, exponential bound in closed-form would be much appreciated.</p> http://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices/37878#37878 Answer by Joseph O'Rourke for Bound on the number of unlabeled cographs on n vertices Joseph O'Rourke 2010-09-06T12:35:07Z 2010-09-06T13:49:57Z <p>The paper "<a href="http://arxiv.org/abs/math/0512435" rel="nofollow">Enumeration and limit laws of series-parallel graphs</a>" by Manuel Bodirsky, Omer Gimenez, Mihyun Kang, and Marc Noy, establishes that the number of <em>labeled</em> series-parallel graphs on $n$ <em>vertices</em> is asymptotically $$g \cdot n^{-\frac{5}{2}} \gamma^n n!$$ where $g$ and $\gamma$ are constants. Perhaps you can convert their bound to one for <em>unlabeled</em> graphs (by removing the $n!$ factor) in terms of <em>edges</em>.</p> http://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices/37884#37884 Answer by Emil for Bound on the number of unlabeled cographs on n vertices Emil 2010-09-06T13:12:24Z 2010-09-06T15:32:23Z <p>A cograph on $n$ vertices can be created by starting with $n$ 1-vertex graphs and then going through a procedure of at each turn either (1) complementing a graph, or (2) replacing two of your graphs with their disjoint union, and stopping when you have one graph remaining.</p> <p>The number of ways that (2) can be done is the $n$th Catalan number, and at each stage you have the option of complementing.</p> <p>I think this should give a $O(8^n)$ bound.</p> http://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices/37886#37886 Answer by Gjergji Zaimi for Bound on the number of unlabeled cographs on n vertices Gjergji Zaimi 2010-09-06T13:23:57Z 2010-09-06T13:23:57Z <p>Let your sequence be $a_n$ for the number of series-parallel networks with $n$ unlabeled edges. The following identity of generating functions holds $$1+\sum_{k=1}^{\infty}a_kx^k=\left[\frac{1}{(1-x)}\prod_{k\geq 1}\frac{1}{(1-x^k)^{a_k}}\right]^{1/2}$$ from which the asymptotics $$a_n\sim C d^n n^{-3/2}$$ follow, where $C=0.4126...$, $d=3.56083930953894...$</p> <p>See also the article "Some enumerative results on series parallel networks" by J.W. Moon.</p> http://mathoverflow.net/questions/37875/bound-on-the-number-of-unlabeled-cographs-on-n-vertices/37904#37904 Answer by David Eppstein for Bound on the number of unlabeled cographs on n vertices David Eppstein 2010-09-06T16:28:42Z 2010-09-06T16:28:42Z <p>See e.g. the <a href="http://en.wikipedia.org/wiki/Cograph" rel="nofollow">Wikipedia article on cographs</a>, which explains that isomorphism classes of cographs are in one-to-one correspondence with isomorphism classes of n-leaf rooted trees in which the internal nodes are labeled with 0's and 1's and in which, moreover, the labels are in strict alternation from root to leaf.</p> <p>Because of the alternation, the labeling part only adds a factor of two to the overall count, so really all you need to do is to count n-leaf rooted trees. So the number of cographs appear to be the numbers in <a href="http://www.research.att.com/~njas/sequences/A000084" rel="nofollow">OEIS sequence A000084</a> (the number of trees is half that, <a href="http://www.research.att.com/~njas/sequences/A000669" rel="nofollow">A000669</a>). They are asymptotic to around 3.561^n, matching Zaimi's answer.</p>