Isomorphy up to complementation

Abstract: Considering uniform hypergraphs, we prove that for every non-negative integer

h

there exist two non-negative integers

k

and

t

with

k l e q t

such that two

h

-uniform hypergraphs

m a t h c a l H

and

m a t h c a l H'

on the same set

V

of vertices, with

| V | g e q t

, are equal up to complementation whenever

m a t h c a l H

and

m a t h c a l H'

are

k

-{hypomorphic up to complementation}. Let

s (h)

be the least integer

k

such that the conclusion above holds and let

v (h)

be the least

t

corresponding to

k = s (h)

. We prove that

s (h) = h + 2^{l f l o o r l o g_{2} h f l o o r}

. In the special case

h = 2^{e l l}

or

h = 2^{e l l} + 1

, we prove that

v (h) l e q s (h) + h

. The values

s (2) = 4

and

v (2) = 6

were obtained in a previous work.

Recommendations

Cited In (9)

This page was built for publication: Isomorphy up to complementation