Interval hypergraphs and D-interval hypergraphs

A hypergraph $\text{H = (V,}\text{E}\text{)}$ is called an interval hypergraph if there exists a one-to-one function ? mapping the elements of V to points on the real line such that for each edge E, there is an interval I, containing the images of all elements of E, but not the images of any elements not in E₁. The difference hypergraph D(H) determined by H is formed by adding to $\text{E}$ all nonempty sets of the form E₁ ? E₁, where E₁ and E₁ are edges of HH is said to be a D-interval hypergraph if D(H) is an interval hypergraph. A forbidden subhypergraph characterization of D-interval hypergraphs is given. By relating D-interval hypergraphs to dimension theory for posets, we determine all 3-irreducible posets of length one.     

A deletion game on hypergraphs

Two players alternately select either a vertex or an edge of a hypergraph H, deleting it together with all the edges containing the selected vertex or edge. The player first unable to move loses and the other player wins. We analyze the game for simple classes of hypergraphs, and discuss various related questions.     

A condition for matchability in hypergraphs

An extension of Hall's theorem is proved, which gives a condition for complete matchings in a certain class of hypergraphs.Research partially supported by NSERC.     

Threshold hypergraphs

This paper deals with three generalizations of threshold graphs to hypergraphs proposed by M. Ch. Golumbic. Answering a question of M. Ch. Golumbic we show that these three definitions are not equivalent. The main results of the paper are Theorems 2.5 and 2.6 which characterize hypergraphs satisfying the most general of above definitions.     

Partitive hypergraphs

We define a new class of hypergraphs (partitive hypergraphs) which generalizes both, the set of all externally related subsets of a graph and the set of all committees of an hypergraph.We give a characterization of the partitive hypergraphs and moreover of those which are associated with hypergraphs or graphs.     

Quasi-random hypergraphs

We introduce an equivalence class of varied properties for hypergraphs. Any hypergraph possessing any one of these properties must of necessity possess them all. Since almost all random hypergraphs share these properties, we term these properties quasi-random. With these results, it becomes quite easy to show that many natural explicit constructions result in hypergraphs which imitate random hypergraphs in a variety of ways.     

Operads of hypergraphs

We construct two countable collections of operads of multidimensional cubic matrices. In every operad from one of these collections we select a suboperad such that its elements can be interpreted as some hypergraphs. We prove that all these suboperads are Epi-operads.     

A note on hypergraphs with the Helly-property

Let H be a hypergraph and t a natural number. The sets which can be written and the union of different edges of H form a new hypergraph which is denoted by H′. Let us suppose that H has the Helly property and we want to state something similar for H′. We prove a conjecture of C, Berge and two negative results.     

Edge-augmentation of hypergraphs

Received January 1995 / Revised version received February 1996 Published online March 16, 1999     

Series-parallel chromatic hypergraphs

In this paper two-terminal series-parallel chromatic hypergraphs are introduced and for this class of hypergraphs it is shown that the chromatic polynomial can be computed with polynomial complexity. It is also proved that h-uniform multibridge hypergraphs θ(h;a₁,a₂,…,a_k) are chromatically unique for h≥3 if and only if h=3 and a₁=a₂=?=a_k=1, i.e., when they are sunflower hypergraphs having a core of cardinality 2 and all petals being singletons.     

Independence in hypergraphs

Suppose an integral function (|A|)q₁ defined on the subsets of edges of a hypergraph (X,u,) satisfies the following two conditions: 1) any set W u such that |A|(|A|) for any AW is matroidally independent; 2) if W is an independent set, then there exists a unique partitionW=T₁+ T₂+...+T_v such that |T ⁱ |=(|T ⁱ |),i1:v, and for any AW, |A|(|A|) there exists a T_i such that AT_i. The form of such a function is found, in terms of parameters of generalized connected components, hypercycles, and hypertrees.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 114, pp. 196–204, 1982.     

Counting acyclic hypergraphs

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.     

Covers in hypergraphs

Let α(H) denote the stability number of a hypergraphH. The covering number ?(H) is defined as the minimal number of edges fromH to cover its vertex setV(H). The main result is the following extension of König’s wellknown theorem: If α(H′)≧|V(H′)|/2 holds for every section hypergraphH′ ofH then ?(H)≦α(H). This theorem is applied to obtain upper bounds on certain covering numbers of graphs and hypergraphs. In par ticular, we prove a conjecture of B. Bollobás involving the hypergraph Turán numbers.