Enumeration of Maximum Acyclic Hypergraphs

Abstract Acyclic hypergraphs are analogues of forests in graphs.They are very useful in the design ofdatabases. In this article,the maximum size of an acvclic hypergraph is determined and the number of maximumγ-uniform acyclic hypergraphs of order n is shown to be (_(r-1)~n)(n(r-1)-r~2 2r)~(n-r-1).     

连通简单$r$-一致超图的约化

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.     

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.     

BSDE,path-dependent PDE and nonlinear Feynman-Kac formula

We introduce a new type of path-dependent quasi-linear parabolic PDEs in which the continuous paths on an interval [0, t] become the basic variables in the place of classical variables(t, x) ∈ [0, T ] × Rd. This new type of PDEs are formulated through a classical BSDE in which the terminal values and the generators are allowed to be general function of Brownian motion paths. In this way, we establish the nonlinear FeynmanKac formula for a general non-Markovian BSDE. Some main properties of solutions of this new PDEs are also obtained.     

On Alternating Sequences Relative to a c-Matching of a Hypergraph

In[1], C.Berge has modified Theorem 1 of [2]to a theorem which is a charac-terization of maximum c-Matchings in a hypergraph (see[1], P.416, Theorem 2),and at the same time can be considered as a generalization of Berge's theorem on     

Hypergraph Turan Numbers of Vertex Disjoint Cycles

