The Erdös-Faber-Lovász Conjecture for Gap-Restricted 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.

RELATIONS AMONG SOME PARAMETERS OF HYPERGRAPHS

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.

Random Hypergraphs and Subset Systems

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.

The Spectral Radii of Intersecting Uniform Hypergraphs

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.

Turán number of Berge linear forests in uniform hypergraphs

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,).

On the Turán Density of Uniform 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 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.

Uniform Hypergraphs under Certain Intersection Constraints between Hyperedges

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.

On the Sizes of k-edge-maximal r-uniform Hypergraphs

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.

On Graph-Lagrangians and Clique Numbers of 3-Uniform Hypergraphs

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.

Counting acyclic hypergraphs

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.

A novel complex-high-order graph convolutional network paradigm:ChyGCN

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.

Dense 3-uniform hypergraphs containing a large clique

An r-uniform graph C is dense if and only if every proper subgraph G' of G satisfies λ(G') < λ(G).,where λ(G) is the Lagrangian of a hypergraph G. In 1980's, Sidorenko showed that π(F), the Turán density of an γ-uniform hypergraph F is r! multiplying the supremum of the Lagrangians of all dense F-hom-free γ-uniform hypergraphs. This connection has been applied in the estimating Turán density of hypergraphs. When γ=2 the result of Motzkin and Straus shows that a graph is dense if and only if it is a complete graph. However,when r ≥ 3, it becomes much harder to estimate the Lagrangians of γ-uniform hypergraphs and to characterize the structure of all dense γ-uniform graphs. The main goal of this note is to give some sufficient conditions for3-uniform graphs with given substructures to be dense. For example, if G is a 3-graph with vertex set [t] and m edges containing [t-1]^(3),then G is dense if and only if m≥{t-2 3)+(t-2 2)+1. We also give a sufficient condition on the number of edges for a 3-uniform hypergraph containing a large clique minus 1 or 2 edges to be dense.

The Maximum and Minimum Degree of the Random r-uniform r-partite Hypergraphs

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.

Decompositions of the 3-uniform hypergraphs K_v^(3) into hypergraphs of a certain type

In this paper,we investigate a generalization of graph decomposition,called hypergraph decomposition.We show that a decomposition of a 3-uniform hypergraph K_v^(3)into a special kind of hypergraph K_4^(3)-e exists if and only if v≡0,1,2(mod 9)and v≥9.

Paths and cycles of hypergraphs

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.

Spectral radius of uniform hypergraphs and degree sequences

We present several upper bounds for the adjacency and signless Laplacian spectral radii of uniform hypergraphs in terms of degree sequences.

Extremality of Graph Entropy Based on Degrees of Uniform Hypergraphs with Few Edges

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 Adjacency and Signless Laplacian Spectra of Cored Hypergraphs and Power Hypergraphs

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.

Laplacian and signless Laplacian Z-eigenvalues of uniform hypergraphs

We show that a connected uniform hypergraph G is odd-bipartite if and only if G has the same Laplacian and signless Laplacian Z-eigenvalues. We obtain some bounds for the largest （signless） Laplacian Z-eigenvalue of a hypergraph. For a k-uniform hyperstar with d edges （2d ≥ k ≥ 3）, we show that its largest （signless） Laplacian Z-eigenvalue is d.

On Size of Unicycle Hypergraphs

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.