Studies on hypergraphs I: Hyperforests

The theory of hyperforests has many applications in fields ranging from mathematical theories, computer sciences to industrial technologies. The purpose of this paper is to systematically outline this widely scattered theory by making use of definitions and theorems found by the author himself, so as to make it into a coherent and independent mathematical theory. The paper begins with the definition of hyperforests as hypergraphs without cycles, in a sense very much similar to that of forests being graphs without cycles. Then, the concept of decomposition is introduced for hypergraphs. The following questions are raised and answered: when is a hypergraph decomposable? How? Thereafter, twig sequences are introduced, and it is proved that if a hypergraph has a twig sequence, then all its maximal intersection sequences are twig sequences. The paper then proves the so-called fundamental theorem, which says that a hypergraph is a hyperforest if and only if it has twig sequences. After exposing a few equivalent conditions for a hypergraph to be a hyperforest, it gives a simple but important property of hyperforests, which essentially explains why the theory of hyperforests has so many applications. After that, the reader is shown a way of testing if a hypergraph is a hyperforest and of finding twig sequences for a hyperforest. The paper ends with the concept of Markov trees, which provides us with a clearer picture of hypertrees-connected hyperforests, and which provides a useful mechanism of the applications of the theory.