Some results on Hu's conjecture concerning binary trees

Given n weights, w₁, w₂,…, w_n, such that 0?w₁?w₂???w₁, we examine a property of permutation π¹, where π¹=(w₁, w_n, w₂, w_n?1,…), concerning alphabetical binary trees.For each permutation π of these n weights, there is an optimal alphabetical binary tree corresponding to π, we denote it's cost by V(π). There is also an optimal almost uniform alphabetical binary tree, corresponding to π, we denote it's cost by V_u(π).This paper asserts that V_u(π¹)?V_u(π)?V(π) for all π. This is a preliminary result concerning the conjecture of T.C. Hu. Hu's conjecture is V(π¹)?V(π) for all π.     

Representation of group elements as subsequence sums

Let G be a finite (additive written) abelian group of order n. Let w₁,…,w_n be integers coprime to n such that w₁+w₂+?+w_n≡0 (mod n). Let I be a set of cardinality 2n-1 and let ξ={x_i:i∈I} be a sequence of elements of G. Suppose that for every subgroup H of G and every a∈G, ξ contains at most terms in a+H.Then, for every y∈G, there is a subsequence {y₁,…,y_n} of ξ such that y=w₁y₁+?+w_ny_n.Our result implies some known generalizations of the Erd?s-Ginzburg-Ziv Theorem.     

Intriguing Sets of Points of Q(2n, 2) \Q +(2n ? 1, 2)

Intriguing sets of vertices have been studied for several classes of strongly regular graphs. In the present paper, we study intriguing sets for the graphs Γ _n , n ≥ 2, which are defined as follows. Suppose Q(2n, 2), n?≥ 2, is a nonsingular parabolic quadric of PG(2n, 2) and Q ⁺(2n ? 1, 2) is a nonsingular hyperbolic quadric obtained by intersecting Q(2n, 2) with a suitable nontangent hyperplane. Then the collinearity relation of Q(2n, 2) defines a strongly regular graph Γ _n on the set Q(2n, 2) \ Q ⁺(2n ? 1, 2). We describe some classes of intriguing sets of Γ _n and classify all intriguing sets of Γ₂ and Γ₃.     

Forbidden (0,1)-Vectors in Hyperplanes of ℝ n : The Restricted Case

In this paper we continue our investigation on “Extremal problems under dimension constraint” introduced in [2]. Let E(n, k) be the set of (0,1)-vectors in ? ⁿ with k one's. Given 1 ≤ m, w ≤ n let X ? E(n, m) satisfy span (X) ∩ E(n, w) = ?. How big can |X| be? This is the main problem studied in this paper. We solve this problem for all parameters 1 ≤ m, w ≤ n and n > n ₀(m, w).     

Probabilistic analysis of solving the assignment problem for the traveling salesman problem

This paper deals with probabilistic analysis of optimal solutions of the asymmetric traveling salesman problem. The exact distribution for the number of required next-best solutions of the assignment problem with random data in order to find an optimal tour is given. For every n-city asymmetric problem, there exists an algorithm such that (i) with probability 1 ? s, s?(0,1) the algorithm produces an optimal tour, (ii) it runs in time $\text{O}\text{(}\text{n}{}^4\text{3}\text{)}$, and (iii) it requires less than w((w + n ? 1)$\text{log}\text{(w + n ? 1) + w + 1) +}\text{1}\text{6}\text{w(n}{}^3\text{+ 3n}{}^2\text{+ 2n ? 6)}$ computational steps, where w = log(s)/log(1 ? E_n); E_n ?(0,1) is given by a simple mathematical formula. Additionally, the polynomial of (iii) gives the exact (deterministic) execution time to find w =1 ,2…. next-best solutions of the assignment problem.     

CR deformations for rational homogeneous surface singularities

In this paper, we will present a CR-construction of the versal deformations of the singularitiesV _n ? ?²/? _n ,n ∈ {2,3,4,?} defined by the immersions of ?² into ? ⁿ⁺¹ X ⁿ : (z, w) → (z ⁿ ,z ^n?1 w, ?,zw ^n?1 ,w ⁿ )     

On a geometrical method of construction of maximal t-linearly independent sets

