Counting unlabeled structures
type: Item
instance of: scholarly article
title: Counting unlabeled structures
zbMATH Open document ID: 0618.05029
DOI: 10.1016/0097-3165(87)90061-6
author: Hans Jürgen Prömel
published in: Journal of Combinatorial Theory. Series A
publication date: 1987-01-01T00:00:00Z
review text: 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…
Mathematics Subject Classification ID: 05C30
zbMATH DE Number: 4002125
zbMATH Keywords: enumeration of structures
zbMATH Keywords: asymptotics
MaRDI profile type: Publication
full work available at URL: 0097-3165(87)90061-6
OpenAlex ID: W2084131533
cites work: Model theory
cites work: A logical approach to asymptotic combinatorics I. First order properties
cites work: Q4133658
cites work: Probabilities on finite models
cites work: The number of finite relational structures
cites work: COMBINATORIAL PROBLEMS IN THE THEORY OF GRAPHS. III
cites work: Asymptotic Enumeration of Partial Orders on a Finite Set
cites work: Asymptotic enumeration and a 0-1 law for $m$-clique free graphs
cites work: K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
cites work: Countable Ultrahomogeneous Undirected Graphs
cites work: Kombinatorische Anzahlbestimmungen in Relationen
cites work: Graphs on unlabelled nodes with a given number of edges
Recommended article: Counting unlabeled \(k\)-trees
Recommended article: Finding the Description of Structure by Counting Method: A Case Study
Recommended article: On Labeled and Unlabeled Combinatorial Structures
Recommended article: Counting unbranched subgraphs
Recommended article: Q4502543
Recommended article: Statistical mechanics of unsupervised structure recognition
Recommended article: Boltzmann Sampling of Unlabelled Structures
Recommended article: Q2934614
Recommended article: Simulating the component counts of combinatorial structures
Recommended article: Counting unrooted maps using tree-decomposition
description: scientific article; zbMATH DE number 4002125