×

Counting unlabeled structures. (English) Zbl 0618.05029

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\).
Reviewer: Yu.M.Voloshin

MSC:

05C30 Enumeration in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chang, C. C.; Keisler, H. J., Model Theory (1973), North Holland: North Holland Amsterdam · Zbl 0276.02032
[2] K. J. ComptonAdv. in Math.; K. J. ComptonAdv. in Math. · Zbl 0646.60012
[3] Erdos, P.; Kleitman, D. J.; Rothschild, B. L., Asymptotic enumeration of \(K_{l+1}\)-free graphs, (Int. Colloq. Combin. Theory. Int. Colloq. Combin. Theory, Atti die Convegni Lincei Vol. 17, Vol. 2 (1976)), 19-27, Rome
[4] Erdös, P.; Lehner, J., The distribution of the number of summands in the partitions of a positive integer, Duke Math. J., 8, 335-345 (1941) · JFM 67.0126.02
[5] Fagin, R., Probabilities on finite models, J. Symbolic Logic, 41, 50-58 (1976) · Zbl 0341.02044
[6] Fagin, R., The number of finite relational structures, Discrete Math., 19, 17-21 (1977) · Zbl 0389.05006
[7] U. Faigle and Gy. TuránDiscrete Math.; U. Faigle and Gy. TuránDiscrete Math.
[8] Ford, G. W.; Uhlenbeck, G. E., Combinatorial problems in the theory of graphs, (Proc. Nat. Acad. Sci. U.S.A., 43 (1957)), 163-167 · Zbl 0073.18603
[9] Kleitman, D. J.; Rothschid, B. L., Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc., 205, 205-220 (1975) · Zbl 0302.05007
[10] Kolaitis, Ph. G.; Prömel, H. J.; Rothschild, B. L., Asymptotic enumeration and a 0-1 law for \(m\)-clique free graphs, Bull. Amer. Math. Soc. (N. S.), 13, 160-162 (1985) · Zbl 0584.05041
[11] Ph. G. Kolaitis, H. J. Promel, and B. L. Rothschild\(K_l \)Trans. Amer. Math. Soc.; Ph. G. Kolaitis, H. J. Promel, and B. L. Rothschild\(K_l \)Trans. Amer. Math. Soc. · Zbl 0641.05025
[12] Lachlan, A. H.; Woodrow, R. E., Countable ultrahomogeneous graphs, Trans. Amer. Math. Soc., 262, 51-94 (1980) · Zbl 0471.03025
[13] Möhring, R., Problem session, Problem 1.7, in, (Rival, I., Graphs and Order (1985), Reidel: Reidel Dordrecht)
[14] Oberschelp, W., Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174, 53-78 (1967) · Zbl 0155.35002
[15] Wright, E. M., Graphs on unlabeled nodes with a given number of edges, Acta Math., 126, 1-9 (1971) · Zbl 0204.57202
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.