Discrete Mathematics & Theoretical Computer Science, Vol 11, No 1 (2009)

Font Size:  Small  Medium  Large

Self-complementing permutations of k-uniform hypergraphs

Artur Szymański, Adam Paweł Wojda


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 O1, ...,Om 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=a2l +s, a is odd, 0 ≤s < 2l and the following two conditions hold: (i) n=b2l+1+r, r ∈{ 0, ...,2l-1+s}, and (ii) Σi:λ(|Oi|) ≤l |Oi| ≤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