Enumeration of sequences of given specification according to rises,falls and maxima

Letn = (a₁.a₂ … a_N) denote a sequence of integers a_i={1.2.…n}. A rise is a part a_i.a_i+1 with a_i <a_i+1: a fall is a pair with a_ia_i+1: a level is a pair with a_i = a_i+1. A maximum is a triple a_i-1.a_ia_i+1 with a_i-1?a_i.a_i?a_i+1. If e_i is the number of a_j?n witha_j = i, then [e₁…e_n] is called the specification of n. In addition, a conventional rise is counted to the left of a₁ and a conventional fall to the right of a_N: ifa₁?a₂, then a₁ is counted as a conventional maximum, similarly if a_N-1 ? a_N thena_N is a conventional maximum. Simon Newcomb's problem is to find the number of sequences n with given specification and r rises; the refined problem of determining the number of sequences of given specification with r rises and s falls has also been solved recently. The present paper is concerned with the problem of finding the number of sequences of given specification with r rises, s falls. λ levels and λ maxima. A generating function for this enumerant is obtained as the quotient of two continuants. In certain special cases this result simplifies considerably.     

Quasi-monotone mappings on θn-continua

A continuous function f from a continuum X onto a continuum Y is quasi-monotone if, for every subcontinuum M of Y with nonvoid interior, f^-1(M) has a finite number of components each of which is mapped onto M by f. A θ_n-continuum is one that no subcontinuum separates into more than n components. It is known that if f is quasi-monotone and X is a θ₁-continuum, then Y is a θ₁-continuum or a θ₂-continuum that is irreducible between two points. Examples are given to show that this cannot be generalized to a θ_n-continuum and n + 1 points for any n >1, but it is proved that if f is quasi-monotone and X is a θ_n-continuum, then Y is a θ_n-continuum or a θ_n+1-continuum that is the union of n + 2 continua H,S₁,S₂,…,S_n+1, whe for each i, S_i is the closure of a component of Y H, S_i is irreducible from some point P_i to H, and H is irreducible about its boundary. Some theorems and examples are given concerning the preservation of decomposition elements by a quasi-monotone map defined on a θ_n-continuum that admits a monotone, upper-semicontinuous decomposition onto a finite graph.     

The Erd?s-Ginzburg-Ziv theorem for dihedral groups

Let n≥23 be an integer and let D_2n be the dihedral group of order 2n. It is proved that, if g₁,g₂,…,g_3n is a sequence of 3n elements in D_2n, then there exist 2n distinct indices i₁,i₂,…,i_2n such that g_i1g_i2?g_i2n=1. This result is a sharpening of the famous Erd?s-Ginzburg-Ziv theorem for G=D_2n.     

Homology of certain algebras defined by graphs

Let K(G) for a finite graph G with vertices v₁,...,v_n denote the K-algebra with generators X₁,...,X_n and defining relations X_iX_j=X_jX_i if and only if v_i is not connected to v_j by an edge in G. We describe centralizers of monomials, show that the centralizer of a monomial is again a graph algebra, prove a unique factorization theorem for factorizations of monomials into commuting factors, compute the homology of K(G), and show that K(G) is the homology ring of a certain loop space. We also construct a K(π, 1) explicitly where π is the group with generators X₁,...,X_n and defining relations X_iX_j=X_jX_i if and only if v_i is not connected to v_j by an edge in G.     

Categoricity results for L∞κ

Let V denote a variety of algebras in a countable language. An algebra is said to be L_∞κ-free if it is L_∞κ-equivalent to a (V-) free algebra. If every L_∞ω1-free algebra of cardinality ω₁ is free, then for all infinite cardinals κ every L_∞κ-free algebra of cardinality κ is free. Further, assuming suitable set-theoretic hypotheses, if there is a non-free L_∞ω1-free algebra of cardinality ω₁, then for a proper class of cardinals κ there are non-free L_∞κ-free algebras of cardinality κ. The varieties in which the class of free algebras are definable by a sentence in L_ω1ω are characterized as the weak Schreier varieties in which every L_∞ω-free algebra of cardinality ω₁ is free. A weak Schreier variety is one in which every L_∞ω-elementary substructure of a free algebra is free. In fact, assuming suitable set-theortic hypotheses, for weak Schreier varieties the class of free algebras is definable in L_∞∞ iff it is definable in L_ω1ω. Varieties in uncountable languages are also considered.     

