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 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