The problem of constructing a maximal t-linearly independent set in V(r; s) (called a maximal L_t(r, s)-set in this paper) is a very important one (called a packing problem) concerning a fractional factorial design and an error correcting code where V(r; s) is an r-dimensional vector space over a Galois field GF(s) and s is a prime or a prime power. But it is very difficult to solve it and attempts made by several research workers have been successful only in special cases.In this paper, we introduce the concept of a {Σ_α=1^kw_α, m; t, s}-min · hyper with weight (w₁, w₂,…, w_k) and using this concept and the structure of a finite projective geometry PG(n ? 1, s), we shall give a geometrical method of constructing a maximal L_t(t + r, s)-set with length t + r + n for any integers r, n, and s such that n ? 3, n ? 1 ? r₀ ? n + s ? 2 and r₁ ? 1, where r = (r₁ + 1)v_n?1 ? r₀ and $\text{v}{}_{\mathrm{n}}\text{=}\text{(s}{}^{\mathrm{n}}\text{? 1)}\text{(s ? 1)}$.     

Complexity and structure of near-minimal contact circuits for elementary symmetric functions

The paper studies the problem of the synthesis of contact circuits for elementary symmetric functions. The structure of minimal contact circuits realizing elementary symmetric functions is established and the estimates of the complexity of the obtained circuits, which are accurate to within an additive constant, are determined. It is proved that, for substantially large n, the complexity of an elementary symmetric function of n variables with the working number w satisfies the relation L(s _n ^w ) = (2w + 1)n ? B _w , whereB _w is a nonnegative constant.     

On the simplex method and a class of linear complementary problems

We consider the linear complementarity problem of finding vectors w?Rⁿ, z?Rⁿ satisfying w ? Mz = q, w ? 0, z ? 0, w^Tz = 0. We show that if the off diagonal elements of M are nonpositive, then the above problem is solved by applying the simplex method to the problem Minimize z₀ subject to w ? Mz ? e_nz₀ = q, (z₀, w, z) ? 0, where e_n is a column vector of 1's. In fact the sequence of basic feasible solutions obtained by the simplex method and by Lemke's algorithm are the same. We also obtain necessary and sufficient conditions for the problem to have solutions for all q.     

A note on the continuous mixing set

The continuous mixing set is , where w₁,…,w_n>0 and f₁,…,f_n∈ℜ. Let m=|{w₁,…,w_n}|. We show that when w₁|?|w_n, optimization over S can be performed in time O(n^m+1), and in time O(nlogn) when w₁=?=w_n=1.     

The asymptotic distribution of weighted empirical distribution functions

Let G_n denote the empirical distribution based on n independent uniform (0, 1) random variables. The asymptotic distribution of the supremum of weighted discrepancies between G_n(u) and u of the forms 6w_v(u)D_n(u)6 and 6w_v(G_n(u))D_n(u)6, where D_n(u) = G_n(u)?u, w_v(u) = (u(1?u))^?1+v and 0 ? v < $\text{1}\text{2}$ is obtained. Goodness-of-fit tests based on these statistics are shown to be asymptotically sensitive only in the extreme tails of a distribution, which is exactly where such statistics that use a weight function w_v with $\text{1}\text{2}$ ? v ? 1 are insensitive. For this reason weighted discrepancies which use the weight function w_v with 0 ? v < $\text{1}\text{2}$ are potentially applicable in the construction of confidence contours for the extreme tails of a distribution.     

Successions in Words and Compositions

We consider words over the alphabet [k] = {1, 2, . . . , k}, k ?? 2. For a fixed nonnegative integer p, a p-succession in a word w ₁ w ₂ . . . w _n consists of two consecutive letters of the form (w _i , w _i ?+ p), i = 1, 2, . . . , n ? 1. We analyze words with respect to a given number of contained p-successions. First we find the mean and variance of the number of p-successions. We then determine the distribution of the number of p-successions in words of length n as n (and possibly k) tends to infinity; a simple instance of a phase transition (Gaussian-Poisson-degenerate) is encountered. Finally, we also investigate successions in compositions of integers.     

Integers with dense divisors 2

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are t-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?t. Let D(x,t) be the number of positive integers not exceeding x whose divisors are t-dense. We show that for x?3, and , we have , where , and d(w) is a continuous function which satisfies d(w)?1/w for w?1. We also consider other counting functions closely related to D(x,t).     

The Ramsey numbers of paths versus wheels

