Spectra of principal submatrices of nonnegative matrices

Let A be an n×n nonnegative matrix with the spectrum (λ₁,λ₂,…,λ_n) and let A₁ be an m×m principal submatrix of A with the spectrum (μ₁,μ₂,…,μ_m). In this paper we present some cases where the realizability of (μ₁,μ₂,…,μ_m,ν₁,ν₂,…,ν_s) implies the realizability of (λ₁,λ₂,…,λ_n,ν₁,ν₂,…,ν_s) and consider the question whether this holds in general. In particular, we show that the list

(λ₁,λ₂,…,λ_n,-μ₁,-μ₂,…,-μ_m)     

Graphs with maximum size and lower bounded girth

For integers n≥4 and ν≥n+1, let ex(ν;{C₃,…,C_n}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C₃,…,C_n}-free graphs with order ν and size ex(ν;{C₃,…,C_n}) are called extremal graphs and denoted by EX(ν;{C₃,…,C_n}). We prove that given an integer k≥0, for each n≥2log₂(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν₀(r,g);{C₃,…,C_g−1}).     

Analysis of three graph parameters for random trees

We consider three basic graph parameters, the node‐independence number, the path node‐covering number, and the size of the kernel, and study their distributional behavior for an important class of random tree models, namely the class of simply generated trees, which contains, e.g., binary trees, rooted labeled trees, and planted plane trees, as special instances. We can show for simply generated tree families that the mean and the variance of each of the three parameters under consideration behave for a randomly chosen tree of size n asymptotically ～μn and ～νn, where the constants μ and ν depend on the tree family and the parameter studied. Furthermore we show for all parameters, suitably normalized, convergence in distribution to a Gaussian distributed random variable. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On the degree distribution of the nodes in increasing trees

Simple families of increasing trees can be constructed from simply generated tree families, if one considers for every tree of size n all its increasing labellings, i.e., labellings of the nodes by distinct integers of the set {1,…,n} in such a way that each sequence of labels along any branch starting at the root is increasing. Three such tree families are of particular interest: recursive trees, plane-oriented recursive trees and binary increasing trees. We study the quantity degree of node j in a random tree of size n and give closed formulae for the probability distribution and all factorial moments for those subclass of tree families, which can be constructed via a tree evolution process. Furthermore limiting distribution results of this parameter are given, which completely characterize the phase change behavior depending on the growth of j compared to n.     

On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

Dual properties of subspaces in products of ordinals

Let μ and ν be two ordinals. If X is a subspace of μ×ν, then X is dually scattered of rank?2. If X is a subspace of countable extent of μ×ν, then X is dually discrete.     

A Komlós Theorem for abstract Banach lattices of measurable functions

Consider a Banach function space X(μ) of (classes of) locally integrable functions over a σ-finite measure space (Ω,Σ,μ) with the weak σ-Fatou property. Day and Lennard (2010) [9] proved that the theorem of Komlós on convergence of Cesàro sums in L¹[0,1] holds also in these spaces; i.e. for every bounded sequence n(fn) in X(μ), there exists a subsequence k(fnk) and a function f∈X(μ) such that for any further subsequence j(hj) of k(fnk), the series converges μ-a.e. to f. In this paper we generalize this result to a more general class of Banach spaces of classes of measurable functions — spaces L¹(ν) of integrable functions with respect to a vector measure ν on a δ-ring — and explore to which point the Fatou property and the Komlós property are equivalent. In particular we prove that this always holds for ideals of spaces L¹(ν) with the weak σ-Fatou property, and provide an example of a Banach lattice of measurable functions that is Fatou but do not satisfy the Komlós Theorem.     

The product of two ordinals is hereditarily dually discrete

Let μ and ν be two ordinals. If X is a subspace of μ×ν, then X is dually discrete. This gives a positive answer to a question of Alas, Junqueira and Wilson. By this conclusion and a known conclusion we show that a subspace Y of μ×ν has countable spread if and only if the space Y is hereditarily a Lindelöf D-space.     

Reduced limit for semilinear boundary value problems with measure data