On indecomposable subcones

Let K₁,K₂ be cones. We say that K₁ is a subcone of K₂ if ExtK₁?ExtK₂. Furthermore, if K₁≠K₂, K₁ is called a proper subcone; if dimK₁=dimK₂, K₁ is called a non-degenerate subcone. We first prove that every n-dimensional indecomposable cone, n?3, contains a non-degenerate indecomposable subcone which has no more than 2n-2 extremals. Then we construct for each n?3 an n-dimensional indecomposable cone with exactly 2n-2 extremals such that each of its proper non-degenerate subcones is decomposable.     

Order of approximation by electrostatic fields due to electrons

LetD be a Jordan domain in the complex plane andA _q (D) the Bers space with norm ∥ ∥ _q . IfD is the unit disk, it is known that ∥S _n 0∥₂≥π/18, whereS _n =∑ _k=1 ⁿ l/(z?z _nk ) withz _nk ∈?D, so that approximation in ∥ ∥ _q ,q<-2, is not possible. In this paper, we give an order of estimate of ∥f?S _n ∥ _q for 2<q<∞ when ?D is a sufficiently smooth Jordan curve, and prove that this order of approximation is in general best possible.     

On Rado's Boundedness Conjecture

We prove that Rado's Boundedness Conjecture from Richard Rado's 1933 famous dissertation Studien zur Kombinatorik is true if it is true for homogeneous equations. We then prove the first nontrivial case of Rado's Boundedness Conjecture: if a₁,a₂, and a₃ are integers, and if for every 24-coloring of the positive integers (or even the nonzero rational numbers) there is a monochromatic solution to the equation a₁x₁+a₂x₂+a₃x₃=0, then for every finite coloring of the positive integers there is a monochromatic solution to a₁x₁+a₂x₂+a₃x₃=0.     

Continuity of invariant measures for families of maps

Let {τ_r} be the family of maps from [0,1] into [0,1] with properties similar to those of τ_r(x) = rx(1 ? x), 0 ≤ r ≤ 4. The limiting behaviour of orbits {τ_r^j(x)}_j^∞ = 1 is a complicated and discontinuous function of the parameter r. The stochastic approximation to the difference equation x_{n + 1} = τ_r(x_n), x_{n + 1} = τ_r(x_n) + W, where W is a fixed random variable independent of r and x_n, is considered. It is shown that this Markov process admits a unique absolutely continuous invariant measure μ_r and, furthermore, that the map r → μ_r is continuous. Such a result is important in applications, since slight changes in the shape of τ_r no longer cause discontinuous consequences in the limiting behaviour of the system.     

Weighted rational approximation in the complex plane

Given a triple (G, W, γ) of an open bounded set G in the complex plane, a weight function W(z) which is analytic and different from zero in G, and a number γ with 0 ≤ γ ≤ 1, we consider the problem of locally uniform rational approximation of any function ƒ(z), which is analytic in G, by weighted rational functions W^m_i+n_i(z)R_mi, n_i(z)_{i = 0}^∞, where R_mi, n_i(z) = P_mi(z)/Q_ni(z) with deg P_mi ≤ m_i and deg Q_ni ≤ n_i for all i ≥ 0 and where m_i + n_i → ∞ as i → ∞ such that lim m_i/[m_i + n_i] = γ. Our main result is a necessary and sufficient condition for such an approximation to be valid. Applications of the result to various classical weights are also included.     

An estimator for the mean of an exponential distribution with random right-censoring

