The property of maximal eigenvectors of trees

Let T be a tree on n vertices and L(T) be its Laplacian matrix. The eigenvalues and eigenvectors of T are respectively referred to those of L(T). With respect to a given eigenvector Y of T, a vertex u of T is called a characteristic vertex if Y [u] = 0 and there is a vertex w adjacent to u with Y [w] ≠ 0; an edge e = (u, w) of G is called a characteristic edge if Y [u]Y [w] < 0. By 𝒞(T, Y) we denote the characteristic set of T with respect to the vector Y, which is defined as the collection of all characteristic vertices and characteristic edges of T corresponding to Y. Merris shows that 𝒞(T, Y) is fixed for all Fiedler vectors of the tree T. An eigenvector of T is called a k-vector (k ≥ 2) of T if this eigenvector corresponds to an eigenvalue λ _k with λ _k > λ _k?1, where λ₁, λ₂, …, λ _n are the eigenvalues of T arranged in non-decreasing order. A k-vector Y of T is called k-maximal if 𝒞(T, Y) has maximum cardinality among all k-vectors of T. We prove that (1) the characteristic set of T with respect to an arbitrary k-vector is contained in that with respect to any k-maximal vector; and consequently (2) the characteristic sets of T with respect to any two k-maximal vectors are same. Our result may be considered as a generalization of Merris' result as Fiedler vectors are 2-maximal.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

On the distribution of sociable numbers

For a positive integer n, define s(n) as the sum of the proper divisors of n. If s(n)>0, define s₂(n)=s(s(n)), and so on for higher iterates. Sociable numbers are those n with sk(n)=n for some k, the least such k being the order of n. Such numbers have been of interest since antiquity, when order-1 sociables (perfect numbers) and order-2 sociables (amicable numbers) were studied. In this paper we make progress towards the conjecture that the sociable numbers have asymptotic density 0. We show that the number of sociable numbers in [1,x], whose cycle contains at most k numbers greater than x, is o(x) for each fixed k. In particular, the number of sociable numbers whose cycle is contained entirely in [1,x] is o(x), as is the number of sociable numbers in [1,x] with order at most k. We also prove that but for a set of sociable numbers of asymptotic density 0, all sociable numbers are contained within the set of odd abundant numbers, which has asymptotic density about 1/500.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

On the eigenvalues of the fredholm operator

We prove that if ω(t, x, K ₂ ^(m) )?c(x)ω(t) for allxε[a, b] andx ε [0,b-a] wherec ∈L ¹(a, b) and ω is a modulus of continuity, then λ _n =O(n ^?m-1/2ω(1/n)) and this estimate is unimprovable.     

The second largest eigenvalue of a tree

Denote by λ₂(T) the second largest eigenvalue of a tree T. An easy algorithm is given to decide whether λ₂(T)?λ for a given number λ, and a structure theorem for trees withλ₂(T)?λ is proved. Also, it is shown that a tree T with n vertices has $\text{λ}{}_2\text{(T)?lsqb}\text{(n?3)}\text{2}\text{rsqb}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$; this bound is best possible for odd n.     

Identification of the unknown diffusion coefficient in a linear parabolic equation by the semigroup approach

In this article, we study the semigroup approach for the mathematical analysis of the inverse coefficient problems of identifying the unknown coefficient k(x) in the linear parabolic equation ut(x,t)=(k(x)uxx(x,t)), with Dirichlet boundary conditions u(0,t)=ψ₀, u(1,t)=ψ₁. Main goal of this study is to investigate the distinguishability of the input-output mappings Φ[⋅]:K→C¹[0,T], Ψ[⋅]:K→C¹[0,T] via semigroup theory. In this paper, we show that if the null space of the semigroup T(t) consists of only zero function, then the input-output mappings Φ[⋅] and Ψ[⋅] have the distinguishability property. Moreover, the values k(0) and k(1) of the unknown diffusion coefficient k(x) at x=0 and x=1, respectively, can be determined explicitly by making use of measured output data (boundary observations) f(t):=k(0)ux(0,t) or/and h(t):=k(1)ux(1,t). In addition to these, the values k^′(0) and k^′(1) of the unknown coefficient k(x) at x=0 and x=1, respectively, are also determined via the input data. Furthermore, it is shown that measured output dataf(t) and h(t) can be determined analytically, by an integral representation. Hence the input-output mappings Φ[⋅]:K→C¹[0,T], Ψ[⋅]:K→C¹[0,T] are given explicitly in terms of the semigroup. Finally by using all these results, we construct the local representations of the unknown coefficient k(x) at the end points x=0 and x=1.     

A note on the kernels of higher derivations

