Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities a...Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities are widespread and significantly influence collective dynamics.Here,we extend the synchronization alignment function framework to hypergraphs of arbitrary order by leveraging the multi-order Laplacian matrix to encode higher-order interactions.Our findings reveal that the upper bound of synchronous behavior is determined by the maximum eigenvalue of the multi-order Laplacian matrix.Furthermore,we decompose the contribution of each hyperedge to this eigenvalue and utilize it as a basis for designing an eigenvalue-based topology modification algorithm.This algorithm effectively enhances the upper bound of synchronous behavior without altering the total number of higher-order interactions.Our study provides new insights into dynamical optimization and topology tuning in hypergraphs,advancing the understanding of the interplay between higher-order interactions and collective dynamics.展开更多
This paper mainly studies the influence maximization problem of threshold models in hypergraphs,which aims to identify the most influential nodes in hypergraphs.Firstly,we introduce a novel information diffusion rule ...This paper mainly studies the influence maximization problem of threshold models in hypergraphs,which aims to identify the most influential nodes in hypergraphs.Firstly,we introduce a novel information diffusion rule in hypergraphs based on Threshold Models and conduct the stability analysis.Then we extend the CI-TM algorithm,originally designed for complex networks,to hypergraphs,denoted as the H-CI-TM algorithm.Secondly,we use an iterative approach to get the globally optimal solutions.The analysis reveals that our algorithm ultimately identifies the most influential set of nodes.Based on the numerical simulations,HCI-TM algorithm outperforms several competing algorithms in both synthetic and real-world hypergraphs.Essentially,when provided with the same number of initial seeds,our algorithm can achieve a larger activation size.Our method not only accurately assesses the influence of individual nodes but also identifies a set of nodes with greater impact.Furthermore,our results demonstrate good scalability when handling intricate relationships and large-scale hypergraphs.The outcomes of our research provide substantial support for the applications of the threshold models across diverse fields,including social network analysis and marketing strategies.展开更多
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.展开更多
In this paper, we consider the r-uniform hypergraphs H with spectral radius at most ■. We show that H must have a quipus-structure, which is similar to the graphs with spectral radius at most ■ [Woo-Neumaier, Graphs...In this paper, we consider the r-uniform hypergraphs H with spectral radius at most ■. We show that H must have a quipus-structure, which is similar to the graphs with spectral radius at most ■ [Woo-Neumaier, Graphs Combin. 2007].展开更多
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.展开更多
It is proved in this paper that if G is a simple connected r-uniform hypergraph with ｜｜G｜｜≥2, then G has an edge e such that G - e - V1（e） is also a simple connected r-uniform hypergraph. This reduction is natu...It is proved in this paper that if G is a simple connected r-uniform hypergraph with ｜｜G｜｜≥2, then G has an edge e such that G - e - V1（e） is also a simple connected r-uniform hypergraph. This reduction is naturally called a combined Graham reduction. Under the simple reductions of single edge removals and single edge contractions, the minor minimal connected simple r-uniform hypergraphs are also determined.展开更多
In this paper, we set ρ_r =~r4^（1/2） and ρ′_r= β^（-1/r）, where β =-1/6 ·（100 ＋ 12·（69）^（1/2））^（1/3）-2/（3·（100＋12·（69）^（1/2）））^（1/3）＋4/3≈0.2451223338. We consider conn...In this paper, we set ρ_r =~r4^（1/2） and ρ′_r= β^（-1/r）, where β =-1/6 ·（100 ＋ 12·（69）^（1/2））^（1/3）-2/（3·（100＋12·（69）^（1/2）））^（1/3）＋4/3≈0.2451223338. We consider connected r-uniform hypergraphs with spectral radius between ρ_r and ρ′_r and give a description of such hypergraphs.展开更多
The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decompos...The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs Kn（3） into k-cycles （3 ≤ k 〈 n） was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that Kn·5m（3） can be decomposed into 5-cycles for n ∈ {5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.展开更多
Suppose to toss an independent coin with equal probability of success and failure for each subset of [n] = {1, 2, ..., n}, and form the random hypergraph H(n) by taking as hyperedges the subsets with successful coin t...Suppose to toss an independent coin with equal probability of success and failure for each subset of [n] = {1, 2, ..., n}, and form the random hypergraph H(n) by taking as hyperedges the subsets with successful coin tosses. It is proved that H(n) is almost surely connected. By defining a graph G(S) according to a subset system S, it is shown that the intersecting problem is NP-complete.展开更多
A k-edge coloring of a hypergraph H is a coloring of the edges of H with k colors such that any two intersecting edges receive distinct colors. The Erdos-Faber-Lovasz conjecture states that every loopless linear hyper...A k-edge coloring of a hypergraph H is a coloring of the edges of H with k colors such that any two intersecting edges receive distinct colors. The Erdos-Faber-Lovasz conjecture states that every loopless linear hypergraph with n vertices has an n-edge coloring. In 2021,Kang, Kelly, K¨uhn, Methuku and Osthus confirmed the conjecture for sufficiently large n. In this paper, the conjecture is verified for collision-weak hypergraphs. This result strictly extends two related ones of Bretto, Faisant and Hennecart in 2020.展开更多
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.展开更多
Complex systems can be more accurately described by higher-order interactions among multiple units.Hypergraphs excel at depicting these interactions,surpassing the binary limitations of traditional graphs.However,retr...Complex systems can be more accurately described by higher-order interactions among multiple units.Hypergraphs excel at depicting these interactions,surpassing the binary limitations of traditional graphs.However,retrieving valuable information from hypergraphs is often challenging due to their intricate interconnections.To address this issue,we introduce a new category of structural patterns,hypermotifs,which are defined as statistically significant local structures formed by interconnected hyperedges.We propose a systematic framework for hypermotif extraction.This framework features the encoding,census,and evaluation of higher-order patterns,effectively overcoming their inherent complexity and diversity.Our experimental results demonstrate that hypermotifs can serve as higher-order fingerprints of real-world hypergraphs,helping to identify hypergraph classes based on network functions.These motifs potentially represent preferential attachments and key modules in real-world hypergraphs,arising from specific mechanisms or constraints.Our work validates the efficacy of hypermotifs in exploring hypergraphs,offering a powerful tool for revealing the design principles and underlying dynamics of interacting systems.展开更多
For an r-uniform hypergraph F,the anti-Ramsey number ar(n,r,F)is the minimum number c of colors such that an n-vertex r-uniform complete hypergraph equipped any edge-coloring with at least c colors unavoidably contain...For an r-uniform hypergraph F,the anti-Ramsey number ar(n,r,F)is the minimum number c of colors such that an n-vertex r-uniform complete hypergraph equipped any edge-coloring with at least c colors unavoidably contains a rainbow copy of F.In this paper,we determine the anti-Ramsey number for cycles of length three in r-uniform hypergraphs for r≥3,including linear cycles,loose cycles and Berge cycles.展开更多
Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers...Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers are focusing on the centrality problem in hypergraphs.Specifically,researchers are tackling the challenge of utilizing higher-order structures to effectively define centrality metrics.This paper presents a novel approach,LGK,derived from the K-shell decomposition method,which incorporates both global and local perspectives.Empirical evaluations indicate that the LGK method provides several advantages,including reduced time complexity and improved accuracy in identifying critical nodes in hypergraphs.展开更多
Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to cert...Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to certain conditions.This paper is to generalize the coprime labelings of graph to hypergraph.We give the definition of coprime labelings of hypergraph.By using Rosser-Schoenfeld's inequality and the coprime mapping theorem of Pomerance and Selfridge,we prove that some linear hypergraphs are prime.展开更多
Let F be a graph and H be a hypergraph.We say that H contains a Berge-F If there exists a bijectionψ:E(F)→E(H)such that for Ve E E(F),e C(e),and the Turan number of Berge-F is defined to be the maximum number of edg...Let F be a graph and H be a hypergraph.We say that H contains a Berge-F If there exists a bijectionψ:E(F)→E(H)such that for Ve E E(F),e C(e),and the Turan number of Berge-F is defined to be the maximum number of edges in an r-uniform hypergraph of order n that is Berge-F-free,denoted by ex,(n,Berge-F).A linear forest is a graph whose connected components are all paths or isolated vertices.Let Ln,k be the family of all linear forests of n vertices with k edges.In this paper,Turan number of Berge-Ln,in an r-uniform hypergraph is studied.When r≥k+1 and 3≤r≤l[]=1,we determine 2 the exact value of ex,(n,Berge-Ln,)respectively.When K-1≤r≤k,we 2 determine the upper bound of ex,(n,Berge-Ln,).展开更多
Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the mi...Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the minimum cardinality of transversals.In 2021,Diao verified that the upper bound of transversal number for any connected 3-uniform hypergraph H is at most 2m+1/3,that is,τ(H)≤2m+1/3, where m is the size of H.Moreover,they gave the necessary and sufficient conditions to reachthe upper bound,namely τ(H)≤2m+1/3,if and only if H is a hypertreewitha 3 perfect matching.In this paper,we investigate the transversal number of connected kunifom hypergraphs for k≥3.We confrm that τ(H)≤(k-1)m+1/k for any k-unifom hypegraphH with size m.Furthermore,we show that τ(H)≤(k-1)m+1/k if and only if H is a hypertree with a perfect matching,which generalizes the results of Diao.展开更多
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.展开更多
基金Project supported by the National Natural Science Foundation of China(Grant Nos.12247153,T2293771,and 12247101)the Zhejiang Provincial Natural Science Foundation of China(Grant No.LTGY24A050002)+3 种基金the Sichuan Science and Technology Program(Grant Nos.2024NSFSC1364 and 2023NSFSC1919)the Project of Huzhou Science and Technology Bureau(Grant No.2022YZ29)the UESTCYDRI research start-up(Grant No.U03210066)the New Cornerstone Science Foundation through the Xplorer Prize。
文摘Complex networks play a crucial role in the study of collective behavior,encompassing the analysis of dynamical properties and network topology.In real-world systems,higher-order interactions among multiple entities are widespread and significantly influence collective dynamics.Here,we extend the synchronization alignment function framework to hypergraphs of arbitrary order by leveraging the multi-order Laplacian matrix to encode higher-order interactions.Our findings reveal that the upper bound of synchronous behavior is determined by the maximum eigenvalue of the multi-order Laplacian matrix.Furthermore,we decompose the contribution of each hyperedge to this eigenvalue and utilize it as a basis for designing an eigenvalue-based topology modification algorithm.This algorithm effectively enhances the upper bound of synchronous behavior without altering the total number of higher-order interactions.Our study provides new insights into dynamical optimization and topology tuning in hypergraphs,advancing the understanding of the interplay between higher-order interactions and collective dynamics.
基金Supported by the National Natural Science Foundation of China(Grant No.12371516)the Natural Science Foundation of Liaoning Province(Grant No.2022-MS-152)the Fundamental Research Funds for the Central Universities(Grant No.DUT22LAB305)。
文摘This paper mainly studies the influence maximization problem of threshold models in hypergraphs,which aims to identify the most influential nodes in hypergraphs.Firstly,we introduce a novel information diffusion rule in hypergraphs based on Threshold Models and conduct the stability analysis.Then we extend the CI-TM algorithm,originally designed for complex networks,to hypergraphs,denoted as the H-CI-TM algorithm.Secondly,we use an iterative approach to get the globally optimal solutions.The analysis reveals that our algorithm ultimately identifies the most influential set of nodes.Based on the numerical simulations,HCI-TM algorithm outperforms several competing algorithms in both synthetic and real-world hypergraphs.Essentially,when provided with the same number of initial seeds,our algorithm can achieve a larger activation size.Our method not only accurately assesses the influence of individual nodes but also identifies a set of nodes with greater impact.Furthermore,our results demonstrate good scalability when handling intricate relationships and large-scale hypergraphs.The outcomes of our research provide substantial support for the applications of the threshold models across diverse fields,including social network analysis and marketing strategies.
文摘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 the National Natural Science Foundation of China(Grant No.11601368)
文摘In this paper, we consider the r-uniform hypergraphs H with spectral radius at most ■. We show that H must have a quipus-structure, which is similar to the graphs with spectral radius at most ■ [Woo-Neumaier, Graphs Combin. 2007].
基金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.
基金Supported by NRF South Africathe National Natural Science Foundation of China(Grant No.11161032)
文摘It is proved in this paper that if G is a simple connected r-uniform hypergraph with ｜｜G｜｜≥2, then G has an edge e such that G - e - V1（e） is also a simple connected r-uniform hypergraph. This reduction is naturally called a combined Graham reduction. Under the simple reductions of single edge removals and single edge contractions, the minor minimal connected simple r-uniform hypergraphs are also determined.
基金Supported by the National Natural Science Foundation of China(Grant Nos.116013681140143411771322)
文摘In this paper, we set ρ_r =~r4^（1/2） and ρ′_r= β^（-1/r）, where β =-1/6 ·（100 ＋ 12·（69）^（1/2））^（1/3）-2/（3·（100＋12·（69）^（1/2）））^（1/3）＋4/3≈0.2451223338. We consider connected r-uniform hypergraphs with spectral radius between ρ_r and ρ′_r and give a description of such hypergraphs.
基金Supported by the National Natural Science Foundation of China(Grant No.11161032)
文摘The problem of decomposing a complete 3-uniform hypergraph into Hamilton cycles was introduced by Bailey and Stevens using a generalization of Hamiltonian chain to uniform hypergraphs by Katona and Kierstead. Decomposing the complete 3-uniform hypergraphs Kn（3） into k-cycles （3 ≤ k 〈 n） was then considered by Meszka and Rosa. This study investigates this problem using a difference pattern of combinatorics and shows that Kn·5m（3） can be decomposed into 5-cycles for n ∈ {5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.
文摘Suppose to toss an independent coin with equal probability of success and failure for each subset of [n] = {1, 2, ..., n}, and form the random hypergraph H(n) by taking as hyperedges the subsets with successful coin tosses. It is proved that H(n) is almost surely connected. By defining a graph G(S) according to a subset system S, it is shown that the intersecting problem is NP-complete.
基金Supported by the National Natural Science Foundation of China (Grant No. 12071265)the Natural Science Foundation of Shandong Province (Grant No. ZR2019MA032)。
文摘A k-edge coloring of a hypergraph H is a coloring of the edges of H with k colors such that any two intersecting edges receive distinct colors. The Erdos-Faber-Lovasz conjecture states that every loopless linear hypergraph with n vertices has an n-edge coloring. In 2021,Kang, Kelly, K¨uhn, Methuku and Osthus confirmed the conjecture for sufficiently large n. In this paper, the conjecture is verified for collision-weak hypergraphs. This result strictly extends two related ones of Bretto, Faisant and Hennecart in 2020.
基金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.
基金supported by the National Natural Science Foundation of China(Nos.62101095&62071095).
文摘Complex systems can be more accurately described by higher-order interactions among multiple units.Hypergraphs excel at depicting these interactions,surpassing the binary limitations of traditional graphs.However,retrieving valuable information from hypergraphs is often challenging due to their intricate interconnections.To address this issue,we introduce a new category of structural patterns,hypermotifs,which are defined as statistically significant local structures formed by interconnected hyperedges.We propose a systematic framework for hypermotif extraction.This framework features the encoding,census,and evaluation of higher-order patterns,effectively overcoming their inherent complexity and diversity.Our experimental results demonstrate that hypermotifs can serve as higher-order fingerprints of real-world hypergraphs,helping to identify hypergraph classes based on network functions.These motifs potentially represent preferential attachments and key modules in real-world hypergraphs,arising from specific mechanisms or constraints.Our work validates the efficacy of hypermotifs in exploring hypergraphs,offering a powerful tool for revealing the design principles and underlying dynamics of interacting systems.
基金supported by the National Natural Science Foundation of China(No.11901292,12301459).
文摘For an r-uniform hypergraph F,the anti-Ramsey number ar(n,r,F)is the minimum number c of colors such that an n-vertex r-uniform complete hypergraph equipped any edge-coloring with at least c colors unavoidably contains a rainbow copy of F.In this paper,we determine the anti-Ramsey number for cycles of length three in r-uniform hypergraphs for r≥3,including linear cycles,loose cycles and Berge cycles.
文摘Hypergraphs,which encapsulate interactions of higher-order beyond mere pairwise connections,are essential for representing polyadic relationships within complex systems.Consequently,an increasing number of researchers are focusing on the centrality problem in hypergraphs.Specifically,researchers are tackling the challenge of utilizing higher-order structures to effectively define centrality metrics.This paper presents a novel approach,LGK,derived from the K-shell decomposition method,which incorporates both global and local perspectives.Empirical evaluations indicate that the LGK method provides several advantages,including reduced time complexity and improved accuracy in identifying critical nodes in hypergraphs.
基金Supported by the Natural Science Foundation of Chongqing(CSTB2022NSCQ-MSX0884)。
文摘Graph labeling is the assignment of integers to the vertices,edges,or both,subject to certain conditions.Accordingly,hypergraph labeling is also the assignment of integers to the vertices,edges,or both,subject to certain conditions.This paper is to generalize the coprime labelings of graph to hypergraph.We give the definition of coprime labelings of hypergraph.By using Rosser-Schoenfeld's inequality and the coprime mapping theorem of Pomerance and Selfridge,we prove that some linear hypergraphs are prime.
文摘Let F be a graph and H be a hypergraph.We say that H contains a Berge-F If there exists a bijectionψ:E(F)→E(H)such that for Ve E E(F),e C(e),and the Turan number of Berge-F is defined to be the maximum number of edges in an r-uniform hypergraph of order n that is Berge-F-free,denoted by ex,(n,Berge-F).A linear forest is a graph whose connected components are all paths or isolated vertices.Let Ln,k be the family of all linear forests of n vertices with k edges.In this paper,Turan number of Berge-Ln,in an r-uniform hypergraph is studied.When r≥k+1 and 3≤r≤l[]=1,we determine 2 the exact value of ex,(n,Berge-Ln,)respectively.When K-1≤r≤k,we 2 determine the upper bound of ex,(n,Berge-Ln,).
基金supported by the National Natural Science Foundation of China(No.12171089).
文摘Let H be a hypergraph with vertex set V(H)and hyperedge set E(H).We call a vertex set R ■V(H)a transversal if it has a nonempty intersection with every hyperedge of H.The transversal number,denoted by τ(H),is the minimum cardinality of transversals.In 2021,Diao verified that the upper bound of transversal number for any connected 3-uniform hypergraph H is at most 2m+1/3,that is,τ(H)≤2m+1/3, where m is the size of H.Moreover,they gave the necessary and sufficient conditions to reachthe upper bound,namely τ(H)≤2m+1/3,if and only if H is a hypertreewitha 3 perfect matching.In this paper,we investigate the transversal number of connected kunifom hypergraphs for k≥3.We confrm that τ(H)≤(k-1)m+1/k for any k-unifom hypegraphH with size m.Furthermore,we show that τ(H)≤(k-1)m+1/k if and only if H is a hypertree with a perfect matching,which generalizes the results of Diao.
基金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.
