Maximum degree and fractional matchings in uniform hypergraphs

Let ℋ be a family ofr-subsets of a finite setX. SetD(ℋ)= |{E:x∈E∈ℋ}|, (maximum degree). We say that ℋ is intersecting if for anyH,H′ ∈ ℋ we haveH ∩H′ ≠ 0. In this case, obviously,D(ℋ)≧|ℋ|/r. According to a well-known conjectureD(ℋ)≧|ℋ|/(r−1+1/r). We prove a slightly stronger result. Let ℋ be anr-uniform, intersecting hypergraph. Then either it is a projective plane of orderr−1, consequentlyD(ℋ)=|ℋ|/(r−1+1/r), orD(ℋ)≧|ℋ|/(r−1). This is a corollary to a more general theorem on not necessarily intersecting hypergraphs.     

Decompositions of the Hardy space Hz^1（Ω）

We give a decomposition of the Hardy space Hz^1（Ω） into ＂div-curl＂ quantities for Lipschitz domains in R^n. We also prove a decomposition of Hz^1（Ω） into Jacobians det Du, u ∈ W0^1,2 （Ω,R^2） for Ω in R^2. This partially answers a well-known open problem.     

Indecomposability and the number of links

Let (ℋ, ℳ) be a linear matrix problem induced from a finite dimensional algebra ∧. Then anṉ ×ṉ matrix M in R(ℋ, ℳ) is indecomposable if and only if the number of links in the canonical formM ^(∞) of M is equal to. ℳ-dimṉ − 1. On the other hand, the dimension of the endomorphism ring of M is equal to ℋ-dimṉ − σ(M).     

An elementary approach to gap theorems

Using elementary comparison geometry, we prove: Let (M, g) be a simply-connected complete Riemannian manifold of dimension ≥ 3. Suppose that the sectional curvature K satisfies −1 − s(r) ≤ K ≤ −1, where r denotes distance to a fixed point in M. If lim _{r → ∞} e^2r s(r) = 0, then (M, g) has to be isometric to ℍ ⁿ . The same proof also yields that if K satisfies −s(r) ≤ K ≤ 0 where lim _{r → ∞} r ² s(r) = 0, then (M, g) is isometric to ℝ ⁿ , a result due to Greene and Wu. Our second result is a local one: Let (M, g) be any Riemannian manifold. For a ∈ ℝ, if K ≤ a on a geodesic ball B _p (R) in M and K = a on ∂B _p (R), then K = a on B _p (R).     

Piecewise linear paths among convex obstacles

Let ℬ be a set ofn arbitrary (possibly intersecting) convex obstacles in ℝ ^d . It is shown that any two points which can be connected by a path avoiding the obstacles can also be connected by a path consisting ofO(n ^{(d−1)[d/2+1]}) segments. The bound cannot be improved below Ω(n ^d ); thus, in ℝ³, the answer is betweenn ³ andn ⁴. For open disjoint convex obstacles, a Θ(n) bound is proved. By a well-known reduction, the general case result also upper bounds the complexity for a translational motion of an arbitrary convex robot among convex obstacles. Asymptotically tight bounds and efficient algorithms are given in the planar case. This research was supported by The Netherlands' Organization for Scientific Research (NWO) and partially by the ESPRIT III Basic Research Action 6546 (PROMotion). J. M. acknowledges support by a Humboldt Research Fellowship. Part of this research was done while he visited Utrecht University.     

The Dichotomy Between Traces on d-sets F in R^n and the Density of D（R^n／Г） in Function Spaces

A space Apq^s （R^n） with A ： B or A = F and s ∈R, 0 〈 p, q 〈 ∞ either has a trace in Lp（Г）, where Г is a compact d-set in R^n with 0 〈 d 〈 n, or D（R^n／Г） is dense in it. Related dichotomy numbers are introduced and calculated.     

On the stability of solutions to quadratic programming problems