We study boundary value problems for semilinear elliptic equations of the form −Δu+g°u=μ$-\mathrm{\Delta }u+g°u=\mu$ in a smooth bounded domain Ω⊂R^N$\Omega \subset R^N$. Let {_μn}$\{{\mu }_n\}$ and {_νn}$\{{\nu }_n\}$ be sequences of measure in Ω and ∂Ω   respectively. Assume that there exists a solution _un$u_n$ with data (_μn,_νn)$({\mu }_n,{\nu }_n)$, i.e., _un$u_n$ satisfies the equation with μ=_μn$\mu ={\mu }_n$ and has boundary trace _νn${\nu }_n$. Further assume that the sequences of measures converge in a weak sense to μ and ν   respectively while {_un}$\{u_n\}$ converges to u   in L¹(Ω)$L^1(\Omega )$. In general u   is not a solution of the boundary value problem with data (μ,ν)$(\mu ,\nu )$. However there exists a pair of measures (μ^?,ν^?)$({\mu }^{?},{\nu }^{?})$ such that u   is a solution of the boundary value problem with this data. The pair (μ^?,ν^?)$({\mu }^{?},{\nu }^{?})$ is called the reduced limit of the sequence {(_μn,_νn)}$\{({\mu }_n,{\nu }_n)\}$. We investigate the relation between the weak limit and the reduced limit and the dependence of the latter on the sequence. A closely related problem was studied by Marcus and Ponce [3].     

On the distribution of distances between specified nodes in increasing trees

We study the quantity distance between nodejand nodenin a random tree of sizen chosen from a family of increasing trees. For those subclass of increasing tree families, which can be constructed via a tree evolution process, we give closed formulæ for the probability distribution, the expectation and the variance. Furthermore we derive a distributional decomposition of the random variable considered and we show a central limit theorem of this quantity, for arbitrary labels 1≤j<n and n→∞.Such tree models are of particular interest in applications, e.g., the widely used models of recursive trees, plane-oriented recursive trees and binary increasing trees are special instances and are thus covered by our results.     

Products of certain dually discrete spaces

If X and Y are locally compact GO spaces then X×Y is dually discrete. If μ and ν are two ordinals and X is a normal subspace of μ×ν then X is dually discrete.     

On tails of stationary measures on a class of solvable groups

Let G be a subgroup of GL(R,d) and let (Qn,Mn) be a sequence of i.i.d. random variables with values in Rd?G and law μ. Under some natural conditions there exists a unique stationary measure ν on Rd of the process Xn=MnXn−1+Qn. Its tail properties, i.e. behavior of as t tends to infinity, were described some over thirty years ago by H. Kesten, whose results were recently improved by B. de Saporta, Y. Guivarc'h and E. Le Page. In the present paper we study the tail of ν in the situation when the group G₀ is Abelian and Rd is replaced by a more general nilpotent Lie group N. Thus the tail behavior of ν is described for a class of solvable groups of type NA, i.e. being semi-direct extension of a simply connected nilpotent Lie group N by an Abelian group isomorphic to Rd. Then, due to A. Raugi, (N,ν) can be interpreted as the Poisson boundary of (NA,μ).     

Approximate methods for convex minimization problems with series–parallel structure

Consider a problem of minimizing a separable, strictly convex, monotone and differentiable function on a convex polyhedron generated by a system of m linear inequalities. The problem has a series–parallel structure, with the variables divided serially into n disjoint subsets, whose elements are considered in parallel. This special structure is exploited in two algorithms proposed here for the approximate solution of the problem. The first algorithm solves at most min{m, ν − n + 1} subproblems; each subproblem has exactly one equality constraint and at most n variables. The second algorithm solves a dynamically generated sequence of subproblems; each subproblem has at most ν − n + 1 equality constraints, where ν is the total number of variables. To solve these subproblems both algorithms use the authors’ Projected Newton Bracketing method for linearly constrained convex minimization, in conjunction with the steepest descent method. We report the results of numerical experiments for both algorithms.     

Splitting families of sets in ZFC

Miller's 1937 splitting theorem was proved for every finite n>0$n>0$ for all ρ-uniform families of sets in which ρ is infinite. A simple method for proving Miller-type splitting theorems is presented here and an extension of Miller's theorem is proved in ZFC for every cardinal ν for all ρ  -uniform families in which ρ≥_?ω(ν)$\rho \ge {\mathrm{?}}_{\omega }(\nu )$. The main ingredient in the method is an asymptotic infinitary Löwenheim–Skolem theorem for anti-monotone set functions.     

