共查询到20条相似文献,搜索用时 31 毫秒
1.
Minimal cellular resolutions of the edge ideals of cointerval hypergraphs are constructed. This class of d-uniform hypergraphs coincides with the complements of interval graphs (for the case d?=?2), and strictly contains the class of ‘strongly stable’ hypergraphs corresponding to pure shifted simplicial complexes. The polyhedral complexes supporting the resolutions are described as certain spaces of directed graph homomorphisms, and are realized as subcomplexes of mixed subdivisions of the Minkowski sums of simplices. Resolutions of more general hypergraphs are obtained by considering decompositions into cointerval hypergraphs. 相似文献
2.
Chvátal, Rödl, Szemerédi and Trotter [V. Chvátal, V. Rödl, E. Szemerédi and W.T. Trotter, The Ramsey number of a graph with a bounded maximum degree, J. Combinatorial Theory B 34 (1983), 239–243] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, 3-uniform hypergraphs of bounded degree have linear Ramsey numbers, submitted] and [B. Nagle, S. Olsen, V. Rödl and M. Schacht, On the Ramsey number of sparse 3-graphs, preprint] the same result was proved for 3-uniform hypergraphs. In [O. Cooley, N. Fountoulakis, D. Kühn and D. Osthus, Embeddings and Ramsey numbers of sparse k-uniform hypergraphs, submitted] we extended this result to k-uniform hypergraphs for any integer . As in the 3-uniform case, the main new tool which we proved and used is an embedding lemma for k-uniform hypergraphs of bounded maximum degree into suitable k-uniform ‘quasi-random’ hypergraphs. 相似文献
3.
《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. 相似文献
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. 相似文献
5.
Fan R.K. Chung 《Random Structures and Algorithms》1991,2(2):241-252
We give a simple proof for Szemerédi's Regularity Lemma and its generalization for k-uniform hypergraphs. For fixed k, there are altogether k -1 different versions of the regularity lemma for k-uniform hypergraphs. The connection between regularity lemmas for hypergraphs and quasi-random classes of hypergraphs is also investigated. 相似文献
6.
Paths and cycles of hypergraphs 总被引:1,自引:0,他引:1
Hypergraphs are the most general structures in discrete mathematics. Acyclic hypergraphs have been proved very useful in relational
databases. New systems of axioms for paths, connectivity and cycles of hypergraphs are constructed. The systems suit the structure
properties of relational databases. The concepts of pseudo cycles and essential cycles of hypergraphs are introduced. They
are relative to each other. Whether a family of cycles of a hypergraph is dependent or independent is defined. An enumeration
formula for the maximum number of independent essential cycles of a hypergraph is given. 相似文献
7.
Jü rgen Herzog Takayuki Hibi Ngô Viê t Trung Xinxian Zheng 《Transactions of the American Mathematical Society》2008,360(12):6231-6249
The aim of this paper is to characterize simplicial complexes which have standard graded vertex cover algebras. This property has several nice consequences for the squarefree monomial ideals defining these algebras. It turns out that such simplicial complexes are closely related to a range of hypergraphs which generalize bipartite graphs and trees. These relationships allow us to obtain very general results on standard graded vertex cover algebras which cover previous major results on Rees algebras of squarefree monomial ideals.
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.
Extremal problems on the number of j-independent sets in uniform simple hypergraphs are studied. Nearly optimal results on the maximum number of independent sets for the class of simple regular hypergraphs and on the minimum number of independent sets for the class of simple hypergraphs with given average degree of vertices are obtained. 相似文献
10.
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. 相似文献
11.
Chvátal, Rödl, Szemerédi and Trotter [3] proved that the Ramsey numbers of graphs of bounded maximum degree are linear in their order. In [6,23] the same result was proved for 3-uniform hypergraphs. Here we extend this result to κ-uniform hypergraphs for any integer κ ≥ 3. As in the 3-uniform case, the main new tool which we prove and use is an embedding lemma for κ-uniform hypergraphs of bounded maximum degree into suitable κ-uniform ‘quasi-random’ hypergraphs. 相似文献
12.
13.
In this paper two-terminal series-parallel chromatic hypergraphs are introduced and for this class of hypergraphs it is shown that the chromatic polynomial can be computed with polynomial complexity. It is also proved that h-uniform multibridge hypergraphs θ(h;a1,a2,…,ak) are chromatically unique for h≥3 if and only if h=3 and a1=a2=?=ak=1, i.e., when they are sunflower hypergraphs having a core of cardinality 2 and all petals being singletons. 相似文献
14.
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 相似文献
15.
16.
Fan R. K. Chung 《Random Structures and Algorithms》1990,1(4):363-382
We investigate the relations among a number of different graph properties for k-uniformhypergraphs, which are shared by random hypergraphs. Various graph properties form equivalence classes which in turn constitute a natural hierarchy. The analogues for binary functions on k-tuples and for hypergraphs with small density are also considered. Several classes are related to communication complexity and expander graphs. 相似文献
17.
Mitre C. Dourado Fábio Protti Jayme L. Szwarcfiter 《Discrete Applied Mathematics》2008,156(7):1053-1057
The notion of strong p-Helly hypergraphs was introduced by Golumbic and Jamison in 1985 [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, J. Combin. Theory Ser. B 38 (1985) 8-22]. Independently, other authors [A. Bretto, S. Ubéda, J. ?erovnik, A polynomial algorithm for the strong Helly property. Inform. Process. Lett. 81 (2002) 55-57, E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220, W.D. Wallis, Guo-Hui Zhang, On maximal clique irreducible graphs. J. Combin. Math. Combin. Comput. 8 (1990) 187-193.] have also considered the strong Helly property in other contexts. In this paper, we characterize strong p-Helly hypergraphs. This characterization leads to an algorithm for recognizing such hypergraphs, which terminates within polynomial time whenever p is fixed. In contrast, we show that the recognition problem is co-NP-complete, for arbitrary p. Further, we apply the concept of strong p-Helly hypergraphs to the cliques of a graph, leading to the class of strong p-clique-Helly graphs. For p=2, this class is equivalent to that of hereditary clique-Helly graphs [E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220]. We describe a characterization for this class and obtain an algorithm for recognizing such graphs. Again, the algorithm has polynomial-time complexity for p fixed, and we show the corresponding recognition problem to be NP-hard, for arbitrary p. 相似文献
18.
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). 相似文献
19.
We present alternative proofs of density versions of some combinatorial partition theorems originally obtained by E. Szemerédi, H. Furstenberg and Y. Katznelson. These proofs are based on an extremal hypergraph result which was recently obtained independently by W. T. Gowers and B. Nagle, V. Rödl, M. Schacht, J. Skokan by extending Szemerédi’s regularity lemma to hypergraphs. 相似文献