ContributionsChromatic Ramsey numbers

Suppose G is a graph. The chromatic Ramsey number r_c(G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let M_n = min[r_c(G): χ(G) = n]. It was conjectured by Burr et al. (1976) that M_n = (n − 1)² + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M₆ and M₇.     

A matrix problem associated with computing Cohen-Macaulay type

Suppose A∈M_n×m(F), B∈M_n×t(F) for some field F. Define Г(AB) to be the set of n×n diagonal matrices D such that the column space of DA is contained in the column space of B. In this paper we determine dim Г(AB). For matrices AB of the same rank we provide an algorithm for computing dim Г(AB).     

Maximal IM-unextendable graphs

A graph G is maximal IM-unextendable if G is not induced matching extendable and, for every two nonadjacent vertices x and y, G+xy is induced matching extendable. We show in this paper that a graph G is maximal IM-unextendable if and only if G is isomorphic to M_r(K_s(K_n1K_n2K_nt)), where M_r is an induced matching of size r, r1, t=s+2, and each n_i is odd.     

Cellular Chain Complex of Small Covers with Integer Coefficients and Its Application

Let Pⁿ be a simple n-polytope with a Z²-characteristic function λ. And h is a Morse function over Pⁿ. Then the small cover Mⁿ(λ) corresponding to the pair (Pⁿ, λ) has a cell structure given by h. From this cell structure we can derive a cellular chain complex of Mⁿ(λ) with integer coefficients. In this paper, firstly, we discuss the highest dimensional boundary morphism ∂_n of this cellular chain complex and get that ∂_n=0 or 2 by a natural way. And then, from the well-known result that the submanifold corresponding to (F, λ_F) is naturally a small cover with dimension k, where F is any k-face of Pⁿ and λ_F is the restriction of λ on F, we get that ∂_k=0 or ±2 for 0 ≤ k < n. Finally, by using the definition of inherited characteristic function which is the restriction of λ on the faces of Pⁿ, we get a way to calculate the homology groups of Mⁿ(λ). Applying our result to a 3-small cover we have that the homology groups of any 3-small cover is torsion-free or has only 2-torsion.     

A sufficient and necessary condition for an OWA bag mapping having the self-identity

A mapping ƒ : _n=1^∞Iⁿ → I is called a bag mapping having the self-identity if for every (x₁,…,x_n) ε _i=1^∞Iⁿ we have (1) ƒ(x₁,…,x_n) = ƒ(x_i1,…,x_in) for any arrangement (i₁,…,i_n) of {1,…,n}; monotonic; (3) ƒ(x₁,…,x_n, ƒ(x₁,…,x_n)) = ƒ(x₁,…,x_n). Let {ω_i,n : I = 1,…,n;n = 1,2,…} be a family of non-negative real numbers satisfying Σ_i=1ⁿω_i,n = 1 for every n. Then one calls the mapping ƒ : _i=1^∞Iⁿ → I defined as follows an OWA bag mapping: for every (x₁,…,x_n) ε _i=1^∞Iⁿ, ƒ(x₁,…,x_n) = Σ_i=1ⁿω_i,ny_i, where y_i is the it largest element in the set {x₁,…,x_n}. In this paper, we give a sufficient and necessary condition for an OWA bag mapping having the self-identity.     

Commuting pairs and triples of matrices and related varieties

In this note, we show that the set of all commuting d-tuples of commuting n×n matrices that are contained in an n-dimensional commutative algebra is a closed set, and therefore, Gerstenhaber's theorem on commuting pairs of matrices is a consequence of the irreduciblity of the variety of commuting pairs. We show that the variety of commuting triples of 4×4 matrices is irreducible. We also study the variety of n-dimensional commutative subalgebras of M_n(F), and show that it is irreducible of dimension n²−n for n4, but reducible, of dimension greater than n²−n for n7.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

Asymptotic Behaviors for Critical Branching Processes with Immigration

In this paper, we investigate the asymptotic behaviors of the critical branching process with immigration {Z_n, n ≥ 0}. First we get some estimation for the probability generating function of Zn. Based on it, we get a large deviation for Z_(n+1)/Z_n. Lower and upper deviations for Zn are also studied. As a by-product, an upper deviation for max_(1≤i≤n) Z_i is obtained.     

Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers

The Ramsey number r(H,K_n) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K_2,m,K_n)(m−1+o(1))(n/log n)² and r(C_2m,K_n)c(n/log n)^m/(m−1) for m fixed and n→∞. Also r(K_2,n,K_n)=Θ(n³/log² n) and .     

Covering hypercubes by isometric paths

An isometric path is merely any shortest path between two vertices. If the vertices of the hypercube Q_n are represented by the set of 0–1 vectors of length n, an isometric path is obtained by changing the coordinates of a vector one at a time, never changing the same coordinate more than once. The minimum number of isometric paths required to cover the vertices of Q_n is at least 2ⁿ/(n+1). We show that when n+1 is a power of 2, the lower bound is in fact the minimum. In doing so, we construct a family of disjoint isometric paths which can be used to find an upper bound for additional classes of hypercubes.     

How many maxima can there be?

Let C be a planar region. Choose n points p₁,,p_nI.I.D. from the uniform distribution over C. Let M^C_n be the number of these points that are maximal. If C is convex it is known that either E(M^C_n)=Θ(√n)> or E(M^C_n)=O(log n). In this paper we will show that, for general C, there is very little that can be said, a-priori, about E(M^C_n). More specifically we will show that if g is a member of a large class of functions then there is always a region C such that E(M^C_n)=Θ(g(n)). This class contains, for example, all monotically increasing functions of the form g(n)= nln^βn, where 0<<1 and β0. This class also contains nondecreasing functions like g(n)=ln^*n. The results in this paper remain valid in higher dimensions.     

