Global Connectivity And Expansion: Long Cycles and Factors In f-Connected Graphs

Given a function f : ℕ→ℝ, call an n-vertex graph f-connected if separating off k vertices requires the deletion of at least f(k) vertices whenever k≤(n−f(k))/2. This is a common generalization of vertex connectivity (when f is constant) and expansion (when f is linear). We show that an f-connected graph contains a cycle of length linear in n if f is any linear function, contains a 1-factor and a 2-factor if f(k)≥2k+1, and contains a Hamilton cycle if f(k)≥2(k+1)². We conjecture that linear growth of f suffices to imply hamiltonicity.     

Bounding the number of connected components of a real algebraic set

For every polynomial mapf=(f ₁,…,f _k): ℝ ⁿ →ℝ ^k , we consider the number of connected components of its zero set,B(Z _f) and two natural “measures of the complexity off,” that is the triple(n, k, d), d being equal to max(degree off _i), and thek-tuple (Δ₁,...,Δ₄), Δ _k being the Newton polyhedron off _i respectively. Our aim is to boundB(Z _f) by recursive functions of these measures of complexity. In particular, with respect to (n, k, d) we shall improve the well-known Milnor-Thom’s bound μ _d (n)=d(2d−1) ⁿ⁻¹. Considered as a polynomial ind, μ _d (n) has leading coefficient equal to 2 ⁿ⁻¹. We obtain a bound depending onn, d, andk such that ifn is sufficiently larger thank, then it improves μ _d (n) for everyd. In particular, it is asymptotically equal to 1/2(k+1)n ^k−1 dⁿ, ifk is fixed andn tends to infinity. The two bounds are obtained by a similar technique involving a slight modification of Milnor-Thom's argument, Smith's theory, and information about the sum of Betti numbers of complex complete intersections.     

Polynomials of best approximation inC[−1,1]

Equivalences between the condition |P _n ^(k) (x)|≦K(n ⁻¹√1−x ²+1/n ²) ^k n ^-a, whereP _n(x) is the bestn-th degree polynomial approximation tof(x), and the Peetre interpolation space betweenC[−1,1] and the space (1−x ²) ^k f ^(2k)(x)∈C[−1,1] is established. A similar result is shown forE _n(f)= ‖f−P _n‖ _C[−1,1]. Rates other thann ^-a are also discussed. Supported by NSERC grant A4816 of Canada.     

A class of constructions for turán’s (3, 4)-problem

Letf(n) denote the minimal number of edges of a 3-uniform hypergraphG=(V, E) onn vertices such that for every quadrupleY ⊂V there existsY ⊃e ∈E. Turán conjectured thatf(3k)=k(k−1)(2k−1). We prove that if Turán’s conjecture is correct then there exist at least 2 ^k−2 non-isomorphic extremal hypergraphs on 3k vertices.     

Growth and distortion theorems on subclasses of quasi-convex mappings in several complex variables

In this paper, the refining growth and covering theorems for f are established, where f is a quasi-convex mapping of order α and x = 0 is a zero of order k + 1 of f(x) − x. As an application, we obtain the upper and lower bounds on the distortion theorem of f(x) defined on the unit polydisc of ℂ ⁿ . The upper bound of the distortion theorem for f(x) defined on the unit ball of a complex Banach space is also given. Our results extend the growth and distortion theorems for convex functions of one complex variable to quasi-convex mappings of several complex variables.     

On the Construction of Permutation Arrays via Mappings from Binary Vectors to Permutations

An (n, d, k)-mapping f is a mapping from binary vectors of length n to permutations of length n + k such that for all x, y {0,1}ⁿ, d_H (f(x), f(y)) ≥ d_H (x, y) + d, if d_H (x, y) ≤ (n + k) − d and d_H (f(x), f(y)) = n + k, if d_H (x, y) > (n + k) − d. In this paper, we construct an (n,3,2)-mapping for any positive integer n ≥ 6. An (n, r)-permutation array is a permutation array of length n and any two permutations of which have Hamming distance at least r. Let P(n, r) denote the maximum size of an (n, r)-permutation array and A(n, r) denote the same setting for binary codes. Applying (n,3,2)-mappings to the design of permutation array, we can construct an efficient permutation array (easy to encode and decode) with better code rate than previous results [Chang (2005). IEEE Trans inf theory 51:359–365, Chang et al. (2003). IEEE Trans Inf Theory 49:1054–1059; Huang et al. (submitted)]. More precisely, we obtain that, for n ≥ 8, P(n, r) ≥ A(n − 2, r − 3) > A(n − 1,r − 2) = A(n, r − 1) when n is even and P(n, r) ≥ A(n − 2, r − 3) = A(n − 1, r − 2) > A(n, r − 1) when n is odd. This improves the best bound A(n − 1,r − 2) so far [Huang et al. (submitted)] for n ≥ 8. The work was supported in part by the National Science Council of Taiwan under contract NSC-93-2213-E-009-117     