Let (Y₁, Z₁),…,(Y_N, Z_N) be i.i.d. pairs of independent random variables such that Y_i is exponentially distributed with unknown mean 1/λ and Z_i has an unknown distribution function F. Let X_i ≔ min(Y_i, Z_i). Under certain assumptions on F an estimator T_N(X₁,…,X_N) for 1/λ is constructed which is consistent and asymptotically normal.     

An addition theorem for finite Abelian groups

If g₁, g₂, …, g_2n?1 is a sequence of 2n ? 1 elements in an Abelian group G of order n, it is known that there are n distinct indices i₁, i₂, …, i_n such that 0 = g_i1 + g_i2 + ? + g_in. In this paper a suitably general condition on the sequence is given which insures that every element g in G has a representation g = g_i1 + g_i2 + ? + g_in as the sum of n terms of the sequence.     

Hyperamarts: Conditions for regularity of continuous parameter processes

The regularity of trajectories of continuous parameter process (X_t)_t∈R+ in terms of the convergence of sequence E(X_Tn) for monotone sequences (T_n) of stopping times is investigated. The following result for the discrete parameter case generalizes the convergence theorems for closed martingales: For an adapted sequence (X_n)_1≤n≤∞ of integrable random variables, lim X_n exists and is equal to X_∞ and (X_T) is uniformly integrable over the set of all extended stopping times T, if and only if lim E(X_Tn) = E(X_∞) for every increasing sequence (T_n) of extended simple stopping times converging to ∞. By applying these discrete parameter theorems, convergence theorems about continuous parameter processes are obtained. For example, it is shown that a progressive, optionally separable process (X_t)_t∈R+ with E{X_T} < ∞ for every bounded stopping time T is right continuous if lim E(X_Tn) = E(X_T) for every bounded stopping time T and every descending sequence (T_n) of bounded stopping times converging to T. Also, Riesz decomposition of a hyperamart is obtained.     

Properties of Regular Uniform k—Stratified Graphs

A regular graph G = (V, E) is a k-stratified graph if V is partitioned into V₁, V₂, …, V_k subsets called strata. The stratification splits the degree d_v ∀v ϵ V into k-integers d_v1, d_v2, …, d_vk each one corresponding to a stratum. If d_v1 = d_v2 = … = d_vk ∀v ϵ V then G is called regular uniform k-stratified, RU^k_s(n, d) where n is the cardinality of the vertex set in each stratum and d is the degree of every vertex in each stratum. For every k, the class RU^k_s(n, d) has a unique graph generator class RU^l_s(n, d) derived by decomposition of graphs in RU^k_s(n, d). We investigate the minimization of the cardinality of V, the colorability, vertex coloring and the diameter of the graphs in the class. We also deal with complexity questions concerning RU^k_s(n, d). Some well-known computer network models such as barrel shifters and hypercubes are shown to belong in RU^k_s(n, d).     

Independence numbers of graphs-an extension of the Koenig-Egervary theorem

Let G be an arbitrary finite, undirected graph with no loops nor multiple edges. In this paper the inequality β₀?n ? β₁ is investigated where β₀ is the independence number of G, n is the number of vertices, and β₁ is the cardinality of a maximum edge matching. The class of graphs for which equality holds is characterized. A polynomially-bounded algorithm is given which tests an arbitrary graph G for equality, and computes a maximum independent set of vertices when equality holds. Equality is “prevented” by the existence of a blossom-pair-a subgraph generated by a certain subset m_i of edges from a maximum edge matching M for G. It is shown that β₀ = n ?β₁?|R| where R is a minimum set oof representatives of the family {m_i} of blossom pair-generating subsets of M. Finally, apolynomially-bonded algorithm is given which partitions an arbitrary graph G into subgraphs G₀, G₁,…, G_q such that $\text{β}{}_0\text{(G) =}\text{∑}\text{i=0}\text{q}\text{β}{}_0\text{(G}{}_{\mathrm{i}}\text{)}$. Moreover, if arbitrary maximum independent subsets of vertices S₁, S₂,…, S_q are known, then a polynomially-bounded algorithm computes a maximum independent set S₀ for G₀ such that S=∪{S_i; i=0, 1,hellip;,q} is a maximum independent subset for G.     

