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 .     

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.     

Computing rectangle enclosures

The rectangle enclosure problem is the problem of determining the subset of n iso-oriented planar rectangles that enclose a query rectangle Q. In this paper, we use a three layered data structure which is a combination of Range and Priority search trees and answers both the static and dynamic cases of the problem. Both the cases use O(n> log² n) space. For the static case, the query time is O(log² n log log n + K). The dynamic case is supported in O(log³ n + K) query time using O(log³ n) amortized time per update. K denotes the size of the answer. For the d-dimensional space the results are analogous. The query time is O(log^2d-2 n log log n + K) for the static case and O(log^2d-1 n + K) for the dynamic case. The space used is O(n> log^2d-2 n) and the amortized time for an update is O(log^2d-1 n). The existing bounds given for a class of problems which includes the present one, are O(log^2d n + K) query time, O(log^2d n) time for an insertion and O(log^2d-1 n) time for a deletion.     

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.     

L2-approximation of real-valued functions with interpolatory constraints

We construct the polynomial p_m,n^* of degree m which interpolates a given real-valued function f L²[a, b] at pre-assigned n distinct nodes and is the best approximant to f in the L₂-sense over all polynomials of degree m with the same interpolatory character. It is shown that the L₂-error p_m,n^* − f → 0 as m → ∞ if f C[a, b].     

Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs:

(1) P_n, a path on n vertices;

(2) K_1,n^s, the graph obtained from K_1,n by subdividing an edge once;

(3) K_2,ne, the graph obtained from K_2,n by deleting an edge;

(4) K_2,n⁺, the graph obtained from K_2,n by adding an edge between the two degree-n vertices x₁ and x₂, and a pendent edge at each x_i.

Two applications of this result are also discussed in the paper.     

Spectrum of Normal Weighted Composition Operators on the Fock Space Over ℂN

By using commutative C^*-algebra techniques, spectrum and essential spectrum of normal weighted composition operators on the Fock space over C^N are completely characterized. As an application, spectrum of self-adjoint weighted composition operators on the Fock space are obtained also.     

Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

Stable rank boundary principle

Let K denote a compact subset of the complex plane . We present correct proof that the stable rank of A(K) is one. Hereby, A (K) is the algebra of all continuous functions on K which are analytic in the interior of K.

Let G denote a plane domain whose boundary consists of finitely many closed, nonintersecting Jordan curves. We show that for a fixed function of gεC( ), g≠0, the following assertions are equivalent:

Every unimodular element (f, g) is reducible to the principal component exp(C( )).

The zero set Z_g is polynomially convex, i.e., its complement Z_g is connected.

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.

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.     

Simple Minimum (K4-e)-coverings of Complete Multipartite Graphs

A decomposition of K_(n(g))∪Γ, the complete n-partite equipartite graph over gn vertices union a graph Γ(called the excess) that is a subgraph of K_(n(g)), into edge disjoint copies of a graph G is called a simple minimum group divisible covering of type g~n with G if Γ contains as few edges as possible. We examine all possible excesses for simple minimum group divisible(K_4-e)-coverings.Necessary and sufficient conditions are established for their existence.     

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.     

Universal C*-algebras defined by completely bounded unital homomorphisms

Suppose A is a unital C*-algebra and r 1.In this paper,we define a unital C*-algebra C_(cb)*(A,r) and a completely bounded unital homomorphism α_r:A → C_(cb)*(A,r)with the property that C_(cb)*(A,r)=C*(α_r(A))and,for every unital C*-algebra B and every unital completely bounded homomorphism φ:A→ B,there is a(unique)unital *-homomorphism π:C_(cb)*(A,r)→B such thatφ=πoα_r.We prove that,if A is generated by a normal set {t_λ:λ∈Λ},then C_(cb)*(A,r)is generated by the set {α_r(t_λ):λ∈Λ}.By proving an equation of the norms of elements in a dense subset of C_(cb)*(A,r)we obtain that,if Β is a unital C*-algebra that can be embedded into A,then C_(cb)*(B,r)can be naturally embedded into C(cb)*(A,r).We give characterizations of C_(cb)*(A,r)for some special situations and we conclude that C_(cb)*(A,r)will be "nice" when dim(A)≤ 2 and "quite complicated" when dim(A)≥ 3.We give a characterization of the relation between K-groups of A and K-groups of C_(cb)*(A,r).We also define and study some analogous of C_(cb)*(A,r).     

Solution to an extremal problem on bigraphic pairs with a <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connected realization

Let S=(a₁,...,a_m; b₁,...,b_n), where a₁,...,a_m and b₁,...,b_n are two nonincreasing sequences of nonnegative integers. The pair S=(a₁,...,a_m; b₁,...,b_n) is said to be a bigraphic pair if there is a simple bipartite graph G=(X ∪ Y, E) such that a₁,...,a_m and b₁,...,b_n are the degrees of the vertices in X and Y, respectively. Let Z₃ be the cyclic group of order 3. Define σ(Z₃, m, n) to be the minimum integer k such that every bigraphic pair S=(a₁,...,a_m; b₁,...,b_n) with a_m, b_n ≥ 2 and σ(S)=a₁ +... + a_m ≥ k has a Z₃-connected realization. For n=m, Yin[Discrete Math., 339, 2018-2026 (2016)] recently determined the values of σ(Z₃, m, m) for m ≥ 4. In this paper, we completely determine the values of σ(Z₃, m, n) for m ≥ n ≥ 4.     

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.     

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.     

Harnack Differential Inequalities for the Parabolic Equation ut=LF(u) on Riemannian Manifolds and Applications

In this paper, let(M~n, g) be an n-dimensional complete Riemannian manifold with the mdimensional Bakry–mery Ricci curvature bounded below. By using the maximum principle, we first prove a Li–Yau type Harnack differential inequality for positive solutions to the parabolic equation u_t= LF(u)=ΔF(u)-f·F(u),on compact Riemannian manifolds Mn, where F∈C~2(0, ∞), F0 and f is a C~2-smooth function defined on M~n. As application, the Harnack differential inequalities for fast diffusion type equation and porous media type equation are derived. On the other hand, we derive a local Hamilton type gradient estimate for positive solutions of the degenerate parabolic equation on complete Riemannian manifolds. As application, related local Hamilton type gradient estimate and Harnack inequality for fast dfiffusion type equation are established. Our results generalize some known results.     

Quasi-orders on the positive cone of a C

Motivated by an inequality of Choi for unital positive linear maps we introduce a quasi-order on the positive cone of a C^*-algebra and present several intrinsic characterizations for it. We consider also another quasi-order based on an inequality of Kadison, and study interrelationship between those two quasi-orders.