A. Paweł WOJDA & Artur SZYMAŃSKI

(WMS, AGH)

Permutacje samodopełniające k-jednolitych hipergrafów samodopełniających

Hipergraf nazywamy k-jednolitym jeśli każda jego krawędź ma k elementów. k-jednolity hipergraf $H=(V;E)$ jest samodopełniający jeśli jest izomorficzny ze swoim dopełnieniem $\overline{H}=(V;{V \choose k}-E)$, to znaczy jeśli istnieje permutacja $\sigma$ (zwana samodopełniającą) zbioru wierzchołków $V$ taka, że funkcja $\sigma^*:V \rightarrow {V \choose k}-E$ zdefiniowana wzorem: $\sigma^*(e)=\{\sigma (x)\vert x\in e\}$ jest bijekcją. Podczas seminarium w listopadzie ub. roku zaprezentowaliśmy dowód faktu, że k-jednolity hipergraf rzędu n istnieje wtedy i tylko wtedy, gdy $n \choose k$ jest liczbą parzystą. Wynik ten jest odpowiednikiem dobrze znanego twierdzenia dla grafów samodopełniających rzędu n - wiadomo (Ringel (1963) i Sachs (1962)), że istnieją jeśli $n \equiv 0,\ 1$ (mod 4), a więc wtedy i tylko wtedy gdy $n \choose 2$ jest parzyste.
Ringel i Sachs podali także bardzo prostą charakteryzację permutacji samodopełniających dla grafów: permutacja jest samodopełniającą dla pewnego grafu o zbiorze wierzchołków $V$, wtedy i tylko wtedy, gdy wszystkie jej orbity mają liczność podzielną przez 4, poza dokładnie jedną orbitą jednoelementową w przypadku gdy $\vert V\vert\equiv 1$ (mod 4).
Podczas seminarium przedstawimy analog tego twierdzenia dla hipergrafów k-jednolitych.

Serdecznie zapraszamy wszystkich chętnych !