k-Lucas numbers and associated bipartite graphs

For a positive integer k2, the k-Fibonacci sequence {g_n^(k)} is defined as: g₁^(k)==g_k−2^(k)=0, g_k−1^(k)=g_k^(k)=1 and for n>k2, g_n^(k)=g_n−1^(k)+g_n−2^(k)++g_n−k^(k). Moreover, the k-Lucas sequence {l_n^(k)} is defined as l_n^(k)=g_n−1^(k)+g_n+k−1^(k) for n1. In this paper, we consider the relationship between g_n^(k) and l_n^(k) and 1-factors of a bipartite graph.     

Generalization of two results of Hilton on total-colourings of a graph

We generalize two results of Hilton on total-colourings of a graph. The first generalized result unifies several previous results/proof techniques of Bermond, Chen, Chew, Fu, Hilton, Wang, and Yap. Applying the second generalized result, we prove that if G K_{n, n} is such that Δ(G) = n − 1 and the complement of G with respect to K_{n, n} contains a 1-factor, then its total chromatic number is Δ(G) + 1.     

Bipartite dimensions and bipartite degrees of graphs

A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G'sbipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d(G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d(K_n) = [log₂n], η(K_n) = d(K_n) for n 16, and η(K_n) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices.     

The polytope of degree sequences of hypergraphs

Let D_n(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope D_n(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes D_n(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on D_n(2). Our main results concern the extreme points and facets of D_n(r). We characterize adjacency of extreme points of D_n(r) and, in the case r=2, determine the distance between two given vertices in the graph of D_n(2). We give a characterization of when a linear inequality determines a facet of D_n(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of D_n(2); find an explicit family of Erdös–Gallai type facets of D_n(r); and describe a simple lifting procedure that produces a facet of D_n+1(r) from one of D_n(r).     

“Drawings since hit tables in lotteries” and a new multivariate geometric distribution

In number lotteries people choose r numbers out of s. Weekly published “drawings since hit tables” indicate how many drawings have taken place since each of the s numbers was last selected as a winning number. Among many lotto players, they enhance the widespread belief that numbers should be “due” if they have not come up for a long time. Under the assumptions of independence of the drawings and equiprobability of all possible combinations, the random s-vectors Y_n, n 1, of entries in a drawings since hit table after n drawings form a Markov chain. The limit distribution of Y_n as n → ∞ is a new multivariate generalization of the geometric distribution. The determination of the distribution of the maximum entry in a drawings since hit table within the first n draws of a lottery seems to be an open problem.     

Almost resolvable maximum packings of complete graphs with 5-cycles

Let X be the vertex set of K_nA k-cycle packing of K_n is a triple (X,C,L), where C is a collection of edge disjoint k-cycles of K_n and L is the collection of edges of K_n not belonging to any of the k-cycles in C. A k-cycle packing (X,C,L) is called resolvable if C can be partitioned into almost parallel classes. A resolvable maximum k-cycle packing of K_n, denoted by k-RMCP(n), is a resolvable k-cycle packing of K_n, (X,C,L), in which the number of almost parallel classes is as large as possible. Let D(n, k) denote the number of almost parallel classes in a k-RMCP(n). D(n, k) for k = 3, 4 has been decided. When n ≡ k (mod 2k) and k ≡ 1 (mod 2) or n ≡ 1 (mod 2k) and k ∈{6, 8, 10, 14}∪{m: 5≤m≤49, m ≡ 1 (mod 2)}, D(n, k) also has been decided with few possible exceptions. In this paper, we shall decide D(n, 5) for all values of n≥5.     

Asymptotic behavior of a nonlinear delay difference equation

This paper considers a class of nonlinear difference equations

Δ₃y_n + ƒ(n, y_n, y_n−r) = 0, n N (n₀)

. A necessary and sufficient condition for the existence of a bounded nonoscillatory solution is given.     

π-Armendariz rings relative to a monoid

Let Mbe a monoid. A ring Ris called M-π-Armendariz if whenever α = a₁g₁+ a₂g₂+ · · · + a_ng_n, β = b₁h₁+ b₂h₂+ · · · + b_mh_m ∈ R[M] satisfy αβ ∈ nil(R[M]), then aibj ∈ nil(R) for all i, j. A ring R is called weakly 2-primal if the set of nilpotent elements in R coincides with its Levitzki radical. In this paper, we consider some extensions of M-π-Armendariz rings and further investigate their properties under the condition that R is weakly 2-primal. We prove that if R is an M-π-Armendariz ring then nil(R[M]) = nil(R)[M]. Moreover, we study the relationship between the weak zip-property (resp., weak APP-property, nilpotent p.p.-property, weak associated prime property) of a ring R and that of the monoid ring R[M] in case R is M-π-Armendariz.     

A note on convergence in Banach spaces of cotype p

Let B be a separable Banach space. The following is one of the results proved in this paper. The Banach space B is of cotype p if and only if

1. d_n, n 1, has no subsequence converging in probability, and

2. ∑_{n 1}|a_n|^p < ∞ whenever ∑_{n 1}a_nd_n converges almost surely are equivalent for every sequence d_n, n 1, of symmetric independent random elements taking values in B.