超图拉格朗日函数

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

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     

超图在圈中的嵌入问题

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

最大k—一致超图

本文刻划直径为ｄ 的最大边数的ｋ－一致超图的结构,推广了Ｏｒｅ 的一个结果     

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.     

基于超图的超网络研究综述

超网络是一般网络的一类自然推广。超网络的研究将会有助于理解“复杂系统之所以复杂”这一极其重要的问题。现实世界中,很多复杂的系统都可以用超网络描述。超网络分为基于网络的超网络与基于超图的超网络。本文主要介绍的是基于超图的超网络,首先对超图理论进行描述,然后对基于超图的超网络进行分析,接着提出了基于超图的超网络和多层超网络的转换及实例并提出了基于超图的超网络演化模型。本文最后对超网络今后的研究方向进行了探讨,其中,超网络的指标构建、动力学研究、链路预测、应用等方面还有待于深入研究。     

Ideal-Based k-Zero-Divisor Hypergraph of Commutative Rings

Let R be a commutative ring,I an ideal of R and k ≥ 2 a fixed integer.The ideal-based k-zero-divisor hypergraph HkI(R) of R has vertex set ZI(R,k),the set of all ideal-based k-zero-divisors of R,and for distinct elements x1,x2,…,xk in ZI(R,k),the set {x1,x2,…,xk} is an edge in HkI(R) if and only if x1x2…xk ∈ I and the product of the elements of any (k-1)-subset of {x1,x2,…,xk} is not in I.In this paper,we show that H3I(R) is connected with diameter at most 4 provided that x2 (∈) I for all ideal-based 3-zero-divisor hypergraphs.Moreover,we find the chromatic number of H3 (R) when R is a product of finite fields.Finally,we find some necessary conditions for a finite ring R and a nonzero ideal I of R to have H3I (R) planar.     

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.

     

具有超图合作结构的赋权Position值

具有超图交流结构的可转移效用合作对策,也称为超图对策,它由一个三元组(N,v,H)所组成,其中(N,H)是一个可转移效用对策(简称TU-对策),而(N,H)是一个超图(超网络)。在超图对策中,除Myerson值(Myerson)外,Position值(Meessen)是另一个重要的分配规则。该模型要求把超图结构中每条超边Shapley的值平均分配给它所包含的点,而不考虑每个点的交流能力或合作水平。本文引入超图结构中点的度值来度量每条超边中每个点的交流能力或合作水平,并结合Haeringer提出用于推广Shapley值的权重系统,并由此定义了具有超图合作结构的赋权Position值。我们证明了具有超图合作结构的赋权Position值可以由“分支有效性”、“冗余超边性”、“超边可分解性”、“拟可加性”、“弱积极性”和“弱能转换”六个性质所唯一确定,并且发现参与者获得的支付随其度值的增加而增加,参与者分摊的成本随其度值的增加而降低。     

A Hypergraph Framework for Optimal Model-Based Decomposition of Design Problems

Decomposition of large engineering system models is desirable sinceincreased model size reduces reliability and speed of numericalsolution algorithms. The article presents a methodology for optimalmodel-based decomposition (OMBD) of design problems, whether or notinitially cast as optimization problems. The overall model isrepresented by a hypergraph and is optimally partitioned into weaklyconnected subgraphs that satisfy decomposition constraints. Spectralgraph-partitioning methods together with iterative improvementtechniques are proposed for hypergraph partitioning. A known spectralK-partitioning formulation, which accounts for partition sizes andedge weights, is extended to graphs with also vertex weights. TheOMBD formulation is robust enough to account for computationaldemands and resources and strength of interdependencies between thecomputational modules contained in the model.     

The Linear Unicyclic Hypergraph with the Second or Third Largest Spectral Radius

The spectral radius of a uniform hypergraph is defined to be that of the adjacency tensor of the hypergraph. It is known that the unique unicyclic hypergraph with the largest spectral radius is a nonlinear hypergraph, and the unique linear unicyclic hypergraph with the largest spectral radius is a power hypergraph. In this paper we determine the unique linear unicyclic hypergraph with the second or third largest spectral radius, where the former hypergraph is a power hypergraph and the latter hypergraph is a non-power hypergraph.     

基于超图的多冲击共因失效模型

复杂冗余系统的共因失效一直是工程中亟待解决的问题.针对传统共因失效模型的缺点,利用超图概念和矩阵相似度的原理,在充分考虑了不同共同原因冲击耦合问题的基础上,提出了一种新的共因失效模型.该模型从实际统计数据出发,不需要专家分析,可以精确计算出不同共同原因冲击对系统的影响,且在实际应用中更加简单.     

关于不含k-C-圈的n阶r-一致超图的若干结果

主要讨论了不含k-C-圈的n阶r-一致超图,对不同的k,分别得出了它的极大边数的一个下界,并且得出在有些情况下它的下界是最大的.另外,我们得到了Krn含k-C-圈的一个充分必要条件.     

超图的Laplacian

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

On the Deductive Strength of Various Distributivity Axioms for Boolean Algebras in Set Theory

In this article, we shall show the generalized notions of distributivity of Boolean algebras have essential relations with several axioms and properties of set theory, say the Axiom of Choice, the Axiom of Dependence Choice, the Prime Ideal Theorems, Martin's axioms, Lebesgue measurability and so on.     

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 a Hypergraph Matching Problem

Let H = (V, E) be an r-uniform hypergraph and let A matching M of H is (α, )-perfect if for each F ∈ , at least α|F| vertices of F are covered by M. Our main result is a theorem giving sufficient conditions for an r-uniform hypergraph to have a -perfect matching. As a special case of our theorem we obtain the following result. Let K(n, r) denote the complete r-uniform hypergraph with n vertices. Let t and r be fixed positive integers where t≥r≥2. Then, K(n, r) can be packed with edge-disjoint copies of K(t, r) such that each vertex is incident with only o(n ^{r ?1}) unpacked edges. This extends a result of Rödl [9].