On K s -free subgraphs in K s+k -free graphs and vertex Folkman numbers

Extending the problem of determining Ramsey numbers Erdős and Rogers introduced the following function. For given integers 2 ≤ s < t let f _s,t (n) = min{max{|S|: S ⊆ V (H) and H[S] contains no K _s }}, where the minimum is taken over all K _t -free graphs H of order n. This function attracted a considerable amount of attention but despite that, the gap between the lower and upper bounds is still fairly wide. For example, when t=s+1, the best bounds have been of the form Ω(n ^1/2+o(1)) ≤ f _s,s+1(n) ≤ O(n ^1−ɛ(s)), where ɛ(s) tends to zero as s tends to infinity. In this paper we improve the upper bound by showing that f _s,s+1(n) ≤ O(n ^2/3). Moreover, we show that for every ɛ > 0 and sufficiently large integers 1 ≪ k ≪ s, Ω(n ^1/2−ɛ ) ≤ f _s,s+k (n) ≤ O(n ^1/2+ɛ . In addition, we also discuss some connections between the function f _s,t and vertex Folkman numbers.     

Norm inequalities for a certain class of ∞ functions

In 1936 the author showed that the function sin(π(x+1)/4) is the entire function of least exponential type (=π/4) among all entire functionsf(z) with the property thatf ⁽ⁿ⁾(z) vanishes somewhere in the real interval [−1, 1] (n=0, 1,2,…). Now more precise results of this kind are obtained by working within the class ∞[−1, 1]. For Paul Montel on his 95th birthday     

A counterexample in copositive approximation

The present paper gives a converse result by showing that there exists a functionf ∈C _[−1,1], which satisfies that sgn(x)f(x) ≥ 0 forx ∈ [−1, 1], such that {fx75-1} whereE _n ⁽⁰⁾ (f, 1) is the best approximation of degreen tof by polynomials which are copositive with it, that is, polynomialsP withP(x(f(x) ≥ 0 for allx ∈ [−1, 1],E _n(f) is the ordinary best polynomial approximation off of degreen.     

Rate of decay of weakly lacunary series

Let function f(z) ≠ 0 be analytic in the unit disk and have sparse nonzero Taylor coefficients. Then the rate of decay of the function f as x → 1 − 0 depends on the rate of sparseness of its nonzero Taylor coefficients. In this paper, we consider the case f(z) = $ \sum\nolimits_{k = 0}^\infty {a_k z^{n_k } } $ \sum\nolimits_{k = 0}^\infty {a_k z^{n_k } } , where n _k ≥ A ₀(k + 2) ^p logb(k + 2).     

Asymptotic Upper Bounds for Ramsey Functions

 We show that for any graph G with N vertices and average degree d, if the average degree of any neighborhood induced subgraph is at most a, then the independence number of G is at least Nf _{a +1}(d), where f _{a +1}(d)=∫₀ ¹(((1−t)^{1/( a +1)})/(a+1+(d−a−1)t))dt. Based on this result, we prove that for any fixed k and l, there holds r(K _k + _l ,K _n )≤ (l+o(1))n ^k /(logn) ^{k −1}. In particular, r(K _k , K _n )≤(1+o(1))n ^{k −1}/(log n) ^{k −2}. Received: May 11, 1998 Final version received: March 24, 1999     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

Differential polynomials sharing one value

In this paper, we investigate uniqueness problems of differential polynomials of meromorphic functions. Let a, b be non-zero constants and let n, k be positive integers satisfying n ≥ 3k+12. If fⁿ + af^(k) and gⁿ + ag^(k) share b CM and the b-points of fⁿ + af^(k) are not the zeros of f and g, then f and g are either equal or closely related.     

A criterion of normality based on a single holomorphic function

Let F be a family of functions holomorphic on a domain D ⊂ ℂ Let k ≥ 2 be an integer and let h be a holomorphic function on D, all of whose zeros have multiplicity at most k −1, such that h(z) has no common zeros with any f ∈ F. Assume also that the following two conditions hold for every f ∈ F: (a) f(z) = 0 ⇒ f′(z) = h(z); and (b) f′(z) = h(z) ⇒ |f ^(k)(z)| ≤ c, where c is a constant. Then F is normal on D.     

Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications

Let A be an n×N real-valued matrix with n<N; we count the number of k-faces f _k (AQ) when Q is either the standard N-dimensional hypercube I ^N or else the positive orthant ℝ₊ ^N . To state results simply, consider a proportional-growth asymptotic, where for fixed δ,ρ in (0,1), we have a sequence of matrices A_n,NnA_{n,N_{n}} and of integers k _n with n/N _n →δ and k _n /n→ρ as n→∞. If each matrix A_n,NnA_{n,N_{n}} has its columns in general position, then f _k (AI ^N )/f _k (I ^N ) tends to zero or one depending on whether ρ>min (0,2−δ ⁻¹) or ρ<min (0,2−δ ⁻¹). Also, if each A_n,NnA_{n,N_{n}} is a random draw from a distribution which is invariant under right multiplication by signed permutations, then f _k (Aℝ₊ ^N )/f _k (ℝ₊ ^N ) tends almost surely to zero or one depending on whether ρ>min (0,2−δ ⁻¹) or ρ<min (0,2−δ ⁻¹). We make a variety of contrasts to related work on projections of the simplex and/or cross-polytope. These geometric face-counting results have implications for signal processing, information theory, inverse problems, and optimization. Indeed, face counting is related to conditions for uniqueness of solutions of underdetermined systems of linear equations. Below, let A be a fixed n×N matrix, n<N, with columns in general position.

Properties of generalised juxtapolynomials

GivenF(z),f ₁(z), ..,f _n(z) defined on a finite point setE, and givenB — the set of generalised polynomials Σ _k ^=1/n a _kf_k(z) — the definition of a juxtapolynomial is extended in the following manner: for a fixedλ(0<λ≦1),f(z) εB is called a generalizedλ-weak juxtapolynomial toF(z) onE if and only if there exists nog(z) εB for whichg(z)=F(z) wheneverf(z)=F(z) and |g(z)−F(z) |<λ|f(z)−F(z)| wheneverf(z)≠F(z). The properties of suchf(z) are investigated with particular attention given to the real case. This note is an extension of a part of the author’s M.Sc. Thesis under the supervision of Prof. B. Grünbaum to whom the author wishes to express his sincerest appreciation. The author also wishes to thank Dr. J. Lindenstrauss for his valuable remarks in the preparation of this paper.     

Estimates on binomial sums of partition functions

Let p(n) denote the partition function and define where p(0)= 1. We prove that p(n,k) is unimodal and satisfies for fixed n≥ 1 and all 1≤k≤n. This result has an interesting application: the minimal dimension of a faithful module for a k-step nilpotent Lie algebra of dimension n is bounded by p(n,k) and hence by , independently of k. So far only the bound n ^{n −1} was known. We will also prove that for n≥ 1 and . Received: 17 December 1999     

Reconstruction of functions from their integrals over<Emphasis Type="Italic">k</Emphasis>-planes

Thek-plane Radon transform assigns to a functionsf(x) on ℝ ⁿ the collection of integralsf(τ)=∫ _τ f over allk-dimensional planesτ. We give a systematic treatment of two inversion methods for this transform, namely, the method of Riesz potentials, and the method of spherical means. We develop new analytic tools which allow to invertf(τ) under minimal assumptions forf. It is assumed thatfεL ^p , 1≤p<n/k, orf is a continuous function with minimal rate of decay at infinity. In the framework of the first method, our approach employs intertwining fractional integrals associated to thek-plane transform. Following the second method, we extend the original formula of Radon for continuous functions on ℝ² tofεL ^p (ℝ ⁿ ) and all 1≤k<n. New integral formulae and estimates, generalizing those of Fuglede and Solmon, are obtained. The work was supported in part by the Edmund Landau Center for Research in Mathematical Analysis and Related Areas, sponsored by the Minerva Foundation (Germany).     

Negative result in pointwise 3-convex polynomial approximation

Let Δ³ be the set of functions three times continuously differentiable on [−1, 1] and such that f″′(x) ≥ 0, x ∈ [−1, 1]. We prove that, for any n ∈ ℕ and r ≥ 5, there exists a function f ∈ C ^r [−1, 1] ⋂ Δ³ [−1, 1] such that ∥f ^(r)∥ _{C[−1, 1]} ≤ 1 and, for an arbitrary algebraic polynomial P ∈ Δ³ [−1, 1], there exists x such that

On Kneser solutions of higher order nonlinear ordinary differential equations

The equationx ⁽ⁿ⁾(t)=(−1) ⁿ │x(t)│ ^k withk>1 is considered. In the casen≦4 it is proved that solutions defined in a neighbourhood of infinity coincide withC(t−t₀)^−n/(k−1), whereC is a constant depending only onn andk. In the general case such solutions are Kneser solutions and can be estimated from above and below by a constant times (t−t ₀)^−n/(k−1). It is shown that they do not necessarily coincide withC(t−t₀)^−n/(k−1). This gives a negative answer to two conjectures posed by Kiguradze that Kneser solutions are determined by their value in a point and that blow-up solutions have prescribed asymptotics. Dedicated to Professor Vladimir Maz'ya on the occasion of his 60th birthday. The author was supported by the Swedish Natural Science Research Council (NFR) grant M-AA/MA 10879-304.