t-expansive andt-wise intersecting hypergraphs

We give a hypergraph generalization of Gallai's theorem about factor-critical graphs. This result can be used to determine ^*(r, t) forr < 3t/2, where ^*(r, t) denotes the maximum value of the fractional covering numbers oft-wise intersecting hypergraphs of rankr. Dedicated to Tibor Gallai     

Finite projective spaces and intersecting hypergraphs

Let ? be a family ofk-subsets on ann-setX andc be a real number 0 <c<1. Suppose that anyt members of ? have a common element (t ≧ 2) and every element ofX is contained in at mostc|?| members of ?. One of the results in this paper is (Theorem 2.9): If $$c = {{(q^{t - 1} + ... + q + 1)} \mathord{\left/ {\vphantom {{(q^{t - 1} + ... + q + 1)} {(q^t + ... + q + 1)}}} \right. \kern-\nulldelimiterspace} {(q^t + ... + q + 1)}}$$ . whereq is a prime power andn is sufficiently large, (n >n (k, c)) then The corresponding lower bound is given by the following construction. LetY be a (q ^t + ... +q + 1)-subset ofX andH ₁,H ₂, ...,H _|Y| the hyperplanes of thet-dimensional projective space of orderq onY. Let ? consist of thosek-subsets which intersectY in a hyperplane, i.e., ?={F∈( _k ^X ): there exists ani, 1≦i≦|Y|, such thatY∩F=H _i }.     

Great intersecting families of edges in hereditary hypergraphs

Chvátal stated in 1972 the following conjecture: If $\text{H}$ is a hereditary hypergraph on S and $\text{M}$ ? $\text{H}$ is a family of maximum cardinality of pairwise intersecting members of $\text{H}$, then there exists an x ∈ S such that d_$\text{H}$(x) = |{H ∈ $\text{H}$: x ∈ H}| = |$\text{M}$|. Berge and Schönheim proved that |$\text{M}$|?$\text{1}\text{2}$|$\text{H}$| for every $\text{H}$ and $\text{M}$. Now we prove that if there exists an $\text{M}$ ? $\text{H}$, |$\text{M}$| = $\text{1}\text{2}$|$\text{H}$| then Chvátal's conjecture is true for this $\text{H}$.     

On hypergraphs without two edges intersecting in a given number of vertices

Let X be a finite set of n-melements and suppose t ? 0 is an integer. In 1975, P. Erdös asked for the determination of the maximum number of sets in a family $\text{F}$ = {F₁,…, F_m}, F_i ? X, such that ∥F_i ∩ F_j∥ ≠ t for 1 ? i ≠ j ? m. This problem is solved for n ? n₀(t). Let us mention that the case t = 0 is trivial, the answer being 2^{n ? 1}. For t = 1 the problem was solved in [3]. For the proof a result of independent interest (Theorem 1.5) is used, which exhibits connections between linear algebra and extremal set theory.     

Critical hypergraphs for the weak chromatic number

Instead of removing a vertex or an edge from a hypergraph H, one may add to some edges of H new vertices (not necessarily belonging to V_H). The weak chromatic number of H tends to drop by this operation. This suggests the definition of an order relation ≥ on the set $\text{S}$ of all Sperner hypergraphs on a universal set V of vertices. The corresponding criticality study leads to unifying and interesting results: reconstruction of critical hypergraphs and two general characterizations of k-chromatic critical hypergraphs (k ≥ 3), from which a special characterization of 3-chromatic critical hypergraphs can be derived.     

Clustering by hypergraphs and dimensionality of cluster systems

In the present paper we discuss a new clustering procedure in the case where instead of a single metric we have a family of metrics. In this case we can obtain a partially ordered graph of clusters which is not necessarily a tree. We discuss a structure of a hypergraph above this graph. We propose two definitions of dimension for hyperedges of this hypergraph and show that for the multidimensional p-adic case both dimensions are reduced to the number of p-adic parameters.We discuss the application of the hypergraph clustering procedure to the construction of phylogenetic graphs in biology. In this case the dimension of a hyperedge will describe the number of sources of genetic diversity.     

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.     

Steiner triple systems with disjoint or intersecting subsystems

