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

An Upper Bound for the Transversal Number of Connected k-Uniform Hypergraphs

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.

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.

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 SPECTRAL RADIUS OF UNIFORM HYPERGRAPH DETERMINED BY THE SIGNLESS LAPLACIAN MATRIX

This paper studies the problem of the spectral radius of the uniform hypergraph determined by the signless Laplacian matrix.The upper bound of the spectral radius of a uniform hypergraph is obtained by using Rayleigh principle and the perturbation of the spectral radius under moving the edge operation,and the extremal hypergraphs are characterized for both supertree and unicyclic hypergraphs.The spectral radius of the graph is generalized.

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.

Maximum Cliques of Hypergraphs and Polynomial Optimization

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.