### Self-complementing permutations of k-uniform hypergraphs

*Artur Szymański, Adam Paweł Wojda*

#### Abstract

A k-uniform hypergraph H=(V;E) is said to be

*self-complementary*whenever it is isomorphic with its complement H=(V;(V choose k)-E). Every permutation σ of the set V such that σ(e) is an edge of H if and only if e ∈E is called*self-complementing*. 2-self-comlementary hypergraphs are exactly self complementary graphs introduced independently by Ringel (1963) and Sachs (1962). For any positive integer n we denote by λ(n) the unique integer such that n=2^{λ(n)}c, where c is odd. In the paper we prove that a permutation σ of [1,n] with orbits O_{1}, ...,O_{m}is a self-complementing permutation of a k-uniform hypergraph of order n if and only if there is an integer l ≥0 such that k=a2^{l}+s, a is odd, 0 ≤s < 2^{l}and the following two conditions hold: (i) n=b2^{l+1}+r, r ∈{ 0, ...,2^{l}-1+s}, and (ii) Σ_{i:λ(|Oi|) ≤l}|O_{i}| ≤r. For k=2 this result is the very well known characterization of self-complementing permutation of graphs given by Ringel and Sachs.Full Text: PDF PostScript