Using Lagrangians of Hypergraphs to Find Non-Jumping Numbers (I)

Let r ≥ 2 be an integer. A real number is a jump for r if for any and any integer m, m ≥ r, any r-uniform graph with vertices and density at least contains a subgraph with m vertices and density at least α + c, where c = c(α) does not depend on or m. It follows from a result of Erdős, Stone, and Simonovits that every is a jump for r = 2. Erdőos asked whether the same is true for r ≥ 3. Frankl and R?dl gave a negative answer by showing an infinite sequence of non-jumping numbers for r ≥ 3. However, there are a lot of unknowns on determining whether a number is a jump for r ≥ 3. In this paper, we first find two infinite sequences of non-jumping numbers for r = 4, then we extend one of the results to every r ≥ 4. Our approach is still based on the approach developed by Frankl and R?dl. Received November 30, 2005     

Long Monochromatic Berge Cycles in Colored 4-Uniform Hypergraphs

Here we prove that for n ≥ 140, in every 3-coloring of the edges of K_n⁽⁴⁾{K_n^{(4)}} there is a monochromatic Berge cycle of length at least n − 10. This result sharpens an asymptotic result obtained earlier. Another result is that for n ≥ 15, in every 2-coloring of the edges of K_n⁽⁴⁾{K_n^{(4)}} there is a 3-tight Berge cycle of length at least n − 10.     

完全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.     

Betti Numbers of Hypergraphs

In this article, we study some algebraic properties of hypergraphs, in particular their Betti numbers. We define some different types of complete hypergraphs, which to the best of our knowledge are not previously considered in the literature. Also, in a natural way, we define a product on hypergraphs, which in a sense is dual to the join operation on simplicial complexes. For such product, we give a general formula for the Betti numbers, which specializes neatly in case of linear resolutions.     

Competition Numbers and Phytogeny Numbers of Connected Graphs and Hypergraphs

Let D be a digraph.The competition graph of D is the graph having the same vertex set with D and having an edge joining two different vertices if and only if they have at least one common out-neighbor in D.The phylogeny graph of D is the competition graph of the digraph constructed from D by adding loops at all vertices.The competition/phylogeny number of a graph is the least number of vertices to be added to make the graph a competition/phylogeny graph of an acyclic digraph.In this paper,we show that for any integer k there is a connected graph such that its phylogeny number minus its competition number is greater than k.We get similar results for hypergraphs.     

r-一致超图Ramsey函数的渐近下界(英文)

本文利用Lovasz局部引理的Spencer形式和对称形式给出r-一致超图Ramsey函数的渐近下界.证明了:对于任意取定的正整数f0,使得当n→∞时,有R~((r))(m~l,n~(k-l))≥(c-o(1))(n~(r-1)/logn)~■.特别地,R~((r))_k(n)≥(1-o(1))n/e k~■(n→∞).对于任意取定的正整数s≥r+1和常数δ>0,α≥0,如果F表示阶为s的r-一致超图,■表示阶为t的r-一致超图,且■的边数满足m(■)≥(δ-o(1))t~r/(logt)α(t→∞),则存在c=c(s,δ,α)>0,使得R~((r))(F,■)≥(c-o(1))(t~(r-1)/(logt)~l+(r-l)α)~(m(F)-l/s-r).     

On the Chromatic Numbers of Random Hypergraphs

Doklady Mathematics - The asymptotic behavior of the chromatic number of the binomial random hypergraph $$H(n,k,p)$$ is studied in the case when $$k \geqslant 4$$ is fixed, n tends to infinity, and...     

超图的强星色数

图的星色数的概念是由Ａ．Ｖｉｎｃｅ（１９８８）首次提出来的,它是图的色数的一个自然而又重要的推广,Ｌ．Ｈａｄａｄ等人（１９９４）将这一概念推广到一致超图,定义了ｈ－一致超图的强（弱）星色数,这里我们给出一般超图的强星色数的概念,研究了它的基本性质,计算了３－一致循环超图的强星色数,它们的强星色数形成了一个严格介于３和４之间的递减序列．     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

Uniform Mixed Hypergraphs: The Possible Numbers of Colors

For a mixed hypergraph , where and are set systems over the vertex set X, a coloring is a partition of X into ‘color classes’ such that every meets some class in more than one vertex, and every has a nonempty intersection with at least two classes. The feasible set of , denoted , is the set of integers k such that admits a coloring with precisely k nonempty color classes. It was proved by Jiang et al. [Graphs and Combinatorics 18 (2002), 309–318] that a set S of natural numbers is the feasible set of some mixed hypergraph if and only if either or S is an ‘interval’ for some integer k ≥ 1. In this note we consider r-uniform mixed hypergraphs, i.e. those with |C| = |D| = r for all and all , r ≥ 3. We prove that S is the feasible set of some r-uniform mixed hypergraph with at least one edge if and only if either for some natural number k ≥ r − 1, or S is of the form where S′′ is any (possibly empty) subset of and S′ is either the empty set or {r − 1} or an ‘interval’ {k, k + 1, ..., r − 1} for some k, 2 ≤ k ≤ r − 2. We also prove that all these feasible sets can be obtained under the restriction , i.e. within the class of ‘bi-hypergraphs’. Research supported in part by the Hungarian Scientific Research Fund, OTKA grant T-049613.     

完全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).     

4一致反超图的最小边数问题

混合超图是在超图的基础上添加一个反超边得到的图．超边和反超边的区别主要体现在着色要求上．在着色中,要求每一超边至少要有两个点着不同的颜色,而每一反超边至少有两个点着相同的颜色．最大最小颜色数分别称为混合超图的上色数和下色数。本文主要研究反超图,即只含反超边的超图。讨论了上色数为3的4一致超图的最小边数问题．给出了上色数为3的4一致反超图的最小边数的一个上界和一个下界．     

4一致C-超图的最小边数的上界(英文)

主要讨论了 4一致C 超图的最小边数与最小上色数的关系 ,给出了上色数为 3的 4一致C 超图的最小边数的一个上界 .     

Extremal Problems for Geometric Hypergraphs

A geometric hypergraph H is a collection of i -dimensional simplices, called hyperedges or, simply, edges, induced by some (i+1) -tuples of a vertex set V in general position in d -space. The topological structure of geometric graphs, i.e., the case d=2 , i=1 , has been studied extensively, and it proved to be instrumental for the solution of a wide range of problems in combinatorial and computational geometry. They include the k -set problem, proximity questions, bounding the number of incidences between points and lines, designing various efficient graph drawing algorithms, etc. In this paper, we make an attempt to generalize some of these tools to higher dimensions. We will mainly consider extremal problems of the following type. What is the largest number of edges (i -simplices) that a geometric hypergraph of n vertices can have without containing certain forbidden configurations? In particular, we discuss the special cases when the forbidden configurations are k intersecting edges, k pairwise intersecting edges, k crossing edges, k pairwise crossing edges, k edges that can be stabbed by an i -flat, etc. Some of our estimates are tight. Received March 4, 1996, and in revised form September 13, 1996.     

Hypergraphs and hypergroups

We associate to every hypergraph a commutative quasi-hypergroupH _qG and find a necessary and sufficient condition on so thatH is associative. For certain, any finite included, we determine a sequence= ₀, ₁,, _n of hypergraphs such that ifH ₀ ,H ₁ ,H, H _n is the sequence of the associated quasi-hypergroups,H _n is a join space.Presented by I. Rosenberg.     

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.