$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH

We wtorek, 24 kwietnia 2001 roku, o godzinie 12:45

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

Peter MIHÓK

(Mathematical Institute, Slovak Academy of Sciences

oraz

Department of Applied Mathematics,

Faculty of Economics, Technical University,

Koszyce)

wygłosi referat pod tytułem:

Unique factorization theorem

for posets, hypergraphs and

other combinatorial structures.

Let $H$ be a hypergraph $H = (X,E)$, where $E$ is a system of subsets (hyperedges) of a finite set $X$ - called the set of vertices of $H$. We will consider simple hypergraphs (i.e. without loops and multiple edges) only. A simple graph $G = (V,E)$ is a simple hypergraph whose edges are $2$-element subset of the vertex set $V$. A property ${\cal P}$ of hypergraphs is any nonempty isomorphism closed class of hypergraphs. A property of hypergraphs is called hereditary if it is closed under induced-subhypergraphs and additive if it is closed under taking disjoint unions of hypergraphs. For additive hereditary properties ${\cal P}_{1}, {\cal P}_{2}, \ldots ,{\cal P}_{n}$ a hypergraph $H = (X,E)$ is said to be ( ${\cal P}_{1}, {\cal P}_{2}, \ldots ,{\cal P}_{n}$)-partitionable if its vertex set $X$ can be partitioned into sets $X_1,X_2, \dots,X_n$ such that the induced subhypergraph $H_i = (X_i,E(X_i))$ has property ${\cal P}_i$ for $i=1,2, \dots,n$. Let us denote by ${\cal P}_1{\scriptstyle \circ}{\cal P}_2{\scriptstyle \circ}\cdots{\scriptstyle \circ}{\cal P}_n$ the class of all ( ${\cal P}_{1}, {\cal P}_{2}, \ldots ,{\cal P}_{n}$)-partitionable hypergraphs. A property ${\cal R}$ of hypergraphs is ${\em reducible}$ if there are nontrivial properties ${\cal P}_1,{\cal P}_2$ such that ${\cal R} = {\cal P}_1 {\scriptstyle \circ}{\cal P}_2$, otherwise it is called ${\em irreducible}$.

We will present the Unique Factorization Theorem for additive hereditary properties of hypergraphs and a necessary and sufficient condition for the existence of uniquely ( ${\cal P}_{1}, {\cal P}_{2}, \ldots ,{\cal P}_{n}$)-partitionable hypergraphs. The presented results are generalizing the analogous statements for simple graphs.

Serdecznie zapraszamy wszystkich chętnych !