Covering Things with Things

An abstract NP-hard covering problem is presented and fixed-parameter tractable algorithms for this problem are described. The running times of the algorithms are expressed in terms of three parameters: $n$, the number of elements to be covered, $k$, the number of sets allowed in the covering, and $d$, the combinatorial dimension of the problem. The first algorithm is deterministic and has a running time of $O(k^{dk}n)$. The second algorithm is also deterministic and has a running time of $O(k^{d(k+1)}+n^{d+1})$. The third is a Monte-Carlo algorithm that runs in time $O(\runtime)$ and is correct with probability $1-n^{-c}$. Here, the $O$ notation hides factors that are polynomial in $d$. These algorithms lead to fixed-parameter tractable algorithms for many geometric and non-geometric covering problems.     

On fractal measures and diophantine approximation

We study diophantine properties of a typical point with respect to measures on Namely, we identify geometric conditions on a measure on guaranteeing that -almost every is not very well multiplicatively approximable by rationals. Measures satisfying our conditions are called friendly. Examples include smooth measures on nondegenerate manifolds; thus this paper generalizes the main result of [KM]. Another class of examples is given by measures supported on self-similar sets satisfying the open set condition, as well as their products and pushforwards by certain smooth maps.     

Generalized quadrangles with an ovoid that is translation with respect to opposite flags

The article [6] contains the result that if a finite generalized quadrangle of order s has an ovoid that is translation with respect to two opposite flags, but not with respect to any two non-opposite flags, then is self-polar and is the set of absolute points of a polarity. In particular, if is the classical generalized quadrangle Q(4, q) then is a Suzuki-Tits ovoid. In this article, we remove the need to assume that is Q(4, q) in order to conclude that is a Suzuki-Tits ovoid by showing that the initial assumptions in fact imply that is Q(4, q). At the same time, we also relax the requirement that have order s.Received: 14 May 2004     

Statistical ensemble error bounds for homogenized microheterogeneous solids

Typically, in order to characterize the homogenized effective macroscopic response of new materials possessing random heterogeneous microstructure, a relation between averages is sought, where and where and are the stress and strain tensor fields within a statistically representative volume element (SRVE) of volume ||. The quantity, is known as the effective property, and is the elasticity tensor used in usual macroscale analyses. In order to generate homogenized responses computationally, a series of detailed boundary value representations resolving the heterogeneous microstructure, posed over the SRVEs domain, must be solved. This requires an enormous numerical effort that can overwhelm most computational facilities. A natural way of generating an approximation to the SRVEs response is by first computing the response of smaller (subrepresentative) samples, each with a different random realization of the microstructural type under investigation, and then to ensemble average the results afterwards. Compared to a direct simulation of an SRVE, testing many small samples is a computationally inexpensive process since the number of floating point operations is greatly reduced, as well as the fact that the samples responses can be computed trivially in parallel. However, there is an inherent error in this process. Clearly the populations ensemble average is not the SRVEs response. However, as shown in this work, the moments on the distribution of the population can be used to generate rigorous upper and lower error bounds on the quality of the ensemble-generated response. Two-sided bounds are given on the SRVE response in terms of the ensemble average, its standard deviation and its skewness.Received: December 11, 2001     

Powers of the Euler product and commutative subalgebras of a complex simple Lie algebra

If is a complex simple Lie algebra, and k does not exceed the dual Coxeter number of , then the absolute value of the k^th coefficient of the power of the Euler product may be given by the dimension of a subspace of defined by all abelian subalgebras of of dimension k. This has implications for all the coefficients of all the powers of the Euler product. Involved in the main results are Dale Petersons 2^rank theorem on the number of abelian ideals in a Borel subalgebra of , an element of type and my heat kernel formulation of Macdonalds -function theorem, a set D_alcove of special highest weights parameterized by all the alcoves in a Weyl chamber (generalizing Young diagrams of null m-core when ), and the homology and cohomology of the nil radical of the standard maximal parabolic subalgebra of the affine Kac–Moody Lie algebra.     

Asymptotic Normality for Non-linear Functionals of Non-causal Linear Processes with Summable Weights

Let be a non-causal linear process with weights a_js satisfying certain summability conditions, and the iid sequence of innovation {_i} having zero mean and finite second moment. For a large class of non-linear functional K which includes indicator functions and polynomials, the present paper develops the central limit theorem for the partial sums      

Pairs of Convex Bodies with Centrally Symmetric Intersections of Translates

For a pair of convex bodies $K$ and $K$ in $E^d$, the $d$-dimensional intersections $K \cap (x + K),$ $x \in E^d,$ are centrally symmetric if and only if $K$ and $K$ are represented as direct sums $K = R \oplus P$ and $K = R \oplus P$ such that: (i) $R$ is a compact convex set of some dimension $m$, $0 \le m \le d,$ and $R = z - R$ for a suitable vector $z \in E^d$, (ii) $P$ and $P$ are isothetic parallelotopes, both of dimension $d-m$.     

Block elimination with one refinement solves bordered linear systems accurately