The Turan number of a k-uniform hypergraph H,denoted by exk(n;H),is the maximum number of edges in any k-uniform hypergraph F on n vertices which does not contain H as a subgraph.Let Cl(k)denote the family of all k-uniform minimal cycles of length l;S(l1,…,lr)denote the family of hypergraphs consisting of unions of r vertex disjoint minimal cycles of lengthl1,…lr,respectively,and Cl(k)denote a k-uniform linear cycle of length l.We determine precisely exk(n;S(l1,…,lr)and exk(n;Cl1(k),…,Cl1(k)for sufficiently large n.Our results extend recent results of Füredi and Jiang who determined the Turan numbers for single k-uniform minimal cycles and linear cycles.     

Solvability of monotone tensor complementarity problems

The tensor complementarity problem is a special instance in the class of nonlinear complementarity problems, which has many applications in multi-person noncooperative games, hypergraph clustering problems and traffic equilibrium problems. Two most important research issues are how to identify the solvability and how to solve such a problem via analyzing the structure of the involved tensor. In this paper, based on the concept of monotone mappings, we introduce a new class of structured tensors ...     

Hypergraph Turán Numbers of Vertex Disjoint Cycles

The Turán number of a k-uniform hypergraph H,denoted by ex_k(n;H),is the maximum number of edges in any k-uniform hypergraph F on n vertices which does not contain H as a subgraph.Let C_l~((k)) denote the family of all k-uniform minimal cycles of length l;S(?₁,…,?_r) denote the family of hypergraphs consisting of unions of r vertex disjoint minimal cycles of length ?₁,…?_r,respectively,and C_l~((k))denote a k-uniform linear ...     

Skew Motzkin paths

In this paper, we study the class S of skew Motzkin paths, i.e., of those lattice paths that are in the first quadrat, which begin at the origin, end on the x-axis, consist of up steps U =(1, 1),down steps D =(1,-1), horizontal steps H =(1, 0), and left steps L =(-1,-1), and such that up steps never overlap with left steps. Let S_n be the set of all skew Motzkin paths of length n and let 8_n = |S_n|. Firstly we derive a counting formula, a recurrence and a convolution formula for sequence{8_n}n≥0. Then we present several involutions on S_n and consider the number of their fixed points.Finally we consider the enumeration of some statistics on S_n.     

PARAMETER ESTIMATION FOR A DISCRETELY OBSERVED STOCHASTIC VOLATILITY MODEL WITH JUMPS IN THE VOLATILITY

In this paper a stochastic volatility model is considered. That is, a log price process Y which is given in terms of a volatility process V is studied. The latter is defined such that the log price possesses some of the properties empirically observed by Barndorff-Nielsen & Jiang[6]. In the model there are two sets of unknown parameters, one set corresponding to the marginal distribution of V and one to autocorrelation of V. Based on discrete time observations of the log price the authors discuss how to estimate the parameters appearing in the marginal distribution and find the asymptotic properties.     

Judicious bisection of hypergraphs

Judicious bisection of hypergraphs asks for a balanced bipartition of the vertex set that optimizes several quantities simultaneously.In this paper,we prove that if G is a hypergraph with n vertices and m_i edges of size i for i=1,2,...,k,then G admits a bisection in which each vertex class spans at most(m_1)/2+1/4m_2+…+(1/(2~k)+m_k+o(m_1+…+m_k) edges,where G is dense enough or △(G)= o(n) but has no isolated vertex,which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott.     

网络最短的最优解集结构

The shortest path problem in a network G is to find shortest paths between some specified source vertices and terminal vertices when the lengths of edges are given. The structure of the optimal solutions set on the shortest paths is studied in this paper. First,the conditions of having unique shortest path between two distinguished vertices s and t in a network G are discussed;Second,the structural properties of 2-transformation graph (?) on the shortest-paths for G are presented heavily.     

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 Turán classical result on the Turán 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 λ(G)=λ([t-1]~((3))) provided (t-13)≤m≤(t-13)+_(t-22).They also conjectured:If G is an r-uniform graph with m edges not containing a clique of order t-1,then λ(G)λ([t-1]~((r))) provided (t-1r)≤ m ≤(t-1r)+(t-2r-1).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=t-13+t-22.Regarding this conjecture,we show: If G is a left-compressed 3-uniform graph on the vertex set [t] with m edges and |[t-1]~((3))\E(G)|=p,then λ(G)λ([t-1]~((3))) provided m=(t-13)+(t-22) and t≥17p/2+11.     

图的割宽最大值问题

§ 1　IntroductionThe cutwidth minimization problem for graphs arises from the circuitlayout of VLSIdesigns[1 ] .Chung pointed outthatthe cutwidth often corresponds to the area of the layoutin array layout in VLSI design[2 ] .In the layout models,the cutwidth problem deals withthe number of edges passing over a vertex when all vertices are arranged in a path.For agraph G with vertex set V(G) and edge set E(G) ,a labeling of G is a one-to-one mapping ffrom V(G) to the integers.The cutwid…     

On the α-spectra of Uniform Hypergraphs and Its Associated Graphs

For 0 ≤α 1 and a k-uniform hypergraph H, the tensor A_α(H) associated with H is defined as A_α(H) = αD(H) +(1-α)A(H), where D(H) and A(H) are the diagonal tensor of degrees and the adjacency tensor of H, respectively. The α-spectra of H is the set of all eigenvalues of A_α(H) and the α-spectral radius ρ_α(H) is the largest modulus of the elements in the spectrum of A_α(H). In this paper we define the line graph L(H) of a uniform hypergraph H and prove that ρ_α(H) ≤■ρ_α(L(H)) + 1 + α(Δ-1-δ~*/k), where Δ and δ~* are the maximum degree of H and the minimum degree of L(H), respectively. We also generalize some results on α-spectra of G~(k,s), which is obtained from G by blowing up each vertex into an s-set and each edge into a k-set where 1 ≤ s ≤ k/2.     

EULER SCHEME FOR FRACTIONAL DELAY STOCHASTIC DIFFERENTIAL EQUATIONS BY ROUGH PATHS TECHNIQUES

In this note, we study a discrete time approximation for the solution of a class of delayed stochastic differential equations driven by a fractional Brownian motion with Hurst parameter H ∈(1/2, 1). In order to prove convergence, we use rough paths techniques.Theoretical bounds are established and numerical simulations are displayed.     

Periodic Solutions of a Model of Mitosis in Prog Eggs

In this paper,we discuss a simplified model of mitosis in frog eggs proposed by M.T. Borisuk and J.J. Tyson in [1]. By using rigorous qualitative analysis, we prove the existence of the periodic solutions on a large scale and present the space region of the periodic solutions and the parameter region coresponding to the periodic solution. We also present the space region and the parameter region where there are no periodic solutions. The results are in accordance with the numerical results in [1] up to the qualitative property.     

A Note on Hamiltonian Grids

A complete grid G_(m,n) is the cartesian product of two paths P_m and P_n. In this paper, it is proved that a class of complete grids with two vertices removed are hamiltonian. This result settles a conjecture of S.M. Hedetniemi, S.T. Hede tniemi and P.J. Slater in positive.     

The Error Estimates of Semi-discrete Galerkin Methods for some Non-linear Parabolic Equations

1. Introduction Concerning the finite element analysis for linear and nonlinear parabolic equa tions there are a lot of papers, however, only a few of them devoted to the parabolic problems with mixed boundary conditions. In[1],[2] and [3], the finite element methods for some non-linear parabolic problems are systematically considered, but they are mainly restriced to the cases in which the boundary conditions are of Dirichlet     

完全3-一致超图的圈分解

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 K_n~(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 K_(n·5m)~(3) can be decomposed into 5-cycles for n ∈{5, 7, 10, 11, 16, 17, 20, 22, 26} using computer programming.