共查询到20条相似文献，搜索用时 190 毫秒
1.
Chung and Graham began the systematic study of k‐uniform hypergraph quasirandom properties soon after the foundational results of Thomason and Chung‐Graham‐Wilson on quasirandom graphs. One feature that became apparent in the early work on k‐uniform hypergraph quasirandomness is that properties that are equivalent for graphs are not equivalent for hypergraphs, and thus hypergraphs enjoy a variety of inequivalent quasirandom properties. In the past two decades, there has been an intensive study of these disparate notions of quasirandomness for hypergraphs, and an open problem that has emerged is to determine the relationship between them. Our main result is to determine the poset of implications between these quasirandom properties. This answers a recent question of Chung and continues a project begun by Chung and Graham in their first paper on hypergraph quasirandomness in the early 1990's. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46,762–800, 2015 相似文献
2.
Yufei Zhao 《Random Structures and Algorithms》2015,47(2):205-226
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 相似文献
3.
4.
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
- one of G and H contains a spanning graph‐star, and each vertex of the other is contained in a graph edge, or
- 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.
5.
The survey is devoted to line graphs and a new multivalued function
called the line hypergraph. This function generalizes two classical concepts at once, namely the line graph and the dual hypergraph. In a certain sense, line graphs and dual hypergraphs are extreme values of the function
. There are many publications about line graphs, but our considerations are restricted to papers concerning Krausz global characterization of line graphs or Whitneys theorem on edge isomorphisms. The survey covers almost all known results on the function
because they are concentrated around Krausz and Whitneys theorems. These results provide evidence that the notion of the line hypergraph is quite natural. It enables one to unify the classical theorems on line graphs and to obtain their more general versions in a simpler way. 相似文献
6.
通过使用超滤子的概念以及所讨论的模糊理想的相应性质,提出了超积BCK-代数和BCK-代数模糊子集的模糊超积. 相似文献
7.
The well‐known Friendship Theorem states that if G is a graph in which every pair of vertices has exactly one common neighbor, then G has a single vertex joined to all others (a “universal friend”). V. Sós defined an analogous friendship property for 3‐uniform hypergraphs, and gave a construction satisfying the friendship property that has a universal friend. We present new 3‐uniform hypergraphs on 8, 16, and 32 vertices that satisfy the friendship property without containing a universal friend. We also prove that if n ≤ 10 and n ≠ 8, then there are no friendship hypergraphs on n vertices without a universal friend. These results were obtained by computer search using integer programming. © 2008 Wiley Periodicals, Inc. J Combin Designs 16: 253–261, 2008 相似文献
8.
9.
《Discrete Mathematics》2022,345(6):112832
An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques that generalize the circuit classification of the signed graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camion's algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance. 相似文献
10.
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 2k 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. 相似文献
11.
《Journal of Graph Theory》2018,87(3):356-361
We investigate the minimum order of a linear r‐regular k‐uniform hypergraph, also known as an ‐combinatorial configuration, which contains a given linear k‐uniform hypergraph of maximum (vertex) degree at most r. 相似文献
12.
《Random Structures and Algorithms》2018,53(2):185-220
In 1990 Bender, Canfield, and McKay gave an asymptotic formula for the number of connected graphs on with m edges, whenever and . We give an asymptotic formula for the number of connected r‐uniform hypergraphs on with m edges, whenever is fixed and with , that is, the average degree tends to infinity. This complements recent results of Behrisch, Coja‐Oghlan, and Kang (the case ) and the present authors (the case , ie, “nullity” or “excess” o(n)). The proof is based on probabilistic methods, and in particular on a bivariate local limit theorem for the number of vertices and edges in the largest component of a certain random hypergraph. The arguments are much simpler than in the sparse case; in particular, we can use “smoothing” techniques to directly prove the local limit theorem, without needing to first prove a central limit theorem. 相似文献
13.
超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果. 相似文献
14.
15.
A 1992 conjecture of Alon and Spencer says, roughly, that the ordinary random graph Gn,1/2 typically admits a covering of a constant fraction of its edges by edge‐disjoint, nearly maximum cliques. We show that this is not the case. The disproof is based on some (partial) understanding of a more basic question: for and A1,…,At chosen uniformly and independently from the k‐subsets of {1,…,n}, what can one say about Our main concern is trying to understand how closely the answers to this and a related question about matchings follow heuristics gotten by pretending that certain (dependent) choices are made independently. 相似文献
16.
Let Η be a hypergraph with n vertices. Suppose that di,￠/2,...,dn are degrees of the vert ices of Η. The t-th graph entropy based on degrees of H is defined as Id^t(Η)=-n∑i=1(di^t/∑j=1^ndj^t^nlogdi^t/∑j=1^ndj^t^n)=log(n∑i=1di^t)-n∑i=1(di^t/∑j=1^ndj^tlogdi^t), where t is a real number and the logarithm is taken to the base two. In this paper we obtain upper and lower bounds of Id^t(Η) for t = 1, when Η is among all uniform super trees, unicyclic uniform hypergraphs and bicyclic uniform hypergraphs, respectively. 相似文献
17.
Yasuki Sekiguchi 《Operations Research Letters》1983,2(5):243-247
A facial structure of the node packing polytope, i.e., of the convex hull of integer solutions of the node packing problem, on hypergraphs is studied. First, the results extracted by Chvàtal and by Balas and Zemel on canonical facets of the node packing polytopes on graphs are generalized to derive some specific hypergraphs having canonical facets. Second, it is shown that the facial structure of the node packing polytope on a hypergraph, named a fat graph, has a very close relationship to the facial structures of the node packing polytope and also of the convex hull of integer solutions of an integer linear program, which are defined on a specific graph corresponding to the fat graph. 相似文献
18.
LIANG Jun-qi 《数学季刊》2004,19(3):300-305
This paper is devoted to the study of the logical properties of BCK algebras. For formalized BCK algebra theory T, it is proved that T is preserved under submodels and unions of chains; T is neither complete nor model complete, and hence there exist no built-in Skolem function. Moreover, the ultraproduct BCK algebras and the fuzzy ultraproduct of fuzzy subsets of BCK algebras were proposed by using the concept of ultrafilters with corresponding properties of fuzzy ideals discussed. 相似文献
19.
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. 相似文献
20.
主要讨论了4一致l-超图的最小边数与最小上色数的关系,给出了上色数为3的4一致l-超图的最小边数的一个上界. 相似文献