Let k ? k′ be a field extension. We give relations between the kernels of higher derivations on k[X] and k′[X], where k[X]:= k[x ₁,…, x _n ] denotes the polynomial ring in n variables over the field k. More precisely, let D = {D _n } _n=0 ^∞ a higher k-derivation on k[X] and D′ = {D′ _n } _n=0 ^∞ a higher k′-derivation on k′[X] such that D′ _m (x _i ) = D _m (x _i ) for all m ? 0 and i = 1, 2,…, n. Then (1) k[X] ^D = k if and only if k′[X] ^D′ = k′; (2) k[X] ^D is a finitely generated k-algebra if and only if k′[X] ^D′ is a finitely generated k′-algebra. Furthermore, we also show that the kernel k[X] ^D of a higher derivation D of k[X] can be generated by a set of closed polynomials.     

Perturbations with several independent parameters

In this paper we discuss the problem of determining a T-periodic solution $\text{x}{}^1\text{(·, λ)}$ of the differential equation x = A(t)x + f(t, x, λ) + b(t), where the perturbation parameter λ is a vector in a parameter-space R^k. The customary approach assumes that λ = λ(?), ??R. One then establishes the existence of an ?₀ > 0 such that the differential equation has a T-periodic solution $\text{x}{}^1\text{(·, λ(?))}$ for all ? satisfying 0 < ? < ?₀. More specifically it is usually assumed that λ(?) has the form λ(?) = ?λ₀ where λ₀ is a fixed vector in R^k. This means that attention is confined in the perturbation procedure to examining the dependence of $\text{x}{}^1\text{(·, λ)}$ on λ as λ varies along a line segment terminating at the origin in the parameter-space R^k. The results established here generalize this previous work by allowing one to study the dependence of $\text{x}{}^1\text{(·, λ)}$ on λ as λ varies through a “conical-horn” whose vertex rests at the origin in R^k. In the process an implicit-function formula is developed which is of some interest in its own right.     

A method of multipliers for mathematical programming problems with equality and inequality constraints

This paper deals with the numerical solution of the general mathematical programming problem of minimizing a scalar functionf(x) subject to the vector constraints φ(x)=0 and ψ(x)≥0. The approach used is an extension of the Hestenes method of multipliers, which deals with the equality constraints only. The above problem is replaced by a sequence of problems of minimizing the augmented penalty function Ω(x, λ, μ,k)=f(x)+λ ^T φ(x)+kφ ^T (x)φ(x) ?μ ^T \(\tilde \psi \) (x)+k \(\tilde \psi \) ^T (x) \(\tilde \psi \) (x). The vectors λ and μ, μ ≥ 0, are respectively the Lagrange multipliers for φ(x) and \(\tilde \psi \) (x), and the elements of \(\tilde \psi \) (x) are defined by \(\tilde \psi \) _(j)(x)=min[ψ_(j)(x), (1/2k) μ_(j)]. The scalark>0 is the penalty constant, held fixed throughout the algorithm. Rules are given for updating the multipliers for each minimization cycle. Justification is given for trusting that the sequence of minimizing points will converge to the solution point of the original problem.     

On set systems with a threshold property

For n,k and t such that 1<t<k<n, a set F of subsets of [n] has the (k,t)-threshold property if every k-subset of [n] contains at least t sets from F and every (k-1)-subset of [n] contains less than t sets from F. The minimal number of sets in a set system with this property is denoted by m(n,k,t). In this paper we determine m(n,4,3)exactly for n sufficiently large, and we show that m(n,k,2) is asymptotically equal to the generalized Turán number T_k-1(n,k,2).     

Estimates for interval probabilities of the sums of random variables with locally subexponential distributions

Let {_i} _i=1 be a sequence of independent identically distributed nonnegative random variables, S _n = ξ₁ + ? +ξ_n. Let Δ = (0, T] and x + Δ = (x, x + T]. We study the ratios of the probabilities P(S _n ε x + Δ)/P(ξ ₁ ε x + Δ) for all n and x. The estimates uniform in x for these ratios are known for the so-called Δ-subexponential distributions. Here we improve these estimates for two subclasses of Δ-subexponential distributions; one of them is a generalization of the well-known class LC to the case of the interval (0, T] with an arbitrary T ≤ ∞. Also, a characterization of the class LC is given.     

On two-sided and asymptotic estimates for the norms of embedding operators of into L q (dμ)

Explicit upper and lower estimates are given for the norms of the operators of embedding of , n ∈ ?, in L _q (dµ), 0 < q < ∞. Conditions on the measure µ are obtained under which the ratio of the above estimates tends to 1 as n → ∞, and asymptotic formulas are presented for these norms in regular cases. As a corollary, an asymptotic formula (as n → ∞) is established for the minimum eigenvalues λ_{1, n, β} , β > 0, of the boundary value problems (?d ²/dx ²) ⁿ u(x) = λ|x| ^β?1, x ∈ (?1, 1), u ^(k)(±1) = 0, k ∈ {0, 1, ..., n ? 1}.     