On Asymptotic and Strict Monotonicity of a Sharper Lower Bound for Student’s t Percentiles

Let z _α and t _ν,α denote the upper 100α% points of a standard normal and a Student’s t _ν distributions respectively. It is well-known that for every fixed $0<\alpha <\frac{1}{2}$ and degree of freedom ν, one has t _ν,α ?>?z _α and that t _ν,α monotonically decreases to z _α as ν increases. Recently, Mukhopadhyay (Methodol Comput Appl Probab, 2009) found a new and explicit expression b _ν (?>?1) such that t _ν,α ?>?b _ν z _α for every fixed $0<\alpha <\frac{1}{2}$ and ν. He also showed that b _ν converges to 1 as ν increases. In this short note, we prove three key results: (i) $\log(b_{\nu+1}/b_{\nu})\sim -\frac{1}{4}\nu^{-2}$ for large enough ν, (ii) b _ν strictly decreases as ν increases, and (iii) $b_{\nu}\sim 1+\frac14\nu^{-1}+\frac1{32}\nu^{-2}$ for large enough ν.     

On the nullity and the matching number of unicyclic graphs

Let G be a graph with n vertices and ν(G) be the matching number of G. Let η(G) denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G)=n-2ν(G). Tan and Liu [X. Tan, B. Liu, On the nullity of unicyclic graphs, Linear Alg. Appl. 408 (2005) 212-220] proved that the nullity set of all unicyclic graphs with n vertices is {0,1,…,n-4} and characterized the unicyclic graphs with η(G)=n-4. In this paper, we characterize the unicyclic graphs with η(G)=n-5, and we prove that if G is a unicyclic graph, then η(G) equals , or n-2ν(G)+2. We also give a characterization of these three types of graphs. Furthermore, we determine the unicyclic graphs G with η(G)=0, which answers affirmatively an open problem by Tan and Liu.     

Sur les entiers dont la somme des chiffres est moyenne

The goal of this paper is to study sets of integers with an average sum of digits. More precisely, let g be a fixed integer, s(n) be the sum of the digits of n in basis g. Let f:N→N such that, in any interval [g^ν,g^ν+1[, f(n) is constant and near from (g-1)ν/2. We give an asymptotic for the number of integers n<x such that s(n)=f(n) and we prove that for every irrational α the sequence (αn) is equidistributed mod 1, for n satisfying s(n)=f(n).     

On the number of antipodal bicolored necklaces

Let ν(2n) be the number of antipodal bicolored necklaces with 2n pearls. In this note, we find the first two terms of the asymptotic expansion of ν(2n). As a byproduct of this result, we also show that the sequence (ν(2n)) _n≥1 is non-holonomic, i.e., it satisfies no linear recurrence of a fixed finite order k with polynomial coefficients.     

Une série génératrice des formes paraboliques de Maass

A certain periodic function F_μ,ν(z), an eigenfunction of the Laplacian on the upper half-plane with respect to z depending on some parameters μ, ν, is not automorphic, but the function μ → F_μ,ν(z)−F_μ,ν(−1/0 extends to a larger domain than the function F_μ,ν(z) itself. Consequently, at the poles of this latter function of μ, the coefficients of the polar parts provide non-analytic modular forms: all Maass cusp forms are finite linear combinations of forms obtained in this way, allowing the second parameter ν to vary     

Moment Densities of Super Brownian Motion,and a Harnack Estimate for a Class of X-harmonic Functions

This paper features a comparison inequality for the densities of the moment measures of super-Brownian motion. These densities are defined recursively for each n≥1 in terms of the Poisson and Green’s kernels, hence can be analyzed using the techniques of classical potential theory. When n=1, the moment density is equal to the Poisson kernel, and the comparison is simply the classical inequality of Harnack. For n>1 we find that the constant in the comparison inequality grows at most exponentially with n. We apply this to a class of X-harmonic functions H ^ν of super-Brownian motion, introduced by Dynkin. We show that for a.e. H ^ν in this class, \(H^{\nu }(\mu )<\infty \) for every μ.