Linear systems with a fairly well-conditioned matrixM of the form , for which a black box solver forA is available, can be accurately solved by the standard process of Block Elimination, followed by just one step of Iterative Refinement, no matter how singularA may be — provided the black box has a property that is possessed by LU- and QR-based solvers with very high probability. The resulting Algorithm BE + 1 is simpler and slightly faster than T.F. Chan's Deflation Method, and just as accurate. We analyse the case where the black box is a solver not forA but for a matrix close toA. This is of interest for numerical continuation methods.Dedicated to the memory of J. H. Wilkinson     

Line Hypergraphs: A Survey

The survey is devoted to line graphs and a new multivalued function called the line hypergraph. This function generalizes two classical concepts at once, namely the line graph and the dual hypergraph. In a certain sense, line graphs and dual hypergraphs are extreme values of the function . There are many publications about line graphs, but our considerations are restricted to papers concerning Krausz global characterization of line graphs or Whitneys theorem on edge isomorphisms. The survey covers almost all known results on the function because they are concentrated around Krausz and Whitneys theorems. These results provide evidence that the notion of the line hypergraph is quite natural. It enables one to unify the classical theorems on line graphs and to obtain their more general versions in a simpler way.     

A sharper stability bound of Fourier frames

Given a real sequence {_n}_n. Suppose that is a frame for L²[–, ] with bounds A, B. The problem is to find a positive constant L such that for any real sequence {_n}_n with ¦_n –_n¦ <L, is also a frame for L²[–, ]. Balan [1] obtained arcsin . This value is a good stability bound of Fourier frames because it covers Kadec's 1/4-theorem and is better than (see Duffin and Schaefer [3]). In this paper, a sharper estimate is given.     

Boundary blow-up for a Brezis-Peletier problem on a singular domain

Let , , be a bounded domain as defined by Flucher, Garroni and Müller [6], which has a singular point such that the Robins function achieves its infimum at . Considering the elliptic problem in ; u = 0 on , with p = (N + 2)/(N-2), , and a minimizing solution of , concentrates at as goes to zero.Received: 15 September 2002, Accepted: 5 November 2002, Published online: 16 May 2003Mathematics Subject Classification: 35J65Angela Pistoia: The author is supported by M.U.R.S.T., project Metodi variazionali e topologici nello studio di fenomeni non lineari     

Subsemigroups of Completely Simple Semigroups and Weak Convergence of Convolution Products of Probability Measures

Let $S$ be a completely simple semigroup with a \underline{given} Rees product structure $A\times B\times C$. A subsemigroup of $S$ will be called a product subsemigroup of $A\times B\times C$ if it can be represented as $A\times B\times C$, where $A\subset A$, $B\subset B$ and $C\subset C$. Such subsemigroups appear when we look into the question of weak convergence of convolution products of (not necessarily identical) probability measures on certain topological semigroups. The reason is that the supports of tail-idempotents in the set of weak limit points of these convolution products are completely simple subsemigroups. The main result of this paper, Theorem 3.3, gives general sufficient conditions for the weak convergence of convolution products.     

Sur la convexité holomorphe des revêtements linéaires réductifs d’une variété projective algébrique complexe

Let X be a smooth connected compact projective variety over . We study the Shafarevich conjecture concerning holomorphic convexity along the lines of Kollárs approach, when the fundamental group of X admits large finite dimensionnal representations. We prove that, given n, the topological covering space of a projective algebraic compact complex manifold X corresponding to the intersection of the kernels of all linear reductive representations of ₁(X) to GL_n() is holomorphically convex. In the surface case, this is a corollary of a theorem due to Katzarkov and Ramachandran.      

A twistor construction of Kähler submanifolds of a quaternionic Kähler manifold

A class of minimal almost complex submanifolds of a Riemannian manifold with a parallel quaternionic structure Q, in particular of a 4-dimensional oriented Riemannian manifold, is studied. A notion of Kähler submanifold is defined. Any Kähler submanifold is pluriminimal. In the case of a quaternionic Kähler manifold of non zero scalar curvature, in particular, when is an Einstein, non Ricci-flat, anti-self-dual 4-manifold, we give a twistor construction of Kähler submanifolds M²ⁿ of maximal possible dimension 2n. More precisely, we prove that any such Kähler submanifold M²ⁿ of is the projection of a holomorphic Legendrian submanifold of the twistor space of , considered as a complex contact manifold with the natural holomorphic contact structure . Any Legendrian submanifold of the twistor space is defined by a generating holomorphic function. This is a natural generalization of Bryants construction of superminimal surfaces in S⁴=P¹. Mathematics Subject Classification (1991) Primary: 53C40; Secondary: 53C55     

On the Mean Value of the Index of Composition of an Integer

For each integer n 2, let be the index of composition of n, where . For convenience, we write (1)=(1)=1. We obtain sharp estimates for and , as well as for and . Finally we study the sum of running over shifted primes.Research supported in part by a grant from NSERC.Research supported by the Applied Number Theory Research Group of the Hungarian Academy of Science and by a grant from OTKA.     

ϰ-affine Räume

The -affine space is defined, i.e. a geometry in which distinct points are joint by exactly one curve (subspace of dimension 1). This definition generalizes the notions of affine [1] and Möbius [4] spaces. An example of a 5-affine space with the Mathieu group as automorphism group is constructed. There are only a few models of at least 4-affine planes of finite order.