Isomorphy up to complementationReportar como inadecuado

Isomorphy up to complementation - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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

Autor: Pouzet Maurice - Hamza Si Kaddour -



Documentos relacionados