Journal of Combinatorics

Volume 7 (2016)

Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

Isomorphy up to complementation

Pages: 285 – 305

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n2.a5

Authors

Maurice Pouzet (ICJ, Mathématiques, Université Claude-Bernard Lyon, Villeurbanne, France; and Mathematics and Statistics Department, University of Calgary, Alberta, Canada)

Hamza Si Kaddour (ICJ, Mathématiques, Université Claude-Bernard Lyon, Villeurbanne, France; and Mathematics and Statistics Department, University of Calgary, Alberta, Canada)

Abstract

Considering uniform hypergraphs, we prove that for every non-negative integer $h$ there exist two non-negative integers $k$ and $t$ with $k\leq t$ such that two $h$-uniform hypergraphs ${\mathcal H}$ and ${\mathcal H}'$ on the same set $V$ of vertices, with $\vert V\vert \geq t$, are equal up to complementation whenever ${\mathcal H}$ and ${\mathcal 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^{\lfloor\log_2 h\rfloor}$. In the special case $h=2^{\ell}$ or $h=2^{\ell}+1$, we prove that $v(h)\leq s(h)+h$. The values $s(2)=4$ and $v(2)=6$ were obtained in [9].

Keywords

graph, hypergraph, reconstruction, incidence matrices, Ramsey’s theorem

2010 Mathematics Subject Classification

05C50, 05C60

Full Text (PDF format)

Published 23 February 2016