The existence of bipartite almost self-complementary 3-uniform hypergraphs

Abstract

An almost self-complementary 3-uniform hypergraph on $n$ vertices exists if and only if $n$ is congruent to 3 modulo 4 A hypergraph $H$ with vertex set $V$ and edge set $E$ is called bipartite if $V$ can be partitioned into two subsets $V_1$ and $V_2$ such that $e \cap V_{1} \neq \emptyset$ and $e \cap V_{2} \neq \emptyset$ for any $e \in E$. A bipartite self-complementary 3-uniform hypergraph $H$ with partition $(V_{1},V_{2})$ of the vertex set $V$ such that $|V_{1}|=m$ and $|V_{2}|=n$ exists if and only if either (i) $m=n$ or (ii) $m \neq n$ and either $m$ or $n$ is congruent to 0 modulo 4 or (iii) $m \neq n$ and both $m$ and $n$ are congruent to 1 or 2 modulo 4. In this paper we define a bipartite almost self-complementary 3-uniform hypergraph $H$ with partition $(V_{1},V_{2})$ of a vertex set $V$ such that $|V_{1}|=m$ and $|V_{2}|=n$ and find the conditions on $m$ and $n$ for a bipartite 3-uniform hypergraph $H$ to be almost self-complementary. We also prove the existence of bi-regular bipartite almost self-complementary 3-uniform hypergraphs.