On the Existence of Friendship Hypergraphs

A 3‐uniform friendship hypergraph is a 3‐uniform hypergraph in which, for all triples of vertices x, y, z there exists a unique vertex w, such that , and are edges in the hypergraph. Sós showed that such 3‐uniform friendship hypergraphs on n vertices exist with a so‐called universal friend if and only if a Steiner triple system, exists. Hartke and Vandenbussche used integer programming to search for 3‐uniform friendship hypergraphs without a universal friend and found one on 8, three nonisomorphic on 16 and one on 32 vertices. So far, these five hypergraphs are the only known 3‐uniform friendship hypergraphs. In this paper we construct an infinite family of 3‐uniform friendship hypergraphs on 2^k vertices and edges. We also construct 3‐uniform friendship hypergraphs on 20 and 28 vertices using a computer. Furthermore, we define r‐uniform friendship hypergraphs and state that the existence of those with a universal friend is dependent on the existence of a Steiner system, . As a result hereof, we know infinitely many 4‐uniform friendship hypergraphs with a universal friend. Finally we show how to construct a 4‐uniform friendship hypergraph on 9 vertices and with no universal friend.     

On the α-spectra of Uniform Hypergraphs and Its Associated Graphs

For 0 ≤α 1 and a k-uniform hypergraph H, the tensor A_α(H) associated with H is defined as A_α(H) = αD(H) +(1-α)A(H), where D(H) and A(H) are the diagonal tensor of degrees and the adjacency tensor of H, respectively. The α-spectra of H is the set of all eigenvalues of A_α(H) and the α-spectral radius ρ_α(H) is the largest modulus of the elements in the spectrum of A_α(H). In this paper we define the line graph L(H) of a uniform hypergraph H and prove that ρ_α(H) ≤■ρ_α(L(H)) + 1 + α(Δ-1-δ~*/k), where Δ and δ~* are the maximum degree of H and the minimum degree of L(H), respectively. We also generalize some results on α-spectra of G~(k,s), which is obtained from G by blowing up each vertex into an s-set and each edge into a k-set where 1 ≤ s ≤ k/2.     

超图中的着色问题

本文是近三十年来有关超图中涉及的着色问题的综述。它包含了有关超图着色中的基本结果,临界可着色性,２－可着色性,非２－可着色性以及在超图中与顶点着色、边着色和其它着色相关的极值问题。     

Extremality of Graph Entropy Based on Degrees of Uniform Hypergraphs with Few Edges

Let $$\mathcal{H}$$     

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

研究了一般的标号严格(d)-连通无圈超图的计数,得到了n阶标号严格(d)-连通无圈超图的计数公式.     

线图泛圈性的一个充分条件

本文证明了如果Ｇ是２连通线图,Ｇ不是圈,ｎ＝｜Ｖ（Ｇ）｜≥９且Ｇ的每个同构于Ａ的导出子图都满足（ａ１,ａ２）,则Ｇ是泛圈图     

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.     

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

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

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

The Degree‐Diameter Problem for Claw‐Free Graphs and Hypergraphs

We study the degree‐diameter problem for claw‐free graphs and 2‐regular hypergraphs. Let be the largest order of a claw‐free graph of maximum degree Δ and diameter D. We show that , where , for any D and any even . So for claw‐free graphs, the well‐known Moore bound can be strengthened considerably. We further show that for with (mod 4). We also give an upper bound on the order of ‐free graphs of given maximum degree and diameter for . We prove similar results for the hypergraph version of the degree‐diameter problem. The hypergraph Moore bound states that the order of a hypergraph of maximum degree Δ, rank k, and diameter D is at most . For 2‐regular hypergraph of rank and any diameter D, we improve this bound to , where . Our construction of claw‐free graphs of diameter 2 yields a similar result for hypergraphs of diameter 2, degree 2, and any even rank .     

4一致(ξ)-超图的最小边数的上界

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

关于Hamltion线图的一个结果

