Classification of δ-invariant amalgamation classes (Q4948540)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1429784
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Classification of δ-invariant amalgamation classes |
scientific article; zbMATH DE number 1429784 |
Statements
Classification of δ-invariant amalgamation classes (English)
0 references
7 June 2000
0 references
amalgamation of graphs
0 references
generic model
0 references
direct sum
0 references
dimension function
0 references
nearly model complete theory
0 references
amalgamation property
0 references
0.7534887790679932
0 references
0.7510387897491455
0 references
0.7409267425537109
0 references
A graph \(A\) is a structure consisting of a set and a binary symmetric and irreflexive relation. The dimension \(\delta(A)\) of a finite graph \(A\) is defined as \(|A|- e(A)\), where \(|A|\) is the cardinality of \(A\) and \(e(A)\) is the number of edges in \(A\). A class \({\mathbf K}\) of finite graphs, closed under isomorphisms, is called \(\delta\)-invariant if an arbitrary graph \(A\) belongs to \({\mathbf K}\) if and only if for every subgraph \(B\) of \(A\) there is a \(B'\in{\mathbf K}\) such that \(\langle|B|, e(B)\rangle=\langle|B'|, e(B')\rangle\) and \(\delta(B)\geq 0\). A \(\delta\)-invariant class \({\mathbf K}\) is closed under subgraphs, too. A connected graph \(A\in{\mathbf K}\) contains exactly one cycle if and only if \(\delta(A)= 0\). Any graph \(A\) is said to be strong in a graph \(B\), in symbols \(A\leq B\), if \(\delta(A)\leq \delta(A')\) for all \(A'\) with \(A\subseteq A'\subseteq B\). A class \({\mathbf K}\) as above has, by definition, the (\(\leq\)-)amalgamation property if every strong extensions \(B\) and \(C\) of \(A\in{\mathbf K}\) have a common strong extension in \({\mathbf K}\). A model \(M\) is called (\({\mathbf K}\),\(\leq\))-generic if it satisfies the following conditions: 1. \(\forall A,B\) \(\exists B'\) \((A\leq M\wedge A\leq B\leq M\in{\mathbf K}\Rightarrow B'\in M\wedge B\cong_A B')\), 2. \(M\) is the union of an increasing sequence of finite strong substructures \(A_n\in{\mathbf K}\). There are exactly three possible types of \(\delta\)-invariant classes having the amalgamation property, namely: \({\mathbf K}_0\), the class of all graphs which omits \(K_2\), \({\mathbf K}_{\mathbf{1},{\mathbf m}}\), the class of all finite graphs which omits \(K_3\) and \(C^k_3\) for all \(k> m\), \(m\leq \omega\), \({\mathbf K}_{\mathbf{2},{\mathbf I}}\), the class of all finite graphs with hereditarily nonnegative dimension omitting all finite graphs \(A\) with \(\delta(A)= 0\) and \(|A|\not\in I\), where \(I\subset\omega\) such that \(\forall m,n\in I\) \((m\neq n\Rightarrow m+ n\in I)\) and \(\forall m\), \(n\leq \omega\) \((n, n+ 1\in I\Rightarrow n+ m\in I)\). The members of each class \({\mathbf K}_{\mathbf{1},{\mathbf m}}\) are characterized as direct sums of discrete graphs, \(K^n_2\), and \(C^k_3\). The members of \(\{{\mathbf K}_{\mathbf{1},{\mathbf m}}\mid m\leq \omega\}\) are all the possible classes, closed under substructures, which omit \(K_3\) but not \(K_2\), and have the amalgamation property. Each member of \({\mathbf K}_{\mathbf{2},{\mathbf I}}\) is characterized as a direct sum of a finite number of certain finite graphs and the \({\mathbf K}_{\mathbf{2},{\mathbf I}}\), \(I\subset \omega\), are all the possible \(\delta\)-invariant amalgamation classes which admit \(K_3\). Moreover, there are only countably many \(\delta\)-invariant amalgamation classes of graphs. The unique generic model up to isomorphisms of the classes \({\mathbf K}\), \({\mathbf K}_{\mathbf{1},{\mathbf m}}\), \({\mathbf K}_{\mathbf{1},\omega}\), and \({\mathbf K}_{\mathbf{2},{\mathbf I}}\), respectively, a characterized. A nearly model complete theory \(T\) is defined by the condition that every formula is equivalent in \(T\) to a Boolean combination of \(\Sigma_1\)-formulas. The theory \(T(M,{\mathbf K})\) is nearly model complete if \({\mathbf K}\) is a \(\delta\)-invariant amalgamation class.
0 references