Isomorphy up to complementation

الأصل · EN

Considering uniform hypergraphs, we prove that for every non-negative integer h there exist two non-negative integers k and t with k≤ t such that two h-uniform hypergraphs H and H' on the same set V of vertices, with | V| ≥ t, are equal up to complementation whenever H and 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 ₂ h. In the special case h=2ℓ or h=2ℓ+1, we prove that v(h)≤ s(h)+h. The values s(2)=4 and v(2)=6 were obtained in a previous work.