Decomposition of regular hypergraphs

A $d$-block is a $0,1$-matrix in which every row has sum $d$. Let $S_n$ be the set of pairs $(k,l)$ such that the columns of any $(k + l)$-block with $n$ rows split into a $k$-block and an $l$-block. For $n \geq 5$, we prove the general necessary condition that $(k,l) \in S_n$ only if each element of $\lbrace 1, \dotsc , n \rbrace$ divides $k$ or $l$. We also determine $S_n$ for $n \leq 5$. Trivially, $S_1 = S_2 = \mathbb{N} \times \mathbb{N}$. Also $S_3 = \lbrace (k,l) : 2 \: \vert \: kl \rbrace$, $S_4 = \lbrace (k,l) : 6 \: \vert \: kl$ and $\min \lbrace k, l \rbrace \gt 1 \rbrace$, and $S_5 = \lbrace (k,l) : 3, 4, 5$ each divide $k$ or $l$, plus $11 \neq \min \lbrace k,l \rbrace \gt 7 \rbrace$.

Keywords

regular hypergraph, $0,1$-matrix, row-sum, $d$-block, indecomposable hypergraph

2010 Mathematics Subject Classification

Primary 05C65. Secondary 05B20.

Full Text (PDF format)

The second author’s research was partially supported by National Security Agency Award No. H98230-10-1-0363; and by Recruitment Program of Foreign Experts, 1000 Talent Plan, State Administration of Foreign Experts Affairs, China.

Received 14 December 2015

Published 5 January 2018