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.     

Enumeration of Maximum Acyclic Hypergraphs

Abstract Acyclic hypergraphs are analogues of forests in graphs.They are very useful in the design ofdatabases. In this article,the maximum size of an acvclic hypergraph is determined and the number of maximumγ-uniform acyclic hypergraphs of order n is shown to be (_(r-1)~n)(n(r-1)-r~2 2r)~(n-r-1).     

Finding the K shortest hyperpaths using reoptimization

We present some reoptimization techniques for computing (shortest) hyperpath weights in a directed hypergraph. These techniques are exploited to improve the worst-case computational complexity (as well as the practical performance) of an algorithm finding the K shortest hyperpaths in acyclic hypergraphs.     

Acyclic Hypergraph Projections

Hypergraphs can be partitioned into two classes: tree (acyclic) hypergraphs and cyclic hypergraphs. This paper analyzes a new class of cyclic hypergraphs called Xrings. HypergraphHis an Xring if the hyperedges ofHcan be circularly ordered so that for every vertex, all hyperedges containing the vertex are consecutive; in addition, the vertices of no hyperedge may be a subset of the vertices of another hyperedge, and no vertex may appear in exactly one hyperedge. LetH₁andH₂be two hypergraphs. A tree projection ofH₁with respect toH₂is an acyclic hypergraphH₃such that the vertices of each hyperedge inH₁appear among the vertices of some hyperedge ofH₃and the vertices of each hyperedge inH₃appear among the vertices of some hyperedge ofH₂. A polynomial time algorithm is presented for deciding, given XringH₁and arbitrary hypergraphH₂, whether there exists a tree projection ofH₂with respect toH₁. It is shown that hypergraphHis an Xring iff a modified adjacency graph ofHis a circular-arc graph. A linear time Xring recognition algorithm, for GYO reduced hypergraphs as inputs, is presented.     

AN INVARIANT FOR HYPERGRAPHS

ＡＮＩＮＶＡＲＩＡＮＴＦＯＲＨＹＰＥＲＧＲＡＰＨＳＷＡＮＧＪＩＡＮＦＡＮＧ（ＩｎｓｔｉｔｕｔｅｏｆＡＰＰｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，ＣｈｉｎａａｎｄＡｓｉａ－Ｐａｃｉｆ...     

Ordering uniform supertrees by their spectral radii

A supertree is a connected and acyclic hypergraph. For a hypergraph H, the maximal modulus of the eigenvalues of its adjacency tensor is called the spectral radius of H. By applying the operation of moving edges on hypergraphs and the weighted incidence matrix method, we determine the ninth and the tenth k-uniform supertrees with the largest spectral radii among all k-uniform supertrees on n vertices, which extends the known result.     

Cellular resolutions of cointerval ideals

Minimal cellular resolutions of the edge ideals of cointerval hypergraphs are constructed. This class of d-uniform hypergraphs coincides with the complements of interval graphs (for the case d?=?2), and strictly contains the class of ‘strongly stable’ hypergraphs corresponding to pure shifted simplicial complexes. The polyhedral complexes supporting the resolutions are described as certain spaces of directed graph homomorphisms, and are realized as subcomplexes of mixed subdivisions of the Minkowski sums of simplices. Resolutions of more general hypergraphs are obtained by considering decompositions into cointerval hypergraphs.     

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.     

无标号真严格(d)-连通无圈超图的计数

本文得到了无标号真严格(d)-连通无圈超图的计数公式,并得到了无标号真严格(d)-连通同胚k不可约无圈超图的计数公式.     

On the discovery of the cycle-axiom of hypergraphs

In this paper, the path through which the cycle axiom of hypergraphs was discovered will be retraced. The long process of discovery will be described, in particular how acyclic hypergraphs originated from the study of relational database schemes and how cycles of hypergraphs originated from the study of acyclic hypergraphs.     

Embeddings and Ramsey numbers of sparse <Emphasis Type="Italic">κ</Emphasis>-uniform hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [3] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [6,23] the same result was proved for 3-uniform hypergraphs. Here we extend this result to κ-uniform hypergraphs for any integer κ ≥ 3. As in the 3-uniform case, the main new tool which we prove and use is an embedding lemma for κ-uniform hypergraphs of bounded maximum degree into suitable κ-uniform ‘quasi-random’ hypergraphs.     

On non-strong jumping numbers and density structures of hypergraphs

