Sperner''s theorem with constraints

A set X of subsets of an n-element set S is called an anti-chain if no two elements of X are related by set-wise inclusion. Sperner showed [8] that max |X|=(ⁿ_[n/2]), where |X| denotes the number of elements in X and the maximum is taken over all anti-chains of subsets of S.

Let non-negative integers i_o<n and m_io≠0, m_io+1,…m_n be given. In this paper we give an algorithm for calculating max |X| where the maximum is taken only over anti-chains containing exactly m_i i-element subsets of S for i_o i n.     

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 class of solutions to the gossip problem, part III

We complete the study of NOHO-graphs, begun in Parts I and II of this paper. NOHO- graphs correspond to solutions to the gossip problem where No One Hears his Own information. These are graphs with a linear ordering on their edges such that an increasing path exists from each vertex to every other, but from no vertex to itself. We discard the two such graphs with no 2-valent vertices. In Part I, we translated these graphs into quadruples of integer sequences. In Part II, we characterized and enumerated the realizable quadruples and various subclasses of them. In Part III, we eliminate the overcounting of isomorphic graphs and obtain recurrence relations and generating functions to enumerate the non-isomorphic NOHO-graphs. If u_m=(1,1,2,…) satisfies u_m=3u_m-1–u_m-3, then the number of non-isomorphic NOHO- graphs on 2m+2 vertices is (u_m + u_[m/2]+1 + u_[m/2]+1 - u_[m/2]). We also examine some re lated questions.     

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 .     

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].     

An extended result of Kleitman and Saks concerning binary trees

In a recent paper, D.J. Kleitman and M.E. Saks gave a proof of Huang's conjecture on alphabetic binary trees.

Given a set E = {e_i}, I = 0, 1, 2, …, m and assigned positive weights to its elements and supposing the elements are indexed such that w(e₀) ≤ w(e₁) ≤ … ≤w (e_m), where w(e_i) is the weight of e_i, we call the following sequence E^* a ‘saw-tooth’ sequence

E^*=(e₀,e_m,e₁,…,e_j,e_m−j,…).

Huang's conjecture is: E^* is the most expensive sequence for alphabetic binary trees. This paper shows that this property is true for the L-restricted alphabetic binary trees, where L is the maximum length of the leaves and log₂(m + 1) ≤L≤m.     

Biased partitions and judicious <Emphasis Type="Italic">k</Emphasis>-partitions of graphs

Let G = (V,E) be a graph with m edges. For reals p ∈ [0, 1] and q = 1- p, let m_p(G) be the minimum of qe(V₁) +pe(V₂) over partitions V = V₁ ∪ V₂, where e(V_i) denotes the number of edges spanned by V_i. We show that if mp(G) = pqm-δ, then there exists a bipartition V₁, V₂ of G such that e(V₁) ≤ p²m - δ + p√m/2 + o(√m) and e(V₂) ≤ q²m - δ + q √m/2 + o(√m) for δ = o(m^2/3). This is sharp for complete graphs up to the error term o(√m). For an integer k ≥ 2, let fk(G) denote the maximum number of edges in a k-partite subgraph of G. We prove that if fk(G) = (1 - 1/k)m + α, then G admits a k-partition such that each vertex class spans at most m/k² - Ω(m/k^7.5) edges for α = Ω(m/k⁶). Both of the above improve the results of Bollobás and Scott.     

The Existence of LHMTS(<Emphasis Type="Italic">m</Emphasis><Superscript><Emphasis Type="Italic">v</Emphasis></Superscript>) and LHDTS(<Emphasis Type="Italic">m</Emphasis><Superscript><Emphasis Type="Italic">v</Emphasis></Superscript>)

In this article, we establish the existence of an LHMTS(m^v) for v ≡ 2 (mod 6) and m≡ 3 (mod 6). Thus there exists an LHMTS(m^v) if and only if v(v-1)m² ≡ 0 (mod 3) except possibly for v=6, m≡ 1, 5 (mod 6) and m≠1. In the similar way, the existence of LHDTS(m^v) is completely determined, i.e., there exists an LHDTS(m^v) if and only if v(v-1)m² ≡ 0 (mod 3).     

New families of exact solitary patterns solutions for the nonlinearly dispersive R(m,n) equations

The R(m,n) equations u_tt+a(uⁿ)_xx+b(u^m)_xxtt=0 (a, b const) are investigated by using some ansatze. As a result, new exact solitary patterns solutions and solitary wave solutions are obtained. These obtained solutions show that not only the nonlinearly dispersive R(m,m) equations (m≠1) but also the linearly dispersive R(1,n) equations (m=1) possess solitary patterns solutions, which has infinite slopes or cusps and solitary wave solutions.     

Matrices with zero trace as commutators of nilpotents