We consider the parametric programming problem (Q _p ) of minimizing the quadratic function f(x,p):=x ^T Ax+b ^T x subject to the constraint Cx≤d, where x∈ℝ ⁿ , A∈ℝ ^n×n , b∈ℝ ⁿ , C∈ℝ ^m×n , d∈ℝ ^m , and p:=(A,b,C,d) is the parameter. Here, the matrix A is not assumed to be positive semidefinite. The set of the global minimizers and the set of the local minimizers to (Q _p ) are denoted by M(p) and M ^loc (p), respectively. It is proved that if the point-to-set mapping M ^loc (·) is lower semicontinuous at p then M ^loc (p) is a nonempty set which consists of at most ? _m,n points, where ? _m,n = is the maximal cardinality of the antichains of distinct subsets of {1,2,...,m} which have at most n elements. It is proved also that the lower semicontinuity of M(·) at p implies that M(p) is a singleton. Under some regularity assumption, these necessary conditions become the sufficient ones. Received: November 5, 1997 / Accepted: September 12, 2000?Published online November 17, 2000     

Hardy spaces via distribution spaces

Let ℐ(ℝⁿ) be the Schwartz class on ℝⁿ and ℐ_∞(ℝⁿ) be the collection of functions ϕ ∊ ℐ(ℝⁿ) with additional property that

On Optimal Orientations of Cartesian Products of Trees

. Let d(D) (resp., d(G)) denote the diameter and r(D) (resp., r(G)) the radius of a digraph D (resp., graph G). Let G×H denote the cartesian product of two graphs G and H. An orientation D of G is said to be (r, d)-invariant if r(D)=r(G) and d(D)=d(G). Let {T _i }, i=1,…,n, where n≥2, be a family of trees. In this paper, we show that the graph ∏ _{i =1} ⁿ T _i admits an (r, d)-invariant orientation provided that d(T ₁)≥d(T ₂)≥4 for n=2, and d(T ₁)≥5 and d(T ₂)≥4 for n≥3. Received: July 30, 1997 Final version received: April 20, 1998     

Better lower bounds on detecting affine and spherical degeneracies