Estimating Turán densities of hypergraphs is believed to be one of the most challenging problems in extremal set theory. The concept of ‘jump’ concerns the distribution of Turán densities. A number α∈[0,1) is a jump for r-uniform graphs if there exists a constant c>0 such that for any family F of r-uniform graphs, if the Turán density of F is greater than α, then the Turán density of F is at least α+c. A fundamental result in extremal graph theory due to Erd?s and Stone implies that every number in [0,1) is a jump for graphs. Erd?s also showed that every number in [0,r!/r^r) is a jump for r-uniform hypergraphs. Furthermore, Frankl and Rödl showed the existence of non-jumps for hypergraphs. Recently, more non-jumps were found in [r!/r^r,1) for r-uniform hypergraphs. But there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we propose a new but related concept-strong-jump and describe several sequences of non-strong-jumps. It might help us to understand the distribution of Turán densities for hypergraphs better by finding more non-strong-jumps.     

On Axioms Contituting the Foundation of Hypergraph Theory

Hypergraphs are systems of finite sets, being the most general structures in discrete mathematics and powerful tools in dealing with discrete systems. In general, a branch of mathematics is built on some axioms. Informational scientists introduced the acyclic axiom for hypergraphs. In this paper, we first list several results concerning acyclic hypergraphs, in order to show that Acyclic-Axioms constitute the foundation of acyclic hypergraph theory. Then we give the basic theorem which shows that the Cycle-Axiom covers the Acyclic-Axioms and constitutes the foundation of hypergraph theory.     

Ramsey numbers of sparse hypergraphs

Chvátal, Rödl, Szemerédi and Trotter [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, The Ramsey number of a graph with a bounded maximum degree, J. Combinatorial Theory B 34 (1983), 239–243] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, 3-uniform hypergraphs of bounded degree have linear Ramsey numbers, submitted] and [B. Nagle, S. Olsen, V. Rödl and M. Schacht, On the Ramsey number of sparse 3-graphs, preprint] the same result was proved for 3-uniform hypergraphs. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, submitted] we extended this result to k-uniform hypergraphs for any integer $k\ge 3$. As in the 3-uniform case, the main new tool which we proved and used is an embedding lemma for k-uniform hypergraphs of bounded maximum degree into suitable k-uniform ‘quasi-random’ hypergraphs.     

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.     

Circular representation problem on hypergraphs

A hypergraph J=(X,E) is said to be circular representable, if its vertices can be placed on a circle, in such way that every edge of H induces an interval. This concept is a translation into the vocabulary of hypergraphs of the circular one's property for the (0, 1) matrices [6] studied by Tucker [9, 10]. We give here a characterization of the hypergraphs which are circular representable. We study when the associated representation is unique, and we characterize the possible transformations of a representation into another, a kind of problem which has already been treated from the algorithmic point of view by Booth and Lueker [1] or Duchet [2] in the case of the interval representable hypergraphs.Finally, we establish a connection between circular graphs and circular representable hypergraphs of the type of the Fulkerson-Gross connection between interval graphs and matrices having the consecutive one's property [5], in some special cases.     

Graph homotopy and Graham homotopy

Simple-homotopy for cell complexes is a special type of topological homotopy constructed by elementary collapses and elementary expansions. In this paper, we introduce graph homotopy for graphs and Graham homotopy for hypergraphs and study the relation between the two homotopies and the simple-homotopy for cell complexes. The graph homotopy is useful to describe topological properties of discretized geometric figures, while the Graham homotopy is essential to characterize acyclic hypergraphs and acyclic relational database schemes.     

Boolean formulae, hypergraphs and combinatorial topology

With a view toward studying the homotopy type of spaces of Boolean formulae, we introduce a simplicial complex, called the theta complex, associated to any hypergraph, which is the Alexander dual of the more well-known independence complex. In particular, the set of satisfiable formulae in k-conjunctive normal form with ?n variables has the homotopy type of Θ(Cube(n,n−k)), where Cube(n,n−k) is a hypergraph associated to the (n−k)-skeleton of an n-cube. We make partial progress in calculating the homotopy type of theta for these cubical hypergraphs, and we also give calculations and examples for other hypergraphs as well. Indeed studying the theta complex of hypergraphs is an interesting problem in its own right.     

Canonical and monophonic convexities in hypergraphs

Known properties of “canonical connections” from database theory and of “closed sets” from statistics implicitly define a hypergraph convexity, here called canonical convexity (c-convexity), and provide an efficient algorithm to compute c-convex hulls. We characterize the class of hypergraphs in which c-convexity enjoys the Minkowski-Krein-Milman property. Moreover, we compare c-convexity with the natural extension to hypergraphs of monophonic convexity (or m-convexity), and prove that: (1) m-convexity is coarser than c-convexity, (2) m-convexity and c-convexity are equivalent in conformal hypergraphs, and (3) m-convex hulls can be computed in the same efficient way as c-convex hulls.