For two given graphs G₁ and G₂, the Ramsey number R(G₁,G₂) is the smallest integer n such that for any graph G of order n, either G contains G₁ or the complement of G contains G₂. Let P_n denote a path of order n and W_m a wheel of order m+1. In this paper, we show that R(P_n,W_m)=2n-1 for m even and n?m-1?3 and R(P_n,W_m)=3n-2 for m odd and n?m-1?2.     

Fractal interpolation on the Sierpinski Gasket

We prove for the Sierpinski Gasket (SG) an analogue of the fractal interpolation theorem of Barnsley. Let V₀={p₁,p₂,p₃} be the set of vertices of SG and the three contractions of the plane, of which the SG is the attractor. Fix a number n and consider the iterations uw=uw₁uw₂?uwn for any sequence w=(w₁,w₂,…,wn)∈n{1,2,3}. The union of the images of V₀ under these iterations is the set of nth stage vertices Vn of SG. Let F:Vn→R be any function. Given any numbers αw(w∈n{1,2,3}) with 0<|αw|<1, there exists a unique continuous extension of F, such that

f(uw(x))=αwf(x)+hw(x)     

Rational approximation with varying weights I

We investigate two problems concerning uniform approximation by weighted rationals {w ⁿr_n～ _∞ ⁿ⁼¹ }, wherer _n=p_n Namely, forw(x):=e ^x we prove that uniform convergence to 1 ofw ⁿr_n is not possible on any interval [0,a] witha>2π. Forw(x):=x ^?, ?>1, we show that uniform convergence to 1 ofw ⁿr_n is not possible on any interval [b, 1] withb<tan ⁴(π(??1)/4?). (The latter result can be interpreted as a rational analogue of results concerning “incomplete polynomials.”) More generally, for α≥0, β≥0, α+β>0, we investigate forw(x)=e ^x andw(x)=x ^?, the possibility of approximation byw ⁿ p_n/q_n～ _∞ ⁿ⁼¹ , where depp _n≤αn, degq _n≤βn. The analysis utilizes potential theoretic methods. These are essentially sharp results though this will not be established in this paper.     

The box parameter for words and permutations

The box parameter for words counts how often two letters w _j and w _k define a “box” such that all the letters w _j+1; ..., w _k?1 fall into that box. It is related to the visibility parameter and other parameters on words. Three models are considered: Words over a finite alphabet, permutations, and words with letters following a geometric distribution. A typical result is: The average box parameter for words over an M letter alphabet is asymptotically given by 2n ? 2 _n H _M /M, for fixed M and n → ∞.     

Note on the uniquely colorable graphs

For n ≥ 3, if there exists a uniquely n colorable graph which contains no subgraph isomorphic to K₃, then the number of points in the graph must be strictly greater than n²+n?1.     

Fine and Wilf words for any periods

Let w = w₁ … w_n be a word of maximal length n, and with a maximal number of distinct letters for this length, such that w has periods p₁, …, p_n but not period gcd(p₁,…,p_r). We provide a fast algorithm to compute n and w. We show that w is uniquely determined apart from isomorphism and that it is a palindrome. Furthermore we give lower and upper bounds for n as explicit functions of p₁, …p_r. For r = 2 the exact value of n is due to Fine and Wilf. In case the number of distinct letters in the extremal word equals r a formula for n had been given by Castelli, Mignosi and Restivo in case r = 3 and by Justin if r > 3.     

Maximal dimensional partially ordered sets III: a characterization of Hiraguchi's inequality for interval dimension

Dushnik and Miller defined the dimensions of a partially ordered set X,denoted dim X, as the smallest positive integer t for which there exist t linear extensions of X whose intersection is the partial ordering on X. Hiraguchi proved that if n ≥2 and |X| ≤2n+1, then dim X ≤ n. Bogart, Trotter and Kimble have given a forbidden subposet characterization of Hiraguchi's inequality by determining for each n ≥ 2, the minimum collection of posets ?_n such that if |X| ?2n+1, the dim X < n unless X contains one of the posets from ?_n. Although |?₃|=24, for each n ≥ 4, ?_n contains only the crown S⁰_n — the poset consisting of all 1 element and n ? 1 element subsets of an n element set ordered by inclusion. In this paper, we consider a variant of dimension, called interval dimension, and prove a forbidden subposet characterization of Hiraguchi's inequality for interval dimension: If n ≥2 and |X 2n+1, the interval dimension of X is less than n unless X contains S⁰_n.