On Extremal Hypergraphs for Hamiltonian Cycles

We study sufficient conditions for Hamiltonian cycles in hypergraphs and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields just a sufficient condition relying solely on the minimum vertex degree.     

完全3-一致超图K_n~((3))的哈密顿圈分解

基于王建方和李东给出的超图哈密顿圈的定义和Katona-Kierstead给出的超图哈密顿链的定义,近年来,国内外学者对一致超图的哈密顿圈分解的研究有一系列结果.特别是Bailey-Stevens和Meszka-Rosa研究了完全3-一致超图K_n~((3))的哈密顿圈分解,得到了n=6k+1,6k+2(k=1,2,3,4,5)的哈密顿圈分解.本文在吉日木图提出的边划分方法的基础上继续研究,得到了完全3-一致超图K_n~((3))的哈密顿圈分解的算法,由此得到了n=6k+2,6k+4(k=1,2,3,4,5,6,7),n=6k+5(k=1,2,3,4,5,6)时的圈分解.这一结果将Meszka-Rosa关于K_n~((3))的哈密顿圈分解结果从n≤32提高到了n≤46(n≠43).     

完全3-一致超图的圈分解

The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs K_n~(3) into k-cycles(3 ≤ k n) was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that K_(n·5m)~(3) can be decomposed into 5-cycles for n ∈{5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.     

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.     

Coloring Non-uniform Hypergraphs Without Short Cycles

The work deals with a generalization of Erd?s–Lovász problem concerning colorings of non-uniform hypergraphs. Let H  = (V, E) be a hypergraph and let \({{f_r(H)=\sum\limits_{e \in E}r^{1-|e|}}}\) for some r ≥ 2. Erd?s and Lovász proposed to find the value f (n) equal to the minimum possible value of f ₂(H) where H is 3-chromatic hypergraph with minimum edge-cardinality n. In the paper we study similar problem for the class of hypergraphs with large girth. We prove that if H is a hypergraph with minimum edge-cardinality n ≥ 3 and girth at least 4, satisfying the inequality $$f_r(H) \leq \frac{1}{2}\, \left(\frac{n}{{\rm ln}\, n}\right)^{2/3},$$ then H is r -colorable. Our result improves previous lower bounds for f (n) in the class of hypergraphs without 2- and 3-cycles.     

Pentagons vs. triangles

We study the maximum number of triangles in graphs with no cycle of length 5 and analogously, the maximum number of edges in 3-uniform hypergraphs with no cycle of length 5.     

On the cyclomatic number of a hypergraph

This note generalizes the notion of cyclomatic number (or cycle rank) from Graph Theory to Hypergraph Theory and links it up with the concept of planarity in hypergraphs which was recently introduced by R.P. Jones. Sharp bounds are obtained for the cyclomatic number of the planar hypergraphs and, further, it is shown that the upper bound is attainable if, and only if the hypergraph satisfies Krewera's condition.     

Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs

We investigate minimum vertex degree conditions for 3-uniform hypergraphs which ensure the existence of loose Hamilton cycles. A loose Hamilton cycle is a spanning cycle in which only consecutive edges intersect and these intersections consist of precisely one vertex.     

Chorded Cycles

A chord is an edge between two vertices of a cycle that is not an edge on the cycle. If a cycle has at least one chord, then the cycle is called a chorded cycle, and if a cycle has at least two chords, then the cycle is called a doubly chorded cycle. The minimum degree and the minimum degree-sum conditions are given for a graph to contain vertex-disjoint chorded (doubly chorded) cycles containing specified elements of the graph, i.e., specified vertices, specified edges as cycle-edges, specified paths, or specified edges as chords. Furthermore, the minimum degree condition is given for a graph to be partitioned into chorded cycles containing specified edges as cycle-edges.     

On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

On the Laplacian Spectrum and Walk-regular Hypergraphs

We use the generalization of the Laplacian matrix to hypergraphs to obtain several spectral-like results on hypergraphs. For instance, we obtain upper bounds on the eccentricity and the excess of any vertex of hypergraphs. We extend to the case of hypergraphs the concepts of walk regularity and spectral regularity, showing that all walk-regular hypergraphs are spectrally-regular. Finally, we obtain an upper bound on the mean distance of walk-regular hypergraphs that involves all the Laplacian spectrum.     

超图的最优标号与特征值

研究超图的标号性质,首先利用拉普拉斯张量的第二小和最大特征值给出4一致超图的带宽和与割宽的上下界;其次构造与超图对应的简单图,通过其拉普拉斯矩阵的特征值给出超图带宽的下界.     

Projective Dimension of String and Cycle Hypergraphs

We present a closed formula and a simple algorithmic procedure to compute the projective dimension of square-free monomial ideals associated to string or cycle hypergraphs. As an application, among these ideals we characterize all the Cohen–Macaulay ones.     

The minimal eigenvalue of the Lyapunov transform †

An (n m) hypergraph is a coupleH=(N E), where the vertex set N is {1,…n} and the edge set E is an m-element multiset of nonempty subsets of N. In this paper, we count nonisomorphic hypergraphs where isomorphism of hypergraphs is the natural extension of that of graphs. A main result is an explicit formula for the cycle index of the permutation representation of any permutation group P with object set N acting on the k-element subsets of N. By making a simple substitution in these cycle indices for P the symmetric group S_N and k=1,…,n, we obtain generating functions which enumerate various types of hypergraphs. Using the technique developed, we extend Snapper's results on characteristic polynomials of permutation representations and group characters from the case where the group has odd order to the general case.     

On extremal hypergraphs for Hamiltonian cycles

We study sufficient conditions for Hamiltonian cycles in hypergraphs, and obtain both Turán- and Dirac-type results. While the Turán-type result gives an exact threshold for the appearance of a Hamiltonian cycle in a hypergraph depending only on the extremal number of a certain path, the Dirac-type result yields a sufficient condition relying solely on the minimum vertex degree.     

关于D-完全一致混合超图上色数的一个结论的推广

混合超图的上、下色数的研究是超图研究中一个重要的话题.由于超图本身结构上的复杂性,近年来对超图色性的研究也近局限于对一些特殊图类的研究,其中完全一致混合超图是最为热门的图类之一.给出了D完全(C不完全)一致混合超图的概念,并运用组合数学中有关分划的思想和方法对该图类的色性进行了进一步的研究,对相关文献中给出的结论进行了推广,得到了一个较为一般化的结论.并在该定理的证明中得到并证明了一个关于混合超图C稳定集的重要论断,对超图色性研究有着重要的意义.     

Even Cycles in Graphs with Many Odd Cycles

It will be shown that if G is a graph of order n which contains a triangle, a cycle of length n or n−1 and at least cn odd cycles of different lengths for some positive constant c, then there exists some positive constant k=k(c) such that G contains at least kn ^1/6 even cycles of different lengths. Other results on the number of even cycle lengths which appear in graphs with many different odd length cycles will be given. Received: October 15, 1997     

On the Number of Independent Sets in Simple Hypergraphs

Extremal problems on the number of j-independent sets in uniform simple hypergraphs are studied. Nearly optimal results on the maximum number of independent sets for the class of simple regular hypergraphs and on the minimum number of independent sets for the class of simple hypergraphs with given average degree of vertices are obtained.     

Axiomatisability and hardness for universal Horn classes of hypergraphs

We consider hypergraphs as symmetric relational structures. In this setting, we characterise finite axiomatisability for finitely generated universal Horn classes of loop-free hypergraphs. An Ehrenfeucht–Fraïssé game argument is employed to show that the results continue to hold when restricted to first order definability amongst finite structures. We are also able to show that every interval in the homomorphism order on hypergraphs contains a continuum of universal Horn classes and conclude the article by characterising the intractability of deciding membership in universal Horn classes generated by finite loop-free hypergraphs.