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.

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.

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.

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.

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 Kv3into a special kind of hypergraph K43-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.

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.

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.

The counting series for (k+1)-uniform linear acyclic 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.

Least H-eigenvalue of adjacency tensor of hypergraphs with cut vertices

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.

The Maximum α-spectral Radius of Unicyclic Hypergraphs with Fixed Diameter

For 0≤α<1,theα-spectral radius of an r-uniform hypergraph G is the spectral radius of A_(α)(G)=αD(G)+(1-α)A(G),where D(G)and A(G)are the diagonal tensor of degrees and adjacency tensor of G,respectively.In this paper,we show the perturbation ofα-spectral radius by contracting an edge.Then we determine the unique unicyclic hypergraph with the maximumα-spectral radius among all r-uniform unicyclic hypergraphs with fixed diameter.We also determine the unique unicyclic hypergraph with the maximumα-spectral radius among all r-uniform unicyclic hypergraphs with given number of pendant edges.

Upper bounds for signless Laplacian Z-spectral radius of uniform hypergraphs

Let ■ be a k-uniform hypergraph on n vertices with degree sequence △= d1≥…≥ dn =δ. In this paper, in terms of degree di , we give some upper bounds for the Z-spectral radius of the signless Laplacian tensor (Q(■)) of ■. Some examples are given to show the efficiency of these bounds.

AN INVARIANT FOR HYPERGRAPHS

ＡＮＩＮＶＡＲＩＡＮＴＦＯＲＨＹＰＥＲＧＲＡＰＨＳＷＡＮＧＪＩＡＮＦＡＮＧ（ＩｎｓｔｉｔｕｔｅｏｆＡＰＰｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００８０，ＣｈｉｎａａｎｄＡｓｉａ－Ｐａｃｉｆ...

Perfect Matching in k-partite k-graphs and 3-uniform HM-bipartite Hypergraphs

Let H=(V,E)be an n-balanced k-partite k-graph with partition classes V1,...,Vk.Suppose for every legal(k-1)-tuple f contained in V\V1 and for every legal(k-1)-tuple g contained in V\Vk such that f∪g■E(H),we have d(f)+d(g)≥n+1.In this paper,we prove that under this condition H must have a perfect matching.Another result of this paper is about the perfect matching in 3-uniform hm-bipartite hypergraphs.Let G be a 3-uniform hm-bipartite hypergraph with one of whose sides V1 has the size n,the another side V2 has size 2 n.If for all the legal 2-tuple f with|f∩V1|=1 and for all the legal 2-tuple g with|g∩V1|=0,we have d(f)≥n-2 and d(g)>n/2,then G has a perfect matching.

Sufficient Conditions for Maximally Edge-Connected Hypergraphs

The edge-connectivity of a graph or a hypergraph is defined as the minimum number of edges whose removal renders the graph or hypergraph disconnected.A graph or hypergraph is called maximally edge-connected if the edge-connectivity equals its minimum degree.In this paper,we show that some classical sufficient conditions for graphs to be maximally edge-connected can be generalized to hypergraphs.

The Maximum Lagrangian of 5-uniform Hypergraphs without Containing Two Edges Intersecting at a Vertex

Obtaining Turán densities of hypergraph through determining Lagrangian densities have been studied actively.Sidorenko showed that the Lagrangian density of an r-uniform hypergraph equals the Turán density of the extension of this hypergraph.Indeed,Lagrangian density and Turán density are the same for a large class of hypergraphs such as hypergraphs covering pairs.Let Pr,sbe the r-uniform hypergraph with two edges intersecting at s vertices.Sidorenko determined the Lagrangian densities of Pr,sfor r=3 and s=1 or 2,or r=4 and s=2 or 3.Hefetz and Keevash determined for r=3 and s=0,and Bene Watts,Norin and Yepremyan determined for r≥4 and s=0.The cases r=5 and s=4 or r=6 and s=5 were determined by Norin and Yepremyan.Jenssen showed for r=5,6 or 7,and s=3,4 or 5 respectively.The cases r=4 and s=1 or r=5 and s=2 were determined by Jiang,Peng and Wu,and Hu,Peng and Wu respectively.For r=5,the only remaining case is s=1.In this paper,we determine for this case.

HAMILTONIAN DECOMPOSITION OF COMPLETE BIPARTITE γ-HYPERGRAPHS

In [1] the concepts of paths and cycles of a hypergraph were introduced. In this paper, we give the concepts for bipartite hypergraph and Hamiltonian paths and cycles of a hypergraph, and prove that the complete bipartite 3-hypergraph with q vertices in earh part is Hamiltonian decomposable where q is a prime.