The Clique Complex and Hypergraph Matching

The width of a hypergraph is the minimal for which there exist such that for any , for some . The matching width of is the minimal such that for any matching there exist such that for any , for some . The following extension of the Aharoni-Haxell matching Theorem [3] is proved: Let be a family of hypergraphs such that for each either or , then there exists a matching such that for all . This is a consequence of a more general result on colored cliques in graphs. The proofs are topological and use the Nerve Theorem. Received June 14, 1999     

超图的Laplacian

本文讨论了由Ｆ．Ｒ．Ｋ．Ｃｈｕｎｇ 引入的ｋ－图的Ｌａｐｌａｃｉａｎ 的一些基本性质．通过引入ｋ－图的邻接图的概念,得到了ｋ－图的Ｌａｐｌａｃｉａｎ 及其特征多项式的更明确的表达式．同时,也改进了文［１］中关于ｄ－正则ｋ－图的谱值的一个下界     

On the Maximal Cut in a Random Hypergraph

Doklady Mathematics - This paper deals with the problem of finding the max-cut for random hypergraphs. We consider the classical binomial model $$H(n,k,p)$$ of a random k-uniform hypergraph on n...     

导出匹配问题的NP-完全性以及导出匹配可扩问题的CO-NP-完全性

图Ｇ的一个匹配Ｍ是导出的,若Ｍ是图Ｇ的一个导出子图。图Ｇ是导邮匹配可扩的（简记ＩＭ－可扩的）,若图Ｇ的任一导出匹配均含于图Ｇ的一个完美匹配当中。本文我们将证明如下结果。⑴对无爪图而言,问题“给定图Ｇ以及一个正整数ｒ,确定是否存在图Ｇ的一个导出匹配Ｍ使得Ｍ≥ｒ”是ＮＰ－完全的。⑵对直径为２的图以及直径为３的偶图,问题“确定一个给定图是否为导出匹配可扩的”是ＣＯ－ＮＰ完全的;而对完全多部图而言,问题“     

The Feasible Matching Problem

Let G = (V, E) be a graph and ${R\subseteq E}$ . A matching M in G is called R-feasible if the subgraph induced by the M-saturated vertices does not have an edge of R. We show that the general problem of finding a maximum size R-feasible matching in G is NP-hard and identify several natural applications of this new concept. In particular, we use R-feasible matchings to give a necessary and sufficient condition for the existence of a systems of disjoint representatives in a family of hypergraphs. This provides another Hall-type theorem for hypergraphs. We also introduce the concept of R-feasible (vertex) cover and combine it with the concept of R-feasible matching to provide a new formulation and approach to Ryser’s conjecture.     

超图在圈中的嵌入问题

H为定义在圈G上的一个超图,将H的每条超边映射为圈G中不同的路,并且这条路包含此超边中的所有的顶点,此问题称为超边在圈G中的嵌入问题(MCHEC问题).超图在圈中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小.应用组合最优化以及概率方法可得到MCHEC问题的PTAS算法.     

On Some Extremal Properties of Hypergraph Colorings

This abstract is concerned with some generalizations of classical B property and different exremal values connected with these generalizations. New improved bounds are also presented.     

On Spectral Hypergraph Theory of the Adjacency Tensor

We study both H and E/Z-eigenvalues of the adjacency tensor of a uniform multi-hypergraph and give conditions for which the largest positive H or Z-eigenvalue corresponds to a strictly positive eigenvector. We also investigate when the E-spectrum of the adjacency tensor is symmetric.     

Hypergraph polytopes

We investigate a family of polytopes introduced by E.M. Feichtner, A. Postnikov and B. Sturmfels, which were named nestohedra. The vertices of these polytopes may intuitively be understood as constructions of hypergraphs. Limit cases in this family of polytopes are, on the one end, simplices, and, on the other end, permutohedra. In between, as notable members one finds associahedra and cyclohedra. The polytopes in this family are investigated here both as abstract polytopes and as realized in Euclidean spaces of all finite dimensions. The later realizations are inspired by J.D. Stasheff ?s and S. Shnider?s realizations of associahedra. In these realizations, passing from simplices to permutohedra, via associahedra, cyclohedra and other interesting polytopes, involves truncating vertices, edges and other faces. The results presented here reformulate, systematize and extend previously obtained results, and in particular those concerning polytopes based on constructions of graphs, which were introduced by M. Carr and S.L. Devadoss.     

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.     

超图拉格朗日函数

超图拉格朗日函数是极值组合中的一个有效工具,本文回顾其在几个重要问题中的应用并提出与超图拉格朗日函数相关的公开问题.     

Hypergraph connectivity augmentation

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

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.     

Flow Hypergraph Reducibility

Reducible flow graphs were first defined by Hecht and Ullman in terms of intervals; another definition, based on two flow graph transformations, was also presented. In this paper, we extend the notion of reducibility to directed hypergraphs, proving that the interval and the transformation approaches are still equivalent when applied to this family.