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

We wtorek, 14 maja 2002 roku, o godzinie 12:45

w sali 304, ³±cznik A-3-A-4, A G H

Gyula Y. KATONA

(Dept. of Comp. Sci. and Inf. Th., Budapest Univ. of Technology)

wyg³osi referat pod tytu³em:

Hamiltonian chains in hypergraphs

Let ${\cal H}$ be a $r$-uniform hypergraph on the vertex set $V({\cal H})=\{v_1, v_2,\ldots,v_n\}$ where $n>r$. A cyclic ordering $(v_1, v_2,\ldots , v_n)$ of the vertex set is called a hamiltonian chain iff for every $1\leq i\leq n$ there exists an edge $E_j$ of ${\cal H}$ such that $\{v_i, v_{i+1},\ldots, v_{i+r-1}\}=E_j$. An $r$-uniform hypergraph is $k$-edge-hamiltonian iff it still contains a hamiltonian chain after deleting any $k$ edges of the hypergraph. What is the minimum number of edges of such a hypergraph? We give lower and upper bounds for this question for several values of $r$ and $k$. We also give a Dirac-type theorem for the existence of a Hamiltonian chain.

Serdecznie zapraszamy wszystkich chêtnych !