Bounds on global secure sets in cactus trees

Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances.     

Range Minima Queries with Respect to a Random Permutation,and Approximate Range Counting

In approximate halfspace range counting, one is given a set P of n points in ℝ ^d , and an ε>0, and the goal is to preprocess P into a data structure which can answer efficiently queries of the form: Given a halfspace h, compute an estimate N such that (1−ε)|P∩h|≤N≤(1+ε)|P∩h|.     

A sup+inf inequality for Liouville type equations with weights

We generalize a result by H. Brezis, Y. Y. Li and I. Shafrir [6] and obtain an Harnack type inequality for solutions of −Δu = |x|^2α Ve ^u in Ω for Ω ⊂ ℝ² open, α ∈ (−1, 0) and V any Lipschitz continuous function satisfying 0 < a ≤ V ≤ b < ∞ and ‖∇V‖_∞ ≤ A.     

Characteristic features of the dynamics of the Ginzburg-Landau equation in a plane domain

We study the boundary value problem w_t=ℵ₀Δw+ℵ₁w-ℵ₂w|w|²,w|∂Ω₀=0 in the domain Ω₀={(x,y):0 ≤ x ≤ l₁,0 ≤ y ≤ l₂}. Here, w is a complex-valued function, Δ is the laplace operator, and ℵ_j, j=0,1,2, are complex constants withRe ℵ_j > 0. We show that under a rather general choice of the parameters l₁ and l₂, the number of stable invariant tori in the problem, as well as their dimensions, grows infinitely asRe ℵ₀ → 0 andRe ℵ₀ → 0. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 125, No. 2, pp. 205–220, November, 2000.     

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

Some properties of cliques in 0–1 mixed integer programs

Summary In this note we present new properties of cliques induced constraints straintsX(C _r ⁺ )-X(C _r ^- ) ≤ 1 - |C _r ^- | for λ εS, whereS is the set of cliques that are implied by 0–1 mixed integer programs. These properties allow to further fixing of 0–1 variables, to detect instance's infeasibility and to imply new cliques.     

Phase space,wavelet transform and Toeplitz-Hankel type operators

Domain constants are numbers attached to regions in the complex plane ℂ. For a region Ω in ℂ, letd(Ω) denote a generic domain constant. If there is an absolute constantM such thatM ⁻¹≤d(Ω)/d(Δ)≤M whenever Ω and Δ are conformally equivalent, then the domain constant is called quasiinvariant under conformal mappings. IfM=1, the domain constant is conformally invariant. There are several standard problems to consider for domain constants. One is to obtain relationships among different domain constants. Another is to determine whether a given domain constant is conformally invariant or quasi-invariant. In the latter case one would like to determine the best bound for quasi-invariance. We also consider a third type of result. For certain domain constants we show there is an absolute constantN such that |d(Ω)−d(Δ)|≤N whenever Ω and Δ and conformally equivalent, sometimes determing the best possible constantN. This distortion inequality is often stronger than quasi-invariance. We establish results of this type for six domain constants. Research partially supported by a National Science Foundation Grant.     

Lower bounds for weak epsilon-nets and stair-convexity

A set N ⊂ ℝ ^d is called a weak ɛ-net (with respect to convex sets) for a finite X ⊂ ℝ ^d if N intersects every convex set C with |X ∩ C| ≥ ɛ|X|. For every fixed d ≥ 2 and every r ≥ 1 we construct sets X ⊂ ℝ ^d for which every weak 1/r -net has at least Ω(r log ^d−1 r) points; this is the first superlinear lower bound for weak ɛ-nets in a fixed dimension.     

Finite unions of shore sets

Adendroid is an arcwise connected hereditarily unicoherent continuum. Ashore set in a dendroidX is a subsetA ofX such that, for each ε>0, there exists a subdendroidB ofX such that the Hausdorff distance fromB toX is less then ε andB∩A=θ. Answering a question by I. Puga, in this paper we prove that the finite union of pairwise disjoint shore subdendroids of a dendroidX is a shore set. We also show that the hypothesis that the shore subdendroids are disjoint is necessary. It is still unknown if the union of two closed disjoint shore subsets of a dendroidX is also shore set.     

Global curvature for surfaces and area minimization under a thickness constraint

Motivated by previous work on elastic rods with self-contact, involving the concept of the global radius of curvature for curves (as defined by Gonzalez and Maddocks), we define the global radius of curvature Δ[X] for a wide class of continuous parametric surfaces X for which the tangent plane exists on a dense set of parameters. It turns out that in this class of surfaces a positive lower bound Δ[X] ≥ θ > 0 provides, naively speaking, the surface with a thickness of magnitude θ; it serves as an excluded volume constraint for X, prevents self-intersections, and implies that the image of X is an embedded C¹-manifold with a Lipschitz continuous normal. We also obtain a convergence and a compactness result for such thick surfaces, and show one possible application to variational problems for embedded objects: the existence of ideal surfaces of fixed genus in each isotopy class. The proofs are based on a mixture of elementary topological, geometric and analytic arguments, combined with a notion of the reach of a set, introduced by Federer in 1959. Mathematics Subject Classification (2000) 49Q10, 53A05, 53C45, 57R52, 74K15     

