Classification of δ-invariant amalgamation classes
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.
- A.D. Taimanov and model theory in Kazakhstan
- Determined theories and limit laws
- Metrically universal generic structures in free amalgamation classes
- Classification of Finite Completions of a Class of LocallyD8Amalgams, II
- Expansions of geometries
- Notes on Quasiminimality and Excellence
- Constructing ω-stable structures: rank 2 fields
- Examples of weak amalgamation classes
- Ab initio generic structures which are superstable but not -stable
This page was built for publication: Classification of δ-invariant amalgamation classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4948540)