We show that in the worst case, Ω(n ^d ) sidedness queries are required to determine whether a set ofn points in ℝ ^d is affinely degenerate, i.e., whether it containsd+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n ^d ) “collapsible” simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n ^d ) lower bound on the number of sidedness queries required to determine the order type of a set ofn points in ℝ ^d . Using similar techniques, we also show that Ω(n ^d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set ofn points in ℝ ^d . An earlier version of this paper was presented at the 34th Annual IEEE Symposium on Foundations of Computer Science [8]. This research has been supported by NSF Presidential Young Investigator Grant CCR-9058440.     

Affinely equivalent complete flat manifolds

Let E _Aff(Γ,G, m) be the set of affine equivalence classes of m-dimensional complete flat manifolds with a fixed fundamental group Γ and a fixed holonomy group G. Let n be the dimension of a closed flat manifold whose fundamental group is isomorphic to Γ. We describe E _Aff(Γ,G, m) in terms of equivalence classes of pairs (ε, ρ), consisting of epimorphisms of Γ onto G and representations of G in ℝ ^m-n . As an application we give some estimates of card E _Aff(Γ,G, m).     

Dilations and Completions for Gabor Systems

Let be a full rank time-frequency lattice in ℝ ^d ×ℝ ^d . In this note we first prove that any dual Gabor frame pair for a Λ-shift invariant subspace M can be dilated to a dual Gabor frame pair for the whole space L ²(ℝ ^d ) when the volume v(Λ) of the lattice Λ satisfies the condition v(Λ)≤1, and to a dual Gabor Riesz basis pair for a Λ-shift invariant subspace containing M when v(Λ)>1. This generalizes the dilation result in Gabardo and Han (J. Fourier Anal. Appl. 7:419–433, [2001]) to both higher dimensions and dual subspace Gabor frame pairs. Secondly, for any fixed positive integer N, we investigate the problem whether any Bessel–Gabor family G(g,Λ) can be completed to a tight Gabor (multi-)frame G(g,Λ)∪(∪ _j=1 ^N G(g _j ,Λ)) for L ²(ℝ ^d ). We show that this is true whenever v(Λ)≤N. In particular, when v(Λ)≤1, any Bessel–Gabor system is a subset of a tight Gabor frame G(g,Λ)∪G(h,Λ) for L ²(ℝ ^d ). Related results for affine systems are also discussed. Communicated by Chris Heil.     

The Estimates for Sharp Maximal Functions of Multilinear Strongly Singular Integral Operators

In this paper, the author obtains that the multilinear operators of strongly singular integral operators and their dual operators are bounded from some L^p（R^n） to L^p（R^n） when the m-th order derivatives of A belong to L^p（R^n） for r large enough. By this result, the author gets the estimates for the Sharp maximal functions of the multilinear operators with the m-th order derivatives of A being Lipschitz functions. It follows that the multilinear operators are （L^p, L^p）-type operators for 1 〈 p 〈 ∞.     

Order reduction of the Euler-Lagrange equations of higher order invariant variational problems on frame bundles

Let μ: FX → X be a principal bundle of frames with the structure group Gl _n (ℝ). It is shown that the variational problem, defined by Gl _n (ℝ)-invariant Lagrangian on J ^r FX, can be equivalently studied on the associated space of connections with some compatibility condition, which gives us order reduction of the corresponding Euler-Lagrange equations.     

The Maximal Operator Associated to a Nonsymmetric Ornstein–Uhlenbeck Semigroup

Let (ℋ _t ) _t≥0 be the Ornstein–Uhlenbeck semigroup on ℝ ^d with covariance matrix I and drift matrix λ(R−I), where λ>0 and R is a skew-adjoint matrix, and denote by γ _∞ the invariant measure for (ℋ _t ) _t≥0. Semigroups of this form are the basic building blocks of Ornstein–Uhlenbeck semigroups which are normal on L ²(γ _∞). We prove that if the matrix R generates a one-parameter group of periodic rotations, then the maximal operator ℋ_* f(x)=sup  _t≥o |ℋ _t f(x)| is of weak type 1 with respect to the invariant measure γ _∞. We also prove that the maximal operator associated to an arbitrary normal Ornstein–Uhlenbeck semigroup is bounded on L ^p (γ _∞) if and only if 1<p≤∞.      

Weighted estimates for commutators of singular integral operators with non-doubling measures

Letμbe a nonnegative Radon measure on R~d which only satisfiesμ(B(x,r))≤C_0r~n for all x∈R~d,r>0,and some fixed constants C_0>0 and n∈(0,d].In this paper,some weighted weak type estimates with A_(p,(log L)~σ)~ρ(μ) weights are established for the commutators generated by Calder■n-Zygmund singular integral operators with RBMO(μ) functions.     

Surjective partial differential operators on real analytic functions defined on open convex sets

Let P(D) be a partial differential operator with constant coefficients which is surjective on the space A(Ω) of real analytic functions on a covex open set Ω⊂ℝ ⁿ . Let L(P _m ) denote the localizations at ∞ (in the sense of H?rmander) of the principal part P _m . Then Q(x+iτN)≠ 0 for (x,τ)∈ℝ ⁿ ×(ℝ\{ 0}) for any Q∈L(P _m ) if N is a normal to δΩ which is noncharacteristic for Q. Under additional assumptions this implies that P _m must be locally hyperbolic. Received: 24 January 2000     

Voronoi diagrams of random lines and flats

It is proved that, for any fixedd ≽ 3 and 0 ≤k ≤ d - 1, the expected combinatorial complexity of the Euclidean Voronoi diagram ofn random &-flats drawn independently from the uniform distribution onk-flats intersecting the unit ball in ℝ^d is Ξ(n ^d/(d-k)) asn → ∞. A by-product of the proof is a density transformation for integrating over sets ofd + 1k-flats in ℝ^d     

On the maximal operator associated with certain rotational invariant measures

The aim of this work is to investigate the integrability properties of the maximal operator Mu,associated with a non-doubling measure μ defined on Rn. We start by establishing for a wide class of radial and increasing measures μ that Mu is bounded on all the spaces Lu^p（R^n）,P〉1.Also,we show that there is a radial and increasing measure p for which Mμ does not map Lμ^p（R^n） into weak Lμ^p（R^n）,1≤p〈∞.