The n-lie property of the Jacobian as a condition for complete integrability

We prove that an associative commutative algebra U with derivations D ₁, ..., D _n ε DerU is an n-Lie algebra with respect to the n-multiplication D ₁ ^ ? ^ D _n if the system {D ₁, ..., D _n } is in involution. In the case of pairwise commuting derivations this fact was established by V. T. Filippov. One more formulation of the Frobenius condition for complete integrability is obtained in terms of n-Lie multiplications. A differential system {D ₁, ..., D _n } of rank n on a manifold M ^m is in involution if and only if the space of smooth functions on M is an n-Lie algebra with respect to the Jacobian Det(D _i u _j ).     

Existence of Tchebycheff extensions

Given a Tchebycheff System {y_o ··· y_n} defined on an interval I, it is proved that there exists a function y_n+1, such that the system {y_o ··· y_n, y_n+1} is a Tchebycheff System on I. A function such as y_n+1 is called a Tchebycheff extension of the system {y_i}ⁿ_{(i = 0)}.     

Atomic decomposition and boundedness criterion of operators on multi-parameter hardy spaces of homogeneous type

The main purpose of this paper is to derive a new ( p, q)-atomic decomposition on the multi-parameter Hardy space Hp (X1 × X2 ) for 0 p0 p ≤ 1 for some p0 and all 1 q ∞, where X1 × X2 is the product of two spaces of homogeneous type in the sense of Coifman and Weiss. This decomposition converges in both Lq (X1 × X2 ) (for 1 q ∞) and Hardy space Hp (X1 × X2 ) (for 0 p ≤ 1). As an application, we prove that an operator T1, which is bounded on Lq (X1 × X2 ) for some 1 q ∞, is bounded from Hp (X1 × X2 ) to Lp (X1 × X2 ) if and only if T is bounded uniformly on all (p, q)-product atoms in Lp (X1 × X2 ). The similar boundedness criterion from Hp (X1 × X2 ) to Hp (X1 × X2 ) is also obtained.     

Stop rule and supremum expectations of i.i.d. random variables: A complete comparison by conjugate duality

A complete comparison is made between the value V(X₁,…, X_n) = sup{EX_t: t is a stop rule for X₁,…,X_n} and E(max_{j ≤ n}X_j) for all uniformly bounded sequences of i.i.d. random variables X₁, …, X_n. Specifically, the set of ordered pairs {(x,y): x = V(X₁, …, X_n) and y = E(max_j≤nX_j) for some i.i.d.r.v.'s X₁,…, X_n taking values in [0, 1]} is precisely the set {(x, y): x≤y≤Γ_n(x); 0 ≤x≤1}, where the upper boundary function Γ_n is given in terms of recursively defined functions. The result yields families of inequalities for the “prophet” problem, relating the motal's value of a game V(X₁, …, X_n) to the prophet's value of the game E(max_j≤nX_j). The proofs utilize conjugate duality theory, probabilistic convexity arguments, and functional equation analysis. Asymptotic analysis of the “prophet” regions and inequalities is also given.     

Accretion centers: A generalization of branch weight centroids

An ordered n-tuple (v_i1,v_i2,…,v_in) is called a sequential labelling of graph G if {v_i1,v_i2,…,v_in} = V(G) and the subgraph induced by {v_i1,v_i2,…, v_ij} is connected for 1≤j≤n. Let σ(v;G) denote the number of sequential labellings of G with v_i1=v. Vertex v is defined to be an accretion center of G if σ is maximized at v. This is shown to generalize the concept of a branch weight centroid of a tree since a vertex in a tree is an accretion center if and only if it is a centroid vertex. It is not, however, a generalization of the concept of a median since for a general graph an accretion center is not necessarily a vertex of minimum distance. A method for computing σ(v;G) based upon edge contractions is described.