The existence of incomplete Steiner triple systems of order υ having holes of orders w and u meeting in z elements is examined, with emphasis on the disjoint (z = 0) and intersecting (z = 1) cases. When and , the elementary necessary conditions are shown to be sufficient for all values of z. Then for and υ “near” the minimum of , the conditions are again shown to be sufficient. Consequences for larger orders are also discussed, in particular the proof that when one hole is at least three times as large as the other, the conditions are again sufficient. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 58–77, 2000     

Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees

A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set E={E₁,…,E_m}, together with integers s_i and t_i (1≤s_i≤t_i≤|E_i|) for i=1,…,m. A vertex coloring φ is feasible if the number of colors occurring in edge E_i satisfies s_i≤|φ(E_i)|≤t_i, for every i≤m.In this paper we point out that hypertrees-hypergraphs admitting a representation over a (graph) tree where each hyperedge E_i induces a subtree of the underlying tree-play a central role concerning the set of possible numbers of colors that can occur in feasible colorings. We also consider interval hypergraphs and circular hypergraphs, where the underlying graph is a path or a cycle, respectively. Sufficient conditions are given for a ‘gap-free’ chromatic spectrum; i.e., when each number of colors is feasible between minimum and maximum. The algorithmic complexity of colorability is studied, too.Compared with the ‘mixed hypergraphs’-where ‘D-edge’ means (s_i,t_i)=(2,|E_i|), while ‘C-edge’ assumes (s_i,t_i)=(1,|E_i|−1)-the differences are rather significant.     

On the algorithmic complexity of coloring simple hypergraphs and steiner triple systems

In this paper we establish that decidingt-colorability for a simplek-graph whent≧3,k≧3 is NP-complete. Next, we establish that if there is a polynomial time algorithm for finding the chromatic number of a Steiner Triple system then there exists a polynomial time “approximation” algorithm for the chromatic number of simple 3-graphs. Finally, we show that the existence of such an approximation algorithm would imply that P=NP. Dedicated to Paul Erdős on his seventieth birthday     

Critical systems thinking and practice

Critical systems thinking and the methodologies associated with it were developed precisely to allow analysis of complex societal problems and intervention to resolve such problems. Early approaches employing systems ideas, such as operational research, systems analysis and systems engineering, were suitable for tackling certain well-defined problems, but were found to have limitations when faced with complex problems involving people with a variety of viewpoints and frequently at odds with one another. Systems thinkers responded with approaches such as system dynamics and organisational cybernetics to tackle complexity; soft systems methodology (SSM) and interactive planning to handle subjectivity; and critical systems heuristics to help the disadvantaged in situations involving conflict. There was a corresponding enlargement of the range of problem contexts in which they felt competent to intervene. It has been critical systems thinking, however, which has supplied the bigger picture, has allowed systems thinking to mature as a discipline and has set out how the variety of methodologies now available can be used together in a coherent manner to promote successful intervention in complex societal problem situations. This paper outlines, at the request of the editor of this special issue, my involvement in developing critical systems thinking and practice, describes its origins, nature and use, and sets out a programme for future research in the area.     

Post's closed systems and the weak chromatic number of hypergraphs

In the Post lattice of the families of closed systems (i.e. sets of boolean functions closed with respect to composition) the particular systems of monotonic functions are closely related to the classification of hypergraphs by their weak chromatic numbers. It is shown also that for k>3, the k-chromatic hypergraphs can be built from the complete graph K.     

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.     

Reconstructing graphs as subsumed graphs of hypergraphs,and some self-complementary triple systems

LetV be a set ofn elements. The set of allk-subsets ofV is denoted . Ak-hypergraph G consists of avertex-set V(G) and anedgeset , wherek≥2. IfG is a 3-hypergraph, then the set of edges containing a given vertexvεV(G) define a graphG _v . The graphs {G _v νvεV(G)} aresubsumed byG. Each subsumed graphG _v is a graph with vertex-setV(G) − v. They can form the set of vertex-deleted subgraphs of a graphH, that is, eachG _v ≽H −v, whereV(H)=V(G). In this case,G is a hypergraphic reconstruction ofH. We show that certain families of self-complementary graphsH can be reconstructed in this way by a hypergraphG, and thatG can be extended to a hypergraphG ^*, all of whose subsumed graphs are isomorphic toH, whereG andG ^* are self-complementary hypergraphs. In particular, the Paley graphs can be reconstructed in this way. This work was supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada.     

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.