共查询到20条相似文献,搜索用时 328 毫秒
1.
2.
Shonda Gosselin 《组合设计杂志》2011,19(6):439-454
In this article, we examine the possible orders of t‐subset‐regular self‐complementary k‐uniform hypergraphs, which form examples of large sets of two isomorphic t‐designs. We reformulate Khosrovshahi and Tayfeh–Rezaie's necessary conditions on the order of these structures in terms of the binary representation of the rank k, and these conditions simplify to a more transparent relation between the order n and rank k in the case where k is a sum of consecutive powers of 2. Moreover, we present new constructions for 1‐subset‐regular self‐complementary uniform hypergraphs, and prove that these necessary conditions are sufficient for all k, in the case where t = 1. © 2011 Wiley Periodicals, Inc. J Combin Designs 19: 439‐454, 2011 相似文献
3.
4.
We show that every simple, (weakly) connected, possibly directed and infinite, hypergraph has a unique prime factor decomposition with respect to the (weak) Cartesian product, even if it has infinitely many factors. This generalizes previous results for graphs and undirected hypergraphs to directed and infinite hypergraphs. The proof adopts the strategy outlined by Imrich and ?erovnik for the case of graphs and introduces the notion of diagonal‐free grids as a replacement of the chord‐free 4‐cycles that play a crucial role in the case of graphs. This leads to a generalization of relation Δ on the arc set, whose convex hull is shown to coincide with the product relation of the prime factorization. © 2011 Wiley Periodicals, Inc. J Graph Theory 相似文献
5.
本文得到了无标号真严格(d)-连通无圈超图的计数公式,并得到了无标号真严格(d)-连通同胚k不可约无圈超图的计数公式. 相似文献
6.
《Discrete Mathematics》2022,345(6):112835
In this work we describe the spectra of all rational numbers that could be a density of a strictly balanced uniform hypergraph. We also introduce some specific constructions of strictly balanced uniform hypergraphs, and exploit them to generalize some results about Zero-One Law and Zero-One k-Law to the case of random uniform hypergraphs. 相似文献
7.
《Random Structures and Algorithms》2018,52(2):301-353
Szemerédi 's Regularity Lemma is a powerful tool in graph theory. It asserts that all large graphs admit bounded partitions of their edge sets, most classes of which consist of uniformly distributed edges. The original proof of this result was nonconstructive, and a constructive proof was later given by Alon, Duke, Lefmann, Rödl, and Yuster. Szemerédi's Regularity Lemma was extended to hypergraphs by various authors. Frankl and Rödl gave one such extension in the case of 3‐uniform hypergraphs, which was later extended to k‐uniform hypergraphs by Rödl and Skokan. W.T. Gowers gave another such extension, using a different concept of regularity than that of Frankl, Rödl, and Skokan. Here, we give a constructive proof of a regularity lemma for hypergraphs. 相似文献
8.
Counting acyclic hypergraphs 总被引:4,自引:0,他引:4
Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct
acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the
explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs. 相似文献
9.
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 相似文献
10.
《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. 相似文献
11.
We introduce an equivalence class of varied properties for hypergraphs. Any hypergraph possessing any one of these properties must of necessity possess them all. Since almost all random hypergraphs share these properties, we term these properties quasi-random. With these results, it becomes quite easy to show that many natural explicit constructions result in hypergraphs which imitate random hypergraphs in a variety of ways. 相似文献
12.
13.
Jian-fang Wang 《应用数学学报(英文版)》2011,27(1):59-62
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. 相似文献
14.
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 相似文献
15.
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. 相似文献
16.
Enumeration of Maximum Acyclic Hypergraphs 总被引:1,自引:0,他引:1
Jian-fang Wang Hai-zhu LiInstitute of Applied Mathematics Academy of Mathematics System Sciences Chinese Academy of Sciences Beijing China 《应用数学学报(英文版)》2002,18(2):215-218
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). 相似文献
17.
研究了一般的标号严格(d)-连通无圈超图的计数,得到了n阶标号严格(d)-连通无圈超图的计数公式. 相似文献
18.
鄢仁政 《纯粹数学与应用数学》2014,(1):40-44
划分问题因其在多个领域的重要应用一直是图论的研究热点.利用张量的特征值研究超图的划分与奇划分,并结合边割的界给出最大奇割、平均最小割、等周数等超图拓扑指标的界.当k取2时,这些结果与对应的图谱理论中的经典结论一致,因此可视为这些结论在超图的推广. 相似文献
19.
Somayeh Moradi 《代数通讯》2020,48(6):2699-2712
AbstractThe present work is concerned with characterizing some algebraic invariants of edge ideals of hypergraphs. To this aim, first, we introduce some kinds of combinatorial invariants similar to matching numbers for hypergraphs. Then we compare them to each other and to previously existing ones. These invariants are used for characterizing or bounding some algebraic invariants of edge ideals of hypergraphs such as graded Betti numbers, projective dimension and Castelnouvo–Mumford regularity.Communicated by Jason P. Bell 相似文献
20.
Chunfeng Cui Ziyan Luo Liqun Qi Hong Yan 《Numerical Linear Algebra with Applications》2023,30(2):e2468
The analytic connectivity (AC), defined via solving a series of constrained polynomial optimization problems, serves as a measure of connectivity in hypergraphs. How to compute such a quantity efficiently is important in practice and of theoretical challenge as well due to the non-convex and combinatorial features in its definition. In this article, we first perform a careful analysis of several widely used structured hypergraphs in terms of their properties and heuristic upper bounds of ACs. We then present an affine-scaling method to compute some upper bounds of ACs for uniform hypergraphs. To testify the tightness of the obtained upper bounds, two possible approaches via the Pólya theorem and semidefinite programming respectively are also proposed to verify the lower bounds generated by the obtained upper bounds minus a small gap. Numerical experiments on synthetic datasets are reported to demonstrate the efficiency of our proposed method. Further, we apply our method in hypergraphs constructed from social networks and text analysis to detect the network connectivity and rank the keywords, respectively. 相似文献