Uniform rates of approximation by short asymptotic expansions in the CLT for quadratic forms

Let X, X ₁, X ₂,… be i.i.d. \mathbbR^d {\mathbb{R}^d} -valued real random vectors. Assume that E X = 0 and that X has a nondegenerate distribution. Let G be a mean zero Gaussian random vector with the same covariance operator as that of X. We study the distributions of nondegenerate quadratic forms \mathbbQ[ S_N ] \mathbb{Q}\left[ {{S_N}} \right] of the normalized sums S _N  = N ^−1/2 (X ₁ + ⋯ + X _N ) and show that, without any additional conditions,

A joint norm control Nehari type theorem forN-tuples of Hardy spaces

If N ∈ ℕ, 0 < p ≤ 1, and(X_k) _k=1 ^N are r.i.p-spaces, it is shown that there is C(= C(p, N)) > 0, such that for every ƒ ∈ ∩ _k=1 ^N X_k, there exists with , for every 1 ≤ k ≤ N. Also, if ⊓ is a convex polygon in ℝ², it is proved that the N-tuple (H(X₁),…, H(X_n)) is K_⊓-closed with respect to (X₁,…, X_N) in the sense of Pisier. Everything follows from Theorem 2.1, which is a general analytic partition of unity type result.     

Many partition relations below density

We force 2 ^λ to be large, and for many pairs in the interval (λ, 2 ^λ ) a strong version of the polarized partition relations holds. We apply this to problems in general topology. For example, consistently, every 2 ^λ is the successor of a singular and for every Hausdorff regular space X, hd(X) ≤ s(X)⁺³, hL(X) ≤ s(X)⁺³ and better when s(X) is regular, via a halfgraph partition relations. For the case s(X) = ℵ ₀ we get hd(X), hL(X) ≤ N ₂.     

An odd Furstenberg-Szemerédi theorem and quasi-affine systems

We prove a version of Furstenberg’s ergodic theorem with restrictions on return times. More specifically, for a measure preserving system (X, B, μ,T), integers 0 ≤j <k, andE ⊂X with μ(E) > 0, we show that there existsn ≡ j (modk) with ώ(E ∩T ^-nE ∩T ^-2nE ∩T ^-3nE) > 0, so long asT ^k is ergodic. This result requires a deeper understanding of the limit of some nonconventional ergodic averages and the introduction of a new class of systems, the ‘Quasi-Affine Systems’. This work was partially carried out while the second author was visiting the Université de Marne la Vallée, supported by NSF grant 9804651.     

The relation of Banach-Alaoglu theorem and Banach-Bourbaki-Kakutani-Šmulian theorem in complete random normed modules to stratification structure

Let (Ω,A,μ) be a probability space, K the scalar field R of real numbers or C of complex numbers,and (S,X) a random normed space over K with base (ω,A,μ). Denote the support of (S,X) by E, namely E is the essential supremum of the set {A ∈ A: there exists an element p in S such that X _p (ω) > 0 for almost all ω in A}. In this paper, Banach-Alaoglu theorem in a random normed space is first established as follows: The random closed unit ball S ^*(1) = {f ∈ S ^*: X ^* _f ⩽ 1} of the random conjugate space (S ^*,X ^*) of (S,X) is compact under the random weak star topology on (S ^*,X ^*) iff E∩A=: {E∩A | A ∈ A} is essentially purely μ-atomic (namely, there exists a disjoint family {A _n : n ∈ N} of at most countably many μ-atoms from E ∩ A such that E = ∪ _n=1^∞ A _n and for each element F in E ∩ A, there is an H in the σ-algebra generated by {A _n : n ∈ N} satisfying μ(FΔH) = 0), whose proof forces us to provide a key topological skill, and thus is much more involved than the corresponding classical case. Further, Banach-Bourbaki-Kakutani-Šmulian (briefly, BBKS) theorem in a complete random normed module is established as follows: If (S,X) is a complete random normed module, then the random closed unit ball S(1) = {p ∈ S: X _p ⩽ 1} of (S,X) is compact under the random weak topology on (S,X) iff both (S,X) is random reflexive and E ∩ A is essentially purely μ-atomic. Our recent work shows that the famous classical James theorem still holds for an arbitrary complete random normed module, namely a complete random normed module is random reflexive iff the random norm of an arbitrary almost surely bounded random linear functional on it is attainable on its random closed unit ball, but this paper shows that the classical Banach-Alaoglu theorem and BBKS theorem do not hold universally for complete random normed modules unless they possess extremely simple stratification structure, namely their supports are essentially purely μ-atomic. Combining the James theorem and BBKS theorem in complete random normed modules leads directly to an interesting phenomenum: there exist many famous classical propositions that are mutually equivalent in the case of Banach spaces, some of which remain to be mutually equivalent in the context of arbitrary complete random normed modules, whereas the other of which are no longer equivalent to another in the context of arbitrary complete random normed modules unless the random normed modules in question possess extremely simple stratification structure. Such a phenomenum is, for the first time, discovered in the course of the development of random metric theory.     

