Counting unlabeled structures

In the paper the author very visually demonstrates how can be enumerated some unlabeled structures with one binary relation when we can enumerate the corresponding labeled structures without any nontrivial automorphisms. Since rich enough classes of labeled structures with one binary relation consist of structures almost all of which are rigid, i.e. they have no nontrivial automorphisms, including such classes as all graphs, all directed graphs, all tournaments, for which mentioned above behavior is well known. Using the rigidity both of classes of \(\ell\)- colorable graphs for \(\ell \geq 2\) and of the partial orders the author obtains some new results in asymptotic enumeration of the corresponding unlabeled classes. Let E be an infinite class of finite labeled structures (with exactly one binary relation) which is closed under (induced) substructures and isomorphisms. Every element in E is assumed to be defined for some n. Let \(E^ u\) be the class of unlabeled structures corresponding to E, i.e. \(E^ u\) is the set of all isomorphism types of structures in E. Let C(n) (and \(C^ u(n))\) be the number of structures in E (in \(E^ u)\) defined on n; and obviously \(C(n)/n!\leq C^ u(n)\). The main result is the Main Lemma: Assume that E satisfies the growth condition \[ cn^ 2+dn+\zeta (n)\leq \log_ 2C(n)<cn^ 2+dn+\xi (n) \] for all n where \(c>0\), d is arbitrary and \(\zeta (n)=o(n)\), \(\xi (n)=o(n)\). Then there is a constant s such that for all n, \[ C^ u(n)\leq C(n)/n!(1+s/2^{cn}). \] As applications of this Lemma the following corollaries are obtained: 1. A graph is \(K_{\ell +1}\)-free if it does not contain a complete graph \(K_{\ell +1}\) with vertices as a subgraph. Let \(\ell \geq 2\), \(S^ u_{\ell}(n)\) \((L^ u_{\ell}(n))\) denote the number of unlabeled \(K_{\ell +1}\)-free graphs on n vertices (and \(\ell\)-colorable graphs, correspondently). Then for any polynomial q(n) there is a constant d such that for all n \[ L^ u_{\ell}(n)\leq S^ u_{\ell}(n)\leq L^ u_{\ell}(n)(1+d/q(n)). \] 2. A class of graphs which has the property that for any first order logic property \(\phi\) the asymptotic probability \(\mu\) (\(\phi)\) that the graph from the class satisfies \(\phi\) exists and is either 0 or 1, is said to have a 0-1 law. Let \(\ell \geq 2\). Then the class of unlabeled \(K_{\ell +1}\)-free graphs has a 0-1 law. 3. Let \(P^ u(n)\) denote the number of unlabeled partial orders on an n- element set. Then there exists a constant s such that for all \[ P^ u(n)\leq P(n)/n!(1+s/2^{n/4}), \] where P(n) denote the number of labeled orders. 4. The P-recognition problem is to decide whether an (unknown) order Q on n is isomorphic to the given order P. Let \(c<(\log_ 2 3)^{-1}\). Then the recognition complexity of almost all partial orders on n is at least cn log\({}_ 2n\).

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Counting unlabeled structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089001)