$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

We wtorek, 6 kwietnia 2004 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Peter MIHÓK i Jozef BUCKO

(Technical University, Kosice, SK)

wygłoszą referat pod tytułem:

Additive and hereditary properties of system of objects

We use the basic elementary notions of category theory. A concrete category ${\bf C}$ is a collection of objects and arrows called morphisms. An object in a concrete category ${\bf C}$ is a set with structure. We will denote the ground-set of the object $A$ by $V(A)$. The morphism between two objects is a structure preserving mapping. Obviously, the morphisms of ${\bf C}$ have to satisfy the axioms of the category theory. The natural examples of concrete categories are: ${\bf Set}$ of sets, ${\bf FinSet}$ of finite sets, ${\bf Graph}$ of graphs, ${\bf Grp}$ of groups, ${\bf Poset}$ of partially ordered sets with structure preserving mappings, called homomorphisms of corresponding structures. For example, a simple finite hypergraph $H = (V,E)$ can be considered as a system of its hyperedges $E = \{e_1,e_2,\dots, e_m \}$, where edges are finite sets and the set of its vertices $V(H)$ is a superset of the union of hyperedges, i.e. $V \supseteq \bigcup_{i=1}^m e_i$. The following definition gives a natural generalization of graphs and hypergraphs. Let ${\bf C}$ be a concrete category. A simple system of objects of ${\bf C}$ is an ordered pair $S = (V, E)$, where $E = \{A_1,A_2,\dots, A_m \}$ is a finite set of the objects of ${\bf C}$, such that the ground-set $V(A_i)$ of each object $A_i \in E$ is a finite set with at least two elements (i.e. there are no loops) and $V \supseteq \bigcup_{i=1}^m V(A_i)$. The class of all simple systems of objects of ${\bf C}$ wil be denoted by ${\cal I}({\bf C})$. The symbols $K_0$ and $K_1$ denotes the null system $K_0 = (\emptyset, \emptyset)$ and system consisting of one isolated element, respectively. We will assume that by renaming (relabeling) the elements of the object $A$ only, we obtain always an object $A^*$ isomorphic to $A$ in every concrete category ${\bf C}$

For example, graphs can be viewed as systems of objects of a concrete category of two-element sets with bijections as arrows, digraphs are systems of objects of the category of two-element posets, hypergraps are finite set systems i.e. ${\cal I}(FinSet)$, etc. There are nice applications of systems of objects in information systems and computer science. A WAN network is a system on LANs, Internet is a system of WANs and the isomorphism in the category of LANs can be defined in a different way depending on the user requirements. The elements of the LANs are obviousely computers. Let us remark, that the $L$-structures generalizing graphs, digraphs and $k$-uniform hypergraphs are special systems of objects on category of relational structures. To generalize the results on generalized colourings of graphs to arbitrary simple systems of objects we need to define isomorphism of systems. We can do this in a natural way: Let $S_1 = (V_1, E_1)$ and $S_2 = (V_2, E_2)$ be two simple systems of objects of a given concrete category ${\bf C}$. The systems $S_1$ and $S_2$ are said to be isomorphic if there is a pair of bijection:

$$\phi : V_1 \longleftrightarrow V_2; \hspace{3cm} \psi : E_1 \longleftrightarrow E_2 ,$$

such that if $\psi(A_{1i}) = A_{2j}$ then $\phi V(A_{1i}) : V(A_{1i}) \longleftrightarrow V(A_{2j})$ is an isomorphism of the objects $A_{1i} \in E_1$ and $A_{2j} \in E_2$ in the category ${\bf C}$. The homomorphism of the systems can be defined in a similar way. The disjoint union of the systems $S_1$ and $S_2$ is the system $S_1 \cup S_2 = ( V_1 \cup V_2, E_1 \cup E_2)$, where we assume that $V_1 \cap V_2 = \emptyset$. A system is said to be connected if it cannot be expressed as a disjoint union of two systems. The subsystem of $S_1$ induced by the set $U \subseteq V(S_1)$ is $S_1[U]$, with objects $E(S_1[U]) := \{A_{1i} \in E(S_1) \vert V(A_{1i}) \subseteq U\}$. $S_2$ is an induced-subsystem of $S_1$ if it is isomorphic to $S_1[U]$ for some $U \subseteq V(S_1)$. Using these definitions we can define, analogously as for graphs, that an additive induced-hereditary property of simple systems of objects of a category ${\bf C}$ is any class of systems closed under isomorphism, induced-subsystems and disjoint union of systems. Let us denote by $^a({\bf C})$ the set of all additive induced-hereditary properties of simple systems of objects of a category ${\bf C}$. In our talk we will consider the structure of additive hereditary properties of systems of objects.

Serdecznie zapraszamy wszystkich chętnych !