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\le t$ such that two $h$-uniform hypergraphs $\mathcal{H}$ and ${\mathcal{H}}^{\prime }$ on the same set $V$ of vertices, with $|V|\ge t$, are equal up to complementation whenever $\mathcal{H}$ and ${\mathcal{H}}^{\prime }$ 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^{\lfloor {\log }_{2}h\rfloor }$. In the special case $h=2^{\ell }$ or $h=2^{\ell }+1$, we prove that $v(h)\le s(h)+h$. The values $s(2)=4$ and $v(2)=6$ were obtained in a previous work.

15 pages