An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is ...An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is denoted by . Erdös, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap-restricted hypergraphs. Our result extends a result of Alesandroni in 2021.展开更多
The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows:Dv(H)≤min{α≤(H), p(H), p(H), T(H)}; De(H)≤min{v(H), T...The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows:Dv(H)≤min{α≤(H), p(H), p(H), T(H)}; De(H)≤min{v(H), T(H), p(H)}; DT(H) ≤αT(H); S(H)≤ Dv (H) + α(H)≤n; 2≤ Dv (H) + T(H) ≤n; 2 〈 Dv (H) + v(H)≤n/2 + [n/r]; Dv (H) + p(H) 〈_n;2≤De(H) + Dv(H)≤n/2 + [n/r];α(H) + De(H)≤n;2 ≤ De(H) + v(H)≤2[n/r]; 2 De(H) + p(H)≤n-r + 2.展开更多
The celebrated Erdos-Ko-Rado theorem states that given n≥2k,every intersecting k-uni-n-1 form hypergraph G on n vertices has at most(n-1 k-1)edges.This paper states spectral versions of the Erd6s-_Ko--Rado theorem:le...The celebrated Erdos-Ko-Rado theorem states that given n≥2k,every intersecting k-uni-n-1 form hypergraph G on n vertices has at most(n-1 k-1)edges.This paper states spectral versions of the Erd6s-_Ko--Rado theorem:let G be an intersecting k-uniform hypergraph on n vertices with n≥2k.Then,the sharp upper bounds for the spectral radius of Aα(G)and 2*(G)are presented,where Aα(G)=αD(G)+(1-α).A(G)is a convex linear combination of the degree diagonal tensor D(G)and the adjacency tensor A(G)for 0≤α<1,and Q^(*)(G)is the incidence Q-tensor,respectively.Furthermore,when n>2k,the extremal hypergraphs which attain the sharp upper bounds are characterized.The proof mainly relies on the Perron-Frobenius theorem for nonnegative tensor and the property of the maximizing connected hypergraphs.展开更多
Let p,q be two positive integers.The 3-graph F(p,q)is obtained from the complete 3-graph K_(p)^(3)by adding q new vertices and P_(q/2)new edges of the form vxy for which v∈V(K_p~3)and{x,y}are new vertices.It frequent...Let p,q be two positive integers.The 3-graph F(p,q)is obtained from the complete 3-graph K_(p)^(3)by adding q new vertices and P_(q/2)new edges of the form vxy for which v∈V(K_p~3)and{x,y}are new vertices.It frequently appears in many literatures on the Turán number or Turán density of hypergraphs.In this paper,we first construct a new class of r-graphs which can be regarded as a generalization of the 3-graph F(p,q),and prove that these r-graphs have the same Turán density under some situations.Moreover,we investigate the Turán density of the F(p,q)for small p,q and obtain some new bounds on their Turán densities.展开更多
A hypergraph H is an(n,m)-hypergraph if it contains n vertices and m hyperedges,where n≥1 and m≥0 are two integers.Let k be a positive integer and let L be a set of nonnegative integers.A hyper graph H is k-uniform ...A hypergraph H is an(n,m)-hypergraph if it contains n vertices and m hyperedges,where n≥1 and m≥0 are two integers.Let k be a positive integer and let L be a set of nonnegative integers.A hyper graph H is k-uniform if all its hyperedges have the same size k,and H is L-intersecting if the number of common vertices of every two hyperedges belongs to L.In this paper,we propose and investigate the problem of estimating the maximum k among all k-uniform L-intersecting(n,m)-hypergraphs for fixed n,m and L.We will provide some tight upper and lower bounds on k in terms of n,m and L.展开更多
Let H=(V,E)be a hypergraph,where V is a set of vertices and E is a set of non-empty subsets of V called edges.If all edges of H have the same cardinality r,then H is an r-uniform hypergraph;if E consists of all r-subs...Let H=(V,E)be a hypergraph,where V is a set of vertices and E is a set of non-empty subsets of V called edges.If all edges of H have the same cardinality r,then H is an r-uniform hypergraph;if E consists of all r-subsets of V,then H is a complete r-uniform hypergraph,denoted by K_(n)^(r),where n=|V|.A hypergraph H′=(V′,E′)is called a subhypergraph of H=(V,E)if V′⊆V and E′⊆E.The edge-connectivity of a hypergraph H is the cardinality of a minimum edge set F⊆E such that H−F is not connected,where H−F=(V,E\F).An r-uniform hypergraph H=(V,E)is k-edge-maximal if every subhypergraph of H has edge-connectivity at most k,but for any edge e∈E(K_(n)^(r))\E(H),H+e contains at least one subhypergraph with edge-connectivity at least k+1.Let k and r be integers with k≥2 and r≥2,and let t=t(k,r)be the largest integer such that(t−1 r−1)≤k.That is,t is the integer satisfying(t−1 r−1)≤k<(t r−1).We prove that if H is an r-uniform k-edge-maximal hypergraph such that n=|V(H)|≥t,then(i)|E(H)|≤(t r)+(n−t)k,and this bound is best possible;(ii)|E(H)|≥(n−1)k−((t−1)k−(t r))[n/t],and this bound is best possible.展开更多
The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs. Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques. ...The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs. Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques. This connection provided a new proof of Turin classical result on the Turan density of complete graphs. Since then, Graph-Lagrangian has become a useful tool in extremal problems for hypergraphs. Peng and Zhao attempted to explore the relationship between the Graph-Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. They showed that if G is a 3-uniform graph with m edges containing a clique of order t - 1, then A(G) = A([t- 1](3)) provided (t31) ≤ m ≤ (3^t1) + (2^rt-2). They also conjectured: If G is an r-uniform graph with m edges not containing a clique of order t - 1, then A(G) 〈 A([t - 1](r)) provided (r^t-1) ≤ m ≤ (r^t-1) + (r-1^t-2). It has been shown that to verify this conjecture for 3-uniform graphs, it is sufficient to verify the conjecture for left-compressed 3-uniform graphs with m = (3^t-1) + (2^t-2). Regarding this conjecture, we show: If G is a left-compressed 3-uniform graph on the vertex set It] with m edges and lit - 1](3) / E(G)|=- p, then A(G) 〈 A([t - 1](3)) provided m = (3^t-1) + (2^t-2) and t ≥ 17p/2 + 11.展开更多
Acyclic hypergraphs are analogues of forests in graphs. They arevery useful in the design of databases. The number of distinct acyclic uniform hypergraphs with n labeled vertices is studied. With the aid of the princi...Acyclic hypergraphs are analogues of forests in graphs. They arevery useful in the design of databases. The number of distinct acyclic uniform hypergraphs with n labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicit formula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.展开更多
In recent years,there has been a growing interest in graph convolutional networks(GCN).However,existing GCN and variants are predominantly based on simple graph or hypergraph structures,which restricts their ability t...In recent years,there has been a growing interest in graph convolutional networks(GCN).However,existing GCN and variants are predominantly based on simple graph or hypergraph structures,which restricts their ability to handle complex data correlations in practical applications.These limitations stem from the difficulty in establishing multiple hierarchies and acquiring adaptive weights for each of them.To address this issue,this paper introduces the latest concept of complex hypergraphs and constructs a versatile high-order multi-level data correlation model.This model is realized by establishing a three-tier structure of complexes-hypergraphs-vertices.Specifically,we start by establishing hyperedge clusters on a foundational network,utilizing a second-order hypergraph structure to depict potential correlations.For this second-order structure,truncation methods are used to assess and generate a three-layer composite structure.During the construction of the composite structure,an adaptive learning strategy is implemented to merge correlations across different levels.We evaluate this model on several popular datasets and compare it with recent state-of-the-art methods.The comprehensive assessment results demonstrate that the proposed model surpasses the existing methods,particularly in modeling implicit data correlations(the classification accuracy of nodes on five public datasets Cora,Citeseer,Pubmed,Github Web ML,and Facebook are 86.1±0.33,79.2±0.35,83.1±0.46,83.8±0.23,and 80.1±0.37,respectively).This indicates that our approach possesses advantages in handling datasets with implicit multi-level structures.展开更多
In this paper we consider the random r-uniform r-partite hypergraph model H(n1, n2,…, nr; n, p) which consists of all the r-uniform r-partite hypergraphs with vertex partition {V1,V2,…, Vr} where |Vi| = ni = ni...In this paper we consider the random r-uniform r-partite hypergraph model H(n1, n2,…, nr; n, p) which consists of all the r-uniform r-partite hypergraphs with vertex partition {V1,V2,…, Vr} where |Vi| = ni = ni(n) (1 ≤ i ≤ r) are positive integer-valued functions on n with n1 +n2 +… +nr =n, and each r-subset containing exactly one element in Vi (1 ≤ i ≤ r) is chosen to be a hyperedge of Hp ∈H(n1,n2,…,nr;n,p) with probability p = p(n), all choices being independent. Let △V1 = △V1 (H) and δv1 = δv1(H) be the maximum and minimum degree of vertices in V1 of H, respectively; Xd,V1 = Xd,V1 (H), Yd,V1 = Yd,V1 (H), Zd,V1 = Zd,V1 (H) and Zc,d,V1=Zc,d,V1 (H) be the number of vertices in V1 of H with degree d, at least d, at most d, and between c and d, respectively. In this paper we obtain that in the space H(n1, n2,…, nr; n,p), Xd,V1, Yd,V1, Zd,V1, and Zc,d,V1all have asymptotically Poisson distributions. We also answer the following two questions. What is the range of p that there exists a function D(n) such that in the space H(n1, n2,…,nr; n, p), lim n→+∞ P(△v1 = D(n)) = 1? What is the range of p such that a.e., Hp ∈ H(n1,n2,...,nr;n,p) has a unique vertex in V1 with degree Av1(Hp)? Both answers are p = o(logn1/N), where N = r ∏ i=2 ni. The corresponding problems on δv1(Hp) also are considered, and we obtained the answers are p ≤ (1+o(1))(logn1/N) andp=o (log n1/N), respectively.展开更多
In this paper,we investigate a generalization of graph decomposition,called hypergraph decomposition.We show that a decomposition of a 3-uniform hypergraph K<sub>v</sub><sup>3</sup>into a speci...In this paper,we investigate a generalization of graph decomposition,called hypergraph decomposition.We show that a decomposition of a 3-uniform hypergraph K<sub>v</sub><sup>3</sup>into a special kind of hypergraph K<sub>4</sub><sup>3</sup>-e exists if and only if v≡0,1,2(mod 9)and v≥9.展开更多
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 ar...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.展开更多
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...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.展开更多
In this paper,we study the adjacency and signless Laplacian tensors of cored hypergraphs and power hypergraphs.We investigate the properties of their adjacency and signless Laplacian H-eigenvalues.Especially,we find o...In this paper,we study the adjacency and signless Laplacian tensors of cored hypergraphs and power hypergraphs.We investigate the properties of their adjacency and signless Laplacian H-eigenvalues.Especially,we find out the largest H-eigenvalues of adjacency and signless Laplacian tensors for uniform squids.We also compute the H-spectra of sunflowers and some numerical results are reported for the H-spectra.展开更多
Cyclic hypergraphs are the analogue of cyclic graphs. The unicycle hypergraph whose cyclomatic number equals to one is the most elemental cyclic hypergraph. In this paper the maximum size of unicycle hypergraphs is s...Cyclic hypergraphs are the analogue of cyclic graphs. The unicycle hypergraph whose cyclomatic number equals to one is the most elemental cyclic hypergraph. In this paper the maximum size of unicycle hypergraphs is studied. It is proved a piecewise linear function of the order and edge size of the hypergraph.展开更多
A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Bul′o and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by ...A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Bul′o and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by studying the relation of local(global) minimizers of a homogeneous polynomial function of degree r and the maximal(maximum) cliques of an r-uniform hypergraph. In this paper, we study polynomial optimization problems for non-uniform hypergraphs with four different types of edges and apply it to get an upper bound of Tur′an densities of complete non-uniform hypergraphs.展开更多
The explicit formula for (k+l)-uniform linear acyclic hypergraphs and the counting series for unlabeled (k +1)-uniform linear acyclic hypergraphs are obtained.
Let G be a connected hypergraph with even uniformity,which contains cut vertices.Then G is the coalescence of two nontrivial connected sub-hypergraphs(called branches)at a cut vertex.Let A(G)be the adjacency tensor of...Let G be a connected hypergraph with even uniformity,which contains cut vertices.Then G is the coalescence of two nontrivial connected sub-hypergraphs(called branches)at a cut vertex.Let A(G)be the adjacency tensor of G.The least H-eigenvalue of A(G)refers to the least real eigenvalue of A(G)associated with a real eigenvector.In this paper,we obtain a perturbation result on the least H-eigenvalue of A(G)when a branch of G attached at one vertex is relocated to another vertex,and characterize the unique hypergraph whose least H-eigenvalue attains the minimum among all hypergraphs in a certain class of hypergraphs which contain a fixed connected hypergraph.展开更多
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...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.展开更多
文摘An edge coloring of hypergraph H is a function such that holds for any pair of intersecting edges . The minimum number of colors in edge colorings of H is called the chromatic index of H and is denoted by . Erdös, Faber and Lovász proposed a famous conjecture that holds for any loopless linear hypergraph H with n vertices. In this paper, we show that is true for gap-restricted hypergraphs. Our result extends a result of Alesandroni in 2021.
基金Supported by Ningbo Institute of Technology, Zhejiang Univ. Youth Innovation Foundation and Zhejiang Provincial Natural Science Foundation( Y604167).
文摘The relations among the dominating number, independence number and covering number of hypergraphs are investigated. Main results are as follows:Dv(H)≤min{α≤(H), p(H), p(H), T(H)}; De(H)≤min{v(H), T(H), p(H)}; DT(H) ≤αT(H); S(H)≤ Dv (H) + α(H)≤n; 2≤ Dv (H) + T(H) ≤n; 2 〈 Dv (H) + v(H)≤n/2 + [n/r]; Dv (H) + p(H) 〈_n;2≤De(H) + Dv(H)≤n/2 + [n/r];α(H) + De(H)≤n;2 ≤ De(H) + v(H)≤2[n/r]; 2 De(H) + p(H)≤n-r + 2.
基金the National Natural Science Foundation of China(Nos.11971311,11531001)the Montenegrin-Chinese Science and Technology Cooperation Project(No.3-12).
文摘The celebrated Erdos-Ko-Rado theorem states that given n≥2k,every intersecting k-uni-n-1 form hypergraph G on n vertices has at most(n-1 k-1)edges.This paper states spectral versions of the Erd6s-_Ko--Rado theorem:let G be an intersecting k-uniform hypergraph on n vertices with n≥2k.Then,the sharp upper bounds for the spectral radius of Aα(G)and 2*(G)are presented,where Aα(G)=αD(G)+(1-α).A(G)is a convex linear combination of the degree diagonal tensor D(G)and the adjacency tensor A(G)for 0≤α<1,and Q^(*)(G)is the incidence Q-tensor,respectively.Furthermore,when n>2k,the extremal hypergraphs which attain the sharp upper bounds are characterized.The proof mainly relies on the Perron-Frobenius theorem for nonnegative tensor and the property of the maximizing connected hypergraphs.
基金the National Natural Science Foundation of China(No.12171089)。
文摘Let p,q be two positive integers.The 3-graph F(p,q)is obtained from the complete 3-graph K_(p)^(3)by adding q new vertices and P_(q/2)new edges of the form vxy for which v∈V(K_p~3)and{x,y}are new vertices.It frequently appears in many literatures on the Turán number or Turán density of hypergraphs.In this paper,we first construct a new class of r-graphs which can be regarded as a generalization of the 3-graph F(p,q),and prove that these r-graphs have the same Turán density under some situations.Moreover,we investigate the Turán density of the F(p,q)for small p,q and obtain some new bounds on their Turán densities.
基金Supported by National Natural Science Foundation of China(Grant Nos.12242111,12131013,12171393,12071370,71973103,U1803263,11601430)Natural Science Foundation of Shaanxi Province(Grant Nos.2021JM-040,2020JQ-099)+2 种基金Shaanxi Fundamental Science Research Project for Mathematics and Physics(Grant No.22JSZ009)Guangdong Basic and Applied Basic Research Foundation(Grant Nos.2023A1515030208,2022A1515010899)the Fundamental Research Funds for the Central Universities。
文摘A hypergraph H is an(n,m)-hypergraph if it contains n vertices and m hyperedges,where n≥1 and m≥0 are two integers.Let k be a positive integer and let L be a set of nonnegative integers.A hyper graph H is k-uniform if all its hyperedges have the same size k,and H is L-intersecting if the number of common vertices of every two hyperedges belongs to L.In this paper,we propose and investigate the problem of estimating the maximum k among all k-uniform L-intersecting(n,m)-hypergraphs for fixed n,m and L.We will provide some tight upper and lower bounds on k in terms of n,m and L.
基金supported by the National Natural Science Foundation of China(Nos.11861066,11531011)Tianshan Youth Project of Xinjiang(2018Q066)。
文摘Let H=(V,E)be a hypergraph,where V is a set of vertices and E is a set of non-empty subsets of V called edges.If all edges of H have the same cardinality r,then H is an r-uniform hypergraph;if E consists of all r-subsets of V,then H is a complete r-uniform hypergraph,denoted by K_(n)^(r),where n=|V|.A hypergraph H′=(V′,E′)is called a subhypergraph of H=(V,E)if V′⊆V and E′⊆E.The edge-connectivity of a hypergraph H is the cardinality of a minimum edge set F⊆E such that H−F is not connected,where H−F=(V,E\F).An r-uniform hypergraph H=(V,E)is k-edge-maximal if every subhypergraph of H has edge-connectivity at most k,but for any edge e∈E(K_(n)^(r))\E(H),H+e contains at least one subhypergraph with edge-connectivity at least k+1.Let k and r be integers with k≥2 and r≥2,and let t=t(k,r)be the largest integer such that(t−1 r−1)≤k.That is,t is the integer satisfying(t−1 r−1)≤k<(t r−1).We prove that if H is an r-uniform k-edge-maximal hypergraph such that n=|V(H)|≥t,then(i)|E(H)|≤(t r)+(n−t)k,and this bound is best possible;(ii)|E(H)|≥(n−1)k−((t−1)k−(t r))[n/t],and this bound is best possible.
基金Supported in part by National Natural Science Foundation of China(Grant No.11271116)
文摘The paper explores the connection of Graph-Lagrangians and its maximum cliques for 3-uniform hypergraphs. Motzkin and Straus showed that the Graph-Lagrangian of a graph is the Graph-Lagrangian of its maximum cliques. This connection provided a new proof of Turin classical result on the Turan density of complete graphs. Since then, Graph-Lagrangian has become a useful tool in extremal problems for hypergraphs. Peng and Zhao attempted to explore the relationship between the Graph-Lagrangian of a hypergraph and the order of its maximum cliques for hypergraphs when the number of edges is in certain range. They showed that if G is a 3-uniform graph with m edges containing a clique of order t - 1, then A(G) = A([t- 1](3)) provided (t31) ≤ m ≤ (3^t1) + (2^rt-2). They also conjectured: If G is an r-uniform graph with m edges not containing a clique of order t - 1, then A(G) 〈 A([t - 1](r)) provided (r^t-1) ≤ m ≤ (r^t-1) + (r-1^t-2). It has been shown that to verify this conjecture for 3-uniform graphs, it is sufficient to verify the conjecture for left-compressed 3-uniform graphs with m = (3^t-1) + (2^t-2). Regarding this conjecture, we show: If G is a left-compressed 3-uniform graph on the vertex set It] with m edges and lit - 1](3) / E(G)|=- p, then A(G) 〈 A([t - 1](3)) provided m = (3^t-1) + (2^t-2) and t ≥ 17p/2 + 11.
基金This work was supported by the National Natural Science Foundation of China (Grant No. 19831080) .
文摘Acyclic hypergraphs are analogues of forests in graphs. They arevery useful in the design of databases. The number of distinct acyclic uniform hypergraphs with n labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicit formula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.12275179 and 11875042)the Natural Science Foundation of Shanghai Municipality,China(Grant No.21ZR1443900)。
文摘In recent years,there has been a growing interest in graph convolutional networks(GCN).However,existing GCN and variants are predominantly based on simple graph or hypergraph structures,which restricts their ability to handle complex data correlations in practical applications.These limitations stem from the difficulty in establishing multiple hierarchies and acquiring adaptive weights for each of them.To address this issue,this paper introduces the latest concept of complex hypergraphs and constructs a versatile high-order multi-level data correlation model.This model is realized by establishing a three-tier structure of complexes-hypergraphs-vertices.Specifically,we start by establishing hyperedge clusters on a foundational network,utilizing a second-order hypergraph structure to depict potential correlations.For this second-order structure,truncation methods are used to assess and generate a three-layer composite structure.During the construction of the composite structure,an adaptive learning strategy is implemented to merge correlations across different levels.We evaluate this model on several popular datasets and compare it with recent state-of-the-art methods.The comprehensive assessment results demonstrate that the proposed model surpasses the existing methods,particularly in modeling implicit data correlations(the classification accuracy of nodes on five public datasets Cora,Citeseer,Pubmed,Github Web ML,and Facebook are 86.1±0.33,79.2±0.35,83.1±0.46,83.8±0.23,and 80.1±0.37,respectively).This indicates that our approach possesses advantages in handling datasets with implicit multi-level structures.
基金Supported in part by the National Natural Science Foundation of China under Grant No.11401102,11271307 and 11101086Fuzhou university of Science and Technology Development Fund No.2014-XQ-29
文摘In this paper we consider the random r-uniform r-partite hypergraph model H(n1, n2,…, nr; n, p) which consists of all the r-uniform r-partite hypergraphs with vertex partition {V1,V2,…, Vr} where |Vi| = ni = ni(n) (1 ≤ i ≤ r) are positive integer-valued functions on n with n1 +n2 +… +nr =n, and each r-subset containing exactly one element in Vi (1 ≤ i ≤ r) is chosen to be a hyperedge of Hp ∈H(n1,n2,…,nr;n,p) with probability p = p(n), all choices being independent. Let △V1 = △V1 (H) and δv1 = δv1(H) be the maximum and minimum degree of vertices in V1 of H, respectively; Xd,V1 = Xd,V1 (H), Yd,V1 = Yd,V1 (H), Zd,V1 = Zd,V1 (H) and Zc,d,V1=Zc,d,V1 (H) be the number of vertices in V1 of H with degree d, at least d, at most d, and between c and d, respectively. In this paper we obtain that in the space H(n1, n2,…, nr; n,p), Xd,V1, Yd,V1, Zd,V1, and Zc,d,V1all have asymptotically Poisson distributions. We also answer the following two questions. What is the range of p that there exists a function D(n) such that in the space H(n1, n2,…,nr; n, p), lim n→+∞ P(△v1 = D(n)) = 1? What is the range of p such that a.e., Hp ∈ H(n1,n2,...,nr;n,p) has a unique vertex in V1 with degree Av1(Hp)? Both answers are p = o(logn1/N), where N = r ∏ i=2 ni. The corresponding problems on δv1(Hp) also are considered, and we obtained the answers are p ≤ (1+o(1))(logn1/N) andp=o (log n1/N), respectively.
基金This work was supported by the National Natural Science Foundation of China(Grant No.10371002)
文摘In this paper,we investigate a generalization of graph decomposition,called hypergraph decomposition.We show that a decomposition of a 3-uniform hypergraph K<sub>v</sub><sup>3</sup>into a special kind of hypergraph K<sub>4</sub><sup>3</sup>-e exists if and only if v≡0,1,2(mod 9)and v≥9.
文摘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.
基金The authors would like to thank the referees for several remarks and suggestions. This work was supported in part by the Joint NSFC-ISF Research Program (jointly funded by the National Natural Science Foundation of China and the Israel Science Foundation (Grant No. 11561141001)), the National Natural Science Foundation of China (Grant Nos. 11531001 and 11271256), Innovation Program of Shanghai Municipal Education Commission (Grant No. 14ZZ016) and SpeciMized Research Fund for the Doctoral Program of Higher Education (Grant No. 20130073110075).
文摘We present several upper bounds for the adjacency and signless Laplacian spectral radii of uniform hypergraphs in terms of degree sequences.
基金Supported by NSFC(Grant Nos.11531011,11671320,11601431,11871034 and U1803263)the China Postdoctoral Science Foundation(Grant No.2016M600813)the Natural Science Foundation of Shaanxi Province(Grant No.2017JQ1019)
文摘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.
基金the National Natural Science Foundation of China(No.11271221)the Specialized Research Fund for State Key Laboratories.
文摘In this paper,we study the adjacency and signless Laplacian tensors of cored hypergraphs and power hypergraphs.We investigate the properties of their adjacency and signless Laplacian H-eigenvalues.Especially,we find out the largest H-eigenvalues of adjacency and signless Laplacian tensors for uniform squids.We also compute the H-spectra of sunflowers and some numerical results are reported for the H-spectra.
文摘Cyclic hypergraphs are the analogue of cyclic graphs. The unicycle hypergraph whose cyclomatic number equals to one is the most elemental cyclic hypergraph. In this paper the maximum size of unicycle hypergraphs is studied. It is proved a piecewise linear function of the order and edge size of the hypergraph.
基金Supported by the National Natural Science Foundation of China(No.11671124)
文摘A remarkable connection between the clique number and the Lagrangian of a graph was established by Motzkin and Straus. Later, Rota Bul′o and Pelillo extended the theorem of Motzkin-Straus to r-uniform hypergraphs by studying the relation of local(global) minimizers of a homogeneous polynomial function of degree r and the maximal(maximum) cliques of an r-uniform hypergraph. In this paper, we study polynomial optimization problems for non-uniform hypergraphs with four different types of edges and apply it to get an upper bound of Tur′an densities of complete non-uniform hypergraphs.
基金This work was supported by the National Natural Science Foundation of China (Grant No. 19771040)and the Natural Science Foundation of Guangdong Province.
文摘The explicit formula for (k+l)-uniform linear acyclic hypergraphs and the counting series for unlabeled (k +1)-uniform linear acyclic hypergraphs are obtained.
基金This work was supported by the National Natural Science Foundation of China(Grant Nos.11871073,11771016).
文摘Let G be a connected hypergraph with even uniformity,which contains cut vertices.Then G is the coalescence of two nontrivial connected sub-hypergraphs(called branches)at a cut vertex.Let A(G)be the adjacency tensor of G.The least H-eigenvalue of A(G)refers to the least real eigenvalue of A(G)associated with a real eigenvector.In this paper,we obtain a perturbation result on the least H-eigenvalue of A(G)when a branch of G attached at one vertex is relocated to another vertex,and characterize the unique hypergraph whose least H-eigenvalue attains the minimum among all hypergraphs in a certain class of hypergraphs which contain a fixed connected hypergraph.
基金Supported by the National Natural Science Foundation of China (No.10671199)
文摘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.