设Ｇ是一个简单图，(?)ｅ∈Ｅ（Ｇ），定义ｅ＝ｕｖ在Ｇ中的度ｄ（ｅ）＝ｄ（ｕ）＋ｄ（ｖ），其中ｄ（ｕ）和ｄ（ｖ）分别为ｕ和ｖ的度数。若连通图Ｇ的每个桥都有一个端点度数为１，则称Ｇ是几乎无桥的图。本文的主要结果是：设Ｇ是ｐ≥２阶几乎无桥的简单连通图，且Ｇ≠Ｋ_{１，ｐ－１}若对任何无公共顶点的两边ｅ₀及ｅ₁，ｄ（ｅ₀）＋ｄ（ｅ₁）≥ｐ＋４，则Ｇ有一个Ｄ－闭迹，从而Ｇ的线图Ｌ（Ｇ）是哈密顿的。     

Hypergraph limits: A regularity approach

A sequence of k‐uniform hypergraphs is convergent if the sequence of homomorphism densities converges for every k‐uniform hypergraph F. For graphs, Lovász and Szegedy showed that every convergent sequence has a limit in the form of a symmetric measurable function . For hypergraphs, analogous limits were constructed by Elek and Szegedy using ultraproducts. These limits had also been studied earlier by Hoover, Aldous, and Kallenberg in the setting of exchangeable random arrays. In this paper, we give a new proof and construction of hypergraph limits. Our approach is inspired by the original approach of Lovász and Szegedy, with the key ingredient being a weak Frieze‐Kannan type regularity lemma. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 205–226, 2015     

Forbidding Complete Hypergraphs as Traces

Let 2 ≤q ≤min{p, t − 1} be fixed and n → ∞. Suppose that is a p-uniform hypergraph on n vertices that contains no complete q-uniform hypergraph on t vertices as a trace. We determine the asymptotic maximum size of in many cases. For example, when q = 2 and p∈{t, t + 1}, the maximum is , and when p = t = 3, it is for all n≥ 3. Our proofs use the Kruskal-Katona theorem, an extension of the sunflower lemma due to Füredi, and recent results on hypergraph Turán numbers. Research supported in part by NSF grants DMS-0400812 and an Alfred P. Sloan Research Fellowship. Research supported in part by NSA grant H98230-06-1-0140. Part of the research conducted while his working at University of Illinois at Chicago as a NSF VIGRE postdot.     

Super-Magic Complete k-Partite Hypergraphs

 We deal with complete k-partite hypergraphs and we show that for all k≥2 and n≠2,6 its hyperedges can be labeled by consecutive integers 1,2,…,n ^k such that the sum of labels of the hyperedges incident to (k−1) particular vertices is the same for all (k−1)-tuples of vertices from (k−1) independent sets. Received: December 8, 1997 Final version received: July 26, 1999     

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

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

A Hypergraph Version of a Graph Packing Theorem by Bollobás and Eldridge

Two n‐vertex hypergraphs G and H pack, if there is a bijection such that for every edge , the set is not an edge in H. Extending a theorem by Bollobás and Eldridge on graph packing to hypergraphs, we show that if and n‐vertex hypergraphs G and H with with no edges of size 0, 1, and n do not pack, then either

1. one of G and H contains a spanning graph‐star, and each vertex of the other is contained in a graph edge, or
2. one of G and H has edges of size not containing a given vertex, and for every vertex x of the other hypergraph some edge of size does not contain x.

     

混合超图的染色理论

混合超图是含有两种超边的超图，一种称为D-超边，一种称为C-超边，它们的区别主要体现在染色要求上．混合超图的染色，要求每-D-超边至少有两个点染不同的颜色，每一C-超边至少有两个点染相同的颜色．用颜色最多的染色所用的颜色数称为该混合超图的上色数，用颜色最少的染色所用的颜色数称为该混合超图的下色数．混合超图的染色理论是目前国际组合学界比较新的研究课题之一．本文主要概括介绍关于混合超图染色理论已经取得的一些成果，其中包含本文作者的研究成果．并提出了一些可供进一步研究的问题．     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.