Let C ∈ F^n×n have minimum polynomial m(x). Suppose C is of zero trace and m(x) splits over F. Then, except when n = 2 and m(x) = (x - c)² or when n = 3 and m(x) = x - c)² with c ≠ 0, there exist nilpotents A, B ∈ F^n×n such that C = AB - BA.     

On some properties of the series ∑k=0 kx and the Stirling numbers of the second kind

We partially characterize the rational numbers x and integers n 0 for which the sum ∑_k=0^∞ kⁿx^k assumes integers. We prove that if ∑_k=0^∞ kⁿx^k is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where v_a(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.

New identities are also derived for the Stirling numbers, e.g., we show that ∑_k=0²ⁿk! S(2n, k) , for all integers n 1.     

Some explicit formulas for the polynomial decomposition of the matrix exponential and applications

This paper is devoted to the study of some formulas for polynomial decomposition of the exponential of a square matrix A. More precisely, we suppose that the minimal polynomial M_A(X) of A is known and has degree m. Therefore, e^tA is given in terms of P₀(A),…,P_m−1(A), where the P_j(A) are polynomials in A of degree less than m, and some explicit analytic functions. Examples and applications are given. In particular, the two cases m=5 and m=6 are considered.     

On application of the Lanczos method to solution of some partial differential equations

Let A be a square symmetric n × n matrix, φ be a vector from ⁿ, and f be a function defined on the spectral interval of A. The problem of computation of the vector u = f(A)φ arises very often in mathematical physics.

We propose the following method to compute u. First, perform m steps of the Lanczos method with A and φ. Define the spectral Lanczos decomposition method (SLDM) solution as u_m = φ Qf(H)e₁, where Q is the n × m matrix of the m Lanczos vectors and H is the m × m tridiagonal symmetric matrix of the Lanczos method. We obtain estimates for u − u_m that are stable in the presence of computer round-off errors when using the simple Lanczos method.

We concentrate on computation of exp(− tA)φ, when A is nonnegative definite. Error estimates for this special case show superconvergence of the SLDM solution. Sample computational results are given for the two-dimensional equation of heat conduction. These results show that computational costs are reduced by a factor between 3 and 90 compared to the most efficient explicit time-stepping schemes. Finally, we consider application of SLDM to hyperbolic and elliptic equations.     

On the Equation n_1n_2= n_3n_4 Restricted to Factor Closed Sets

We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.     

Strong Laws of Large Numbers for Double Sums of Banach Space Valued Random Elements

For a double array {V_(m,n), m ≥ 1, n ≥ 1} of independent, mean 0 random elements in a real separable Rademacher type p(1 ≤ p ≤ 2) Banach space and an increasing double array {b_(m,n), m ≥1, n ≥ 1} of positive constants, the limit law ■ and in L_p as m∨n→∞ is shown to hold if ■ This strong law of large numbers provides a complete characterization of Rademacher type p Banach spaces. Results of this form are also established when 0 p ≤ 1 where no independence or mean 0 conditions are placed on the random elements and without any geometric conditions placed on the underlying Banach space.     

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.     

Limiting values of the variance and the moments of the dimension of a sum or intersection of random vector subspaces

Let W be an n-dimensional vector space over a field F; for each positive integer m, let the m-tuples (U₁, …, U_m) of vector subspaces of W be uniformly distributed; and consider the statistics X_m,1 dim_F(∑_i=1^m U_i) and X_m,2 dim_F (∩_i=1^m U_i). If F is finite of cardinality q, we determine lim E(X_m,1^k), and lim E(X_m,2^k), and hence, lim var(X_m,1) and lim var(X_m,2), for any k > 0, where the limits are taken as q → ∞ (for fixed n). Further, we determine whether these, and other related, limits are attained monotonically. Analogous issues are also addressed for the case of infinite F.     

π-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.     

Integral approach to compacton solutions of Boussinesq-like B(m,n) equation with fully nonlinear dispersion

There exists much good work in the area of usual solitons, but there appears little in the field of compacton solutions. Only a few mathematical tools were employed so far. Recently, Yan [Chaos, Solitons & Fractals 14 (2002) 1151] extended the decomposition method to seek compacton solutions of B(m,n) equation u_tt=(uⁿ)_xx+(u^m)_xxxx. In this paper we present a different approach, integral approach, to investigate the compacton solutions of the B(m,n) equation. Not only Yan’s results but also many new compacton solutions of the B(m,n) equation are obtained. Our approach is simple and also suitable for studying compacton solutions of some other equations.     

A note on linearization of actions of finitely semisimple Hopf algebras on local algebras

Let H be a Hopf algebra over a field k and let H A → A, h a → h.a, be an action of H on a commutative local Noetherian kalgebra (A, m). We say that this action is linearizable if there exists a minimal system x₁, …, x_n of generators of the maximal ideal m such that h.x_i ε kx₁ + …+ kx_n for all h ε H and i = 1, …, n. In the paper we prove that the actions from a certain class are linearizable (see Theorem 4), and we indicate some consequences of this fact.