Uniform rates of convergence in the CLT for quadratic forms in multidimensional spaces

Summary.   Let X,X ₁,X ₂,… be a sequence of i.i.d. random vectors taking values in a d-dimensional real linear space ℝ ^d . Assume that E X=0 and that X is not concentrated in a proper subspace of ℝ ^d . Let G denote a mean zero Gaussian random vector with the same covariance operator as that of X. We investigate the distributions of non-degenerate quadratic forms ℚ[S _N ] of the normalized sums S _N =N ^−1/2(X ₁+⋯+X _N ) and show that

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.     

On antipodal Euclidean tight (2e + 1)-designs

Neumaier and Seidel (1988) generalized the concept of spherical designs and defined Euclidean designs in ℝ ⁿ . For an integer t, a finite subset X of ℝ ⁿ given together with a weight function w is a Euclidean t-design if holds for any polynomial f(x) of deg(f)≤ t, where {S _i , 1≤ i ≤ p} is the set of all the concentric spheres centered at the origin that intersect with X, X _i = X∩ S _i , and w:X→ ℝ_{> 0}. (The case of X⊂ S ⁿ⁻¹ with w≡ 1 on X corresponds to a spherical t-design.) In this paper we study antipodal Euclidean (2e+1)-designs. We give some new examples of antipodal Euclidean tight 5-designs. We also give the classification of all antipodal Euclidean tight 3-designs, the classification of antipodal Euclidean tight 5-designs supported by 2 concentric spheres.     

Geometric Models for Quasicrystals I. Delone Sets of Finite Type

This paper studies three classes of discrete sets X in ⁿ which have a weak translational order imposed by increasingly strong restrictions on their sets of interpoint vectors X-X . A finitely generated Delone set is one such that the abelian group [X-X] generated by X-X is finitely generated, so that [X-X] is a lattice or a quasilattice. For such sets the abelian group [X] is finitely generated, and by choosing a basis of [X] one obtains a homomorphism . A Delone set of finite type is a Delone set X such that X-X is a discrete closed set. A Meyer set is a Delone set X such that X-X is a Delone set. Delone sets of finite type form a natural class for modeling quasicrystalline structures, because the property of being a Delone set of finite type is determined by ``local rules.' That is, a Delone set X is of finite type if and only if it has a finite number of neighborhoods of radius 2R , up to translation, where R is the relative denseness constant of X . Delone sets of finite type are also characterized as those finitely generated Delone sets such that the map ϕ satisfies the Lipschitz-type condition ||ϕ (x) - ϕ (x')|| < C ||x - x'|| for x, x' ∈X , where the norms || . . . || are Euclidean norms on ^s and ⁿ , respectively. Meyer sets are characterized as the subclass of Delone sets of finite type for which there is a linear map and a constant C such that ||ϕ (x) - (x)|| for all x∈X . Suppose that X is a Delone set with an inflation symmetry, which is a real number η > 1 such that . If X is a finitely generated Delone set, then η must be an algebraic integer; if X is a Delone set of finite type, then in addition all algebraic conjugates | η ' | η; and if X is a Meyer set, then all algebraic conjugates | η ' | 1. Received May 9, 1997, and in revised form March 5, 1998.     

The density of rational points on non-singular hypersurfaces

LetF(x) =F[x₁,…,x_n]∈ℤ[x₁,…,x_n] be a non-singular form of degree d≥2, and letN(F, X)=#{xεℤ ⁿ ;F(x)=0, |x|⩽X}, where . It was shown by Fujiwara [4] [Upper bounds for the number of lattice points on hypersurfaces,Number theory and combinatorics, Japan, 1984, (World Scientific Publishing Co., Singapore, 1985)] thatN(F, X)≪X ^n−2+2/n for any fixed formF. It is shown here that the exponent may be reduced ton - 2 + 2/(n + 1), forn ≥ 4, and ton - 3 + 15/(n + 5) forn ≥ 8 andd ≥ 3. It is conjectured that the exponentn - 2 + ε is admissable as soon asn ≥ 3. Thus the conjecture is established forn ≥ 10. The proof uses Deligne’s bounds for exponential sums and for the number of points on hypersurfaces over finite fields. However a composite modulus is used so that one can apply the ‘q-analogue’ of van der Corput’s AB process. Dedicated to the memory of Professor K G Ramanathan