Extremal problems on detectable colorings of trees

Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a₁,a₂,…,a_k), where a_i is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let D_T(n) be the maximum detection number among all trees of order n and d_T(n) the minimum detection number among all trees of order n. The numbers D_T(n) and d_T(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if d_T(n)?k?D_T(n).     

Hitting time of a moving boundary for a diffusion

We obtain asymptotic estimates for the quantity r = log P[T_f[rang]t] as t → ∞ where T_f = inf\s{s : |X(s)|[rang]f(s)\s} and X is a real diffusion in natural scale with generator a(x) d²(·)/dx² and the ‘boundary’ f(s) is an increasing function. We impose regular variation on a and f and the result is expressed as r = ∫^t₀ λ₁ (f(s) ds(1 + o(1)) where λ₁(f) is the smallest eigenvalue for the process killed at ±f.     

The Hilbert Scheme Parameterizing Finite Length Subschemes of the Line with Support at the Origin

We introduce symmetrizing operators of the polynomial ring A[x] in the variable x over a ring A. When A is an algebra over a field k these operators are used to characterize the monic polynomials F(x) of degree n in A[x] such that A _k k[x]_(x)/(F(x)) is a free A-module of rank n. We use the characterization to determine the Hilbert scheme parameterizing subschemes of length n of k[x]_(x).     

Zeros of analytic functions and norms of inverse matrices

Letk _n be the smallest constant such that for anyn-dimensional normed spaceX and any invertible linear operatorT ∈L(X) we have $|\det (T)| \cdot ||T^{ - 1} || \le k_n |||T|^{n - 1} $ . LetA ₊ be the Banach space of all analytic functionsf(z)=Σ _k≥0 a _kz^k on the unit diskD with absolutely convergent Taylor series, and let ‖f‖A ₊=σ _k≥0 |ακ|; define ? _n on $\overline D ^n $ by $ \begin{array}{l} \varphi _n \left( {\lambda _1 ,...,\lambda _n } \right) \\ = inf\left\{ {\left\| f \right\|_{A + } - \left| {f\left( 0 \right)} \right|; f\left( z \right) = g\left( z \right)\prod\limits_{i = 1}^n {\left( {\lambda _1 - z} \right), } g \in A_ + , g\left( 0 \right) = 1 } \right\} \\ \end{array} $ . We show thatk _n=sup {? _n(λ₁,…, λ _n ); (λ₁,…, λ _n )∈ $\overline D ^n $ }. Moreover, ifS is the left shift operator on the space ?∞:S(x ₀,x ₁, …,x _p, …)=(x ₁,…,x _p,…) and if J_n(S) denotes the set of allS-invariantn-dimensional subspaces of ?∞ on whichS is invertible, we have $k_n = \sup \{ |\det (S|_E )|||(S|_E )^{ - 1} ||E \in J_n (S)\} $ . J. J. Schäffer (1970) proved thatk _n≤√en and conjectured thatk _n=2, forn≥2. In factk ₃>2 and using the preceding results, we show that, up to a logarithmic factor,k _n is of the order of √n whenn→+∞.     

The Harmonious Chromatic Number of Deep and Wide Complete n- ary Trees

The harmonious chromatic number of a graph G is the least number of colors which can be used to color V(G) such that adjacent vertices are colored differently and no two edges have the same color pair on their vertices. Unsolved Problem 17.5 of Graph Coloring Problems by Jensen and Toft asks for the harmonious chromatic number of T_m,n the complete n-ary tree on m levels. Let q be the number of edged of T_m,n and k be the smallest positive integer such that the binomial coefficient C(k, 2) ≥ q. We show that for all sufficiently large m, n, the harmonious chromatic number of T_m,n is at most k + 1, and that many such T_m,n have harmonious chromatic number k.     

On theT-ideal generated by a standard identity

We determine the structure of the ideal of identities of degreen +1 in theT-ideals T_o(s_n(x₁,…,x_n)) and T_o(u_n(x₁,…,x_n)), wheres _n is the standard identity and u_n the unitary identity of degreen.     

The periods of the sequences generated by some symmetric shift registers

E_k(x₂,…, x_n) is defined by E_k(a₂,…, a_n) = 1 if and only if ∑_i=2ⁿa_i = k. We determine the periods of sequences generated by the shift registers with the feedback functions x₁ + E_k(x₂,…, x_n) and x₁ + E_k(x₂,…, x_n) + E_k+1(x₂,…, x_n) over the field GF(2).