Isomorphy up to complementationReport as inadecuate

Isomorphy up to complementation - Download this document for free, or read online. Document in PDF available to download.

1 LAPCS - Laboratoire de Probabilités, Combinatoire et Statistique 2 ICJ - Institut Camille Jordan Villeurbanne

Abstract : 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 sh be the least integer k such that the conclusion above holds and let vh be the least t corresponding to k = sh. We prove that sh = h + 2 ⌊log 2 h⌋ . In the special case h = 2 or h = 2 + 1, we prove that vh ≤ sh + h. The values s2 = 4 and v2 = 6 were obtained in 9.

Keywords : reconstruction graph hypergraph Ramsey-s theorem. incidence matrices

Author: Pouzet Maurice - Hamza Si Kaddour -



Related documents