Polynomial-time approximation of largest simplices in V-polytopes

This paper considers the problem of computing the squared volume of a largest j-dimensional simplex in an arbitrary d-dimensional polytope P given by its vertices (a “V-polytope”), for arbitrary integers j and d with 1⩽j⩽d. The problem was shown by Gritzmann, Klee and Larman to be $\text{NP}$-hard. This paper examines the possible accuracy of deterministic polynomial-time approximation algorithms for the problem. On the negative side, it is shown that unless $\text{P}\text{=}\text{NP}$, no such algorithm can approximately solve the problem within a factor of less than 1.09. It is also shown that the $\text{NP}$-hardness and inapproximability continue to hold when the polytope P is restricted to be an affine crosspolytope.On the positive side, a simple deterministic polynomial-time approximation algorithm for the problem is described. The algorithm takes as input integers j and d with 1⩽j⩽d and a V-polytope P of dimension d. It returns a j-simplex S⊂P such that$\text{vol}{}^2\text{(T)}\text{vol}{}^2\text{(S)}\text{⩽A(Bj)}{}^{\mathrm{j}}\text{,}$where T is any largest j-simplex in P, and A and B are positive constants independent of j,d,P.     

Hamiltonicity in (0–1)-polyhedra

The graph G(P) of a polyhedron P has a node corresponding to each vertex of P and two nodes are adjacent in G(P) if and only if the corresponding vertices of P are adjacent on P. We show that if P ? $\text{R}$ⁿ is a polyhedron, all of whose vertices have (0–1)-valued coordinates, then (i) if G(P) is bipartite, the G(P) is a hypercube; (ii) if G(P) is nonbipartite, then G(P) is hamilton connected. It is shown that if P ? $\text{R}$ⁿ has (0–1)-valued vertices and is of dimension d (≤n) then there exists a polyhedron P′ ? $\text{R}$^d having (0–1)-valued vertices such that $\text{G(P) ? G(P′)}$. Some combinatorial consequences of these results are also discussed.     

Equivalence of measures for some class of Gaussian random fields

We consider two Gaussian measures P₁ and P₂ on (C(G), $\text{B}$) with zero expectations and covariance functions R₁(x, y) and R₂(x, y) respectively, where R_ν(x, y) is the Green's function of the Dirichlet problem for some uniformly strongly elliptic differential operator A^(ν) of order $\text{2m, m ≥ [}\text{d}\text{2}\text{] + 1}$, on a bounded domain G in $\text{R}$^d (ν = 1, 2). It is shown that if the order of A⁽²⁾ ? A⁽¹⁾ is at most $\text{2m ? [}\text{d}\text{2}\text{] ? 1}$, then P₁ and P₂ are equivalent, while if the order is greater than $\text{2m ? [}\text{d}\text{2}\text{] ? 1}$, then P₁ and P₂ are not always equivalent.     

Asymptotic behavior of a stochastic growth process associated with a system of interacting branching random walksComportement asymptotique d'un processus stochastique de croissance associé à un système de marches aléatoires en interaction

We study a continuous time growth process on $\text{Z}{}^{\mathrm{d}}$ (d?1) associated to the following interacting particle system: initially there is only one simple symmetric continuous time random walk of total jump rate one located at the origin; then, whenever a random walk visits a site still unvisited by any other random walk, it creates a new independent random walk starting from that site. Let us call P_d the law of such a process and S⁰_d(t) the set of sites, visited by all walks by time t. We prove that there exists a bounded, non-empty, convex set $\text{C}{}_{\mathrm{d}}\text{?}\text{R}{}^{\mathrm{d}}$, such that for every ε>0, P_d-a.s. eventually in t, the set S_d⁰(t) is within an ε neighborhood of the set [C_dt], where for $\text{A?}\text{R}{}^{\mathrm{d}}$ we define $\text{[A]:=A∩}\text{Z}{}^{\mathrm{d}}$. Moreover, for d large enough, the set C_d is not a ball under the Euclidean norm. We also show that the empirical density of particles within S_d⁰(t) converges weakly to a product Poisson measure of parameter one. To cite this article: A.F. Ram??rez, V. Sidoravicius, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 821–826.     

Harmonic analysis on unitary groups

A theory of harmonic analysis on a metric group (G, d) is developed with the model of U$\text{U}$, the unitary group of a C¹-algebra $\text{U}$, in mind. Essential in this development is the set $\text{G}\text{?}{}_{\mathrm{d}}$ of contractive, irreducible representations of G, and its concomitant set P_d(G) of positive-definite functions. It is shown that $\text{G}\text{?}{}_{\mathrm{d}}$ is compact and closed in $\text{G}\text{?}$. The set $\text{G}\text{?}{}_{\mathrm{d}}$ is determined in a number of cases, in particular when G = U($\text{U}$) with $\text{U}$ abelian. If $\text{U}$ is an AW¹-algebra, it is shown that $\text{G}\text{?}$_d is essentially the same as $\text{U}\text{?}$. Unitary groups are characterised in terms of a certain Lie algebra $\text{g}$_u and several characterisations of G = U($\text{U}$) when $\text{U}$ is abelian are given.     

Girsanov functionals and optimal bang-bang laws for final value stochastic control

Girsanov's theorem is a generalization of the Cameron-Martin formula for the derivative of a measure induced by a translation in Wiener space. It states that for ? a nonanticipative Brownian functional with ∫|?|² ds < ∞ a.s. and $\text{d}\text{P}\text{?}\text{=exp[ζ(?)] d}\text{P}$ with $\text{E}\text{?}\text{{1}=1}$, where $\text{ζ(?) = ∫?}\text{d}\text{w-}\text{1}\text{2}\text{∫|?|}{}^2\text{d}\text{s}$, the translated functions $\text{(Tw)(t) = w}{}_{\mathrm{t}}\text{-}\text{∫}\text{0}\text{t}\text{?}\text{d}\text{s}$ are a Wiener process under P?. The Girsanov functionals exp [ζ(?)] have been used in stochastic control theory to define measures corresponding to solutions of stochastic DEs with only measurable control laws entering the right-hand sides. The present aim is to show that these same concepts have direct practical application to final value problems with bounded control. This is done here by an example, the noisy integrator: Make E{x²₁}∣small, subject to dx_t = u_t dt + dw_t, |u|? 1, x_t observed. For each control law there is a definite cost v(1?t, x) of starting at x, t and using that law till t = 1, expressible as an integral with respect to (a suitable) P?. By restricting attention to a dense set of smooth laws, using Itô's lemma, Kac's theorem, and the maximum principle for parabolic equations, it is possible to calculate sgn v_x for a critical class of control laws, then to compare control laws, “solve” the Bellman-Hamilton-Jacobi equation, and thus justify selection of the obvious bang-bang law as optimal.     

A class of extension properties that are not simply generated

Let $\text{P}$ be a closed-hereditary topological property preserved by products. Call a space $\text{P}$-regular if it is homeomorphic to a subspace of a product of spaces with $\text{P}$. Suppose that each $\text{P}$-regular space possesses a $\text{P}$-regular compactification. It is well-known that each $\text{P}$-regular space X is densely embedded in a unique space γ_scPX with $\text{P}$ such that if f: X → Y is continuous and Y has $\text{P}$, then f extends continuously to γ_scPX. Call $\text{P}$-pseudocompact if γ_scPX is compact.Associated with $\text{P}$ is another topological property $\text{P}$^#, possessing all the properties hypothesized for $\text{P}$ above, defined as follows: a $\text{P}$-regular space X has $\text{P}$^# if each $\text{P}$-pseudocompact closed subspace of X is compact. It is known that the $\text{P}$-pseudocompact spaces coincide with the $\text{P}$^#-pseudocompact spaces, and that $\text{P}$^# is the largest closed-hereditary, productive property for which this is the case. In this paper we prove that if $\text{P}$ is not the property of being compact and $\text{P}$-regular, then $\text{P}$^# is not simply generated; in other words, there does not exist a space E such that the spaces with $\text{P}$^# are precisely those spaces homeomorphic to closed subspaces of powers of E.     

Ordered partitions and codes generated by circulant matrices

We consider the set of ordered partitions of n into m parts acted upon by the cyclic permutation (12…m). The resulting family of orbits $\text{P}\text{(n, m)}$ is shown to have cardinality $\text{p}\text{(n,m)=(}\text{1}\text{n}\text{∑}{}_{\mathrm{<mtext>d</mtext><mtext>m</mtext>}}\text{φ(d)(}{}_{\mathrm{<mtext>n</mtext><mtext>d</mtext>}}{}^{\mathrm{<mtext>m</mtext><mtext>d</mtext>}}\text{)}$, where φ is Euler's φ-function. $\text{P}\text{(n, m)}$ is shown to be set-isomorphic to the family of orbits $\text{C}\text{(n, m)}$ of the set of all m-subsets of an n-set acted upon by the cyclic permutation (12…n). This isomorphism yields an efficient method for determining the complete weight enumerator of any code generated by a circulant matrix.     

Indecomposable triple systems

A t-design (λ, t, d, n) is a system $\text{B}$ of sets of size d from an n-set S, such that each t subset of S is contained in exactly λ elements of $\text{B}$. A t-design is indecomposable (written IND(λ, t, d, n)) if there does not exist a subset $\text{B}$ ? $\text{B}$ such that $\text{B}$ is a (λ, t, d, n) for some λ, 1 ? λ < λ. A triple system is a (λ; 2, 3, n). Recursive and constructive methods (several due to Hanani) are employed to show that: (1) an IND(2; 2, 3, n) exists for n ≡ 0, 1 (mod 3), n ? 4 and n ≡ 7 (designs of Bhattacharya are used here), (2) an IND(3; 2, 3, n) exists for n odd, n ? 5, (3) if an IND(λ, 2, 3, n) exists, n odd, then there exists an infinite number of indecomposable triple systems with that λ.     

On the irreducibility of multivariate subresultants

Let P₁,…,P_n be generic homogeneous polynomials in n variables of degrees d₁,…,d_n respectively. We prove that if ν is an integer satisfying ∑_i=1ⁿd_i?n+1?min{d_i}<ν, then all multivariate subresultants associated to the family P₁,…,P_n in degree ν are irreducible. We show that the lower bound is sharp. As a byproduct, we get a formula for computing the residual resultant of $\text{ρ?ν+n?1}\text{n?1}$ smooth isolated points in $\text{P}{}^{\mathrm{<mspace\; sp="0.2"\; width="2px"\; linebreak="nobreak"\; is="true"></mspace><mtext>n?1</mtext>}}\text{.}$To cite this article: L. Busé, C. D'Andrea, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Extreme points in sets of positive linear maps on B(H)

Three main results are obtained: (1) If $\text{D}$ is an atomic maximal Abelian subalgebra of $\text{B}$($\text{H}$), $\text{P}$ is the projection of $\text{B}$($\text{H}$) onto $\text{D}$ and h is a complex homomorphism on $\text{D}$, then h ° $\text{P}$ is a pure state on $\text{B}$($\text{H}$). (2) If {P_n} is a sequence of mutually orthogonal projections with rank(P_n) = n and ∑ P_n = I, $\text{P}$ is the projection of $\text{B}$($\text{H}$) onto {P_n}″ given by P(T)=∑trace_n(T)P_n and h is a homomorphism on {P_n}″ such that h(P_n) = 0 for all n then h ° $\text{P}$ induces a type II_∞ factor representation of the Calkin algebra. (3) If $\text{M}$ is a nonatomic maximal Abelian subalgebra of $\text{B}$($\text{H}$) then there is an atomic maximal Abelian subalgebra $\text{D}$ of $\text{B}$($\text{H}$) and a large family {Φ_α} of ¹-homomorphisms from $\text{D}$ onto $\text{M}$ such that for each α, Φ_α ° $\text{P}$ is an extreme point in the set of projections from $\text{B}$($\text{H}$) onto $\text{M}$. (Here $\text{P}$ denotes the projection of $\text{B}$($\text{H}$) onto $\text{D}$.)     

Characterization of projective graphs

We denote the distance between vertices x and y of a graph by d(x, y), and p_ij(x, y) = ∥ {z : d(x, z) = i, d(y, z) = j} ∥. The (s, q, d)-projective graph is the graph having the s-dimensional subspaces of a d-dimensional vector space over GF(q) as vertex set, and two vertices x, y adjacent iff $\text{dim}\text{(x ? y) = s ? 1}$. These graphs are regular graphs. Also, there exist integers λ and μ > 4 so that μ is a perfect square, p₁₁(x, y) = λ whenever d(x, y) = 1, and p₁₁(x, y) = μ whenever d(x, y) = 2. The (s, q, d)-projective graphs where $\text{2d}\text{3}\text{≤ s < d ? 2}$ and $\text{(s, q, d) ≠ (}\text{2d}\text{3}\text{, 2, d)}$, are characterized by the above conditions together with the property that there exists an integer r satisfying certain inequalities.     

Some partitions associated with a partially ordered set

For any partially ordered set P, let $\text{d}{}_{\mathrm{k}}\text{(P)(}\text{d}\text{?}{}_{\mathrm{k}}\text{(P))}$ denote the cardinality of the largest subset of P obtained by taking the union of k antichains (chains). Then there exists a partition Δ = {Δ_l ? Δ₂ > … ? Δ_l} of | P | such that d_k(P) = Δ₁ + Δ₂ + … + Δ_k and $\text{d}\text{?}{}_{\mathrm{k}}\text{(P) = Δ}{}_1{}^1\text{+ Δ}{}_2{}^1\text{+ … + Δ}{}_{\mathrm{k}}{}^1$ for each k, where $\text{Δ}{}^1$ denotes the partition conjugate to Δ. This result can be used to prove a general class of “Dilworth-type” theorems for subfamilies of P.     

Über die Wurzelschranke für das Minimalgewicht von codes

Let d be the minimum distance of an (n, k) code $\text{C}$, invariant under an abelian group acting transitively on the basis of the ambient space over a field F with char F × n. Assume that $\text{C}$ contains the repetition code, that dim($\text{C}$ ∏ $\text{C}$^⊥) = k ? 1 and that the supports of the minimal weight vectors of $\text{C}$ form a 2-design. Then d² ? d + 1 ? n with equality if and only if the design is a projective plane of order d ? 1. The case d² ? d + 1 = n can often be excluded with Hall's multiplier theorem on projective planes, a theorem which follows easily from the tools developed in this paper Moreover, if d² ? d + 1 > n and F = GF(2) then (d ? 1)² ? n. Examples are the generalized quadratic residue codes.     

An upper bound for the diameter of a polytope

The distance between two vertices of a polytope is the minimum number of edges in a path joining them. The diameter of a polytope is the greatest distance between two vertices of the polytope. We show that if P is a d-dimensional polytope with n facets, then the diameter of P is at most $\text{1}\text{3}\text{2}{}^{\mathrm{d?3}}\text{(n?d+}\text{5}\text{2}\text{)}$.     

Sur l'équation divu=fOn the equation divu=f

The main result is the following. Let $\text{Ω}$ be a bounded Lipschitz domain in $\text{R}{}^{\mathrm{d}}$, d?2. Then for every $\text{f∈}\text{L}{}^{\mathrm{d}}\text{(Ω)}$ with ∫f=0, there exists a solution $\text{u∈}\text{C}{}^0\text{(}\text{Ω}\text{)∩}\text{W}{}^{\mathrm{1,d}}\text{(Ω)}$ of the equation divu=f in $\text{Ω}$, satisfying in addition u=0 on $\text{?Ω}$ and the estimate

where C depends only on $\text{Ω}$. However one cannot choose u depending linearly on f. To cite this article: J. Bourgain, H. Brezis, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 973–976.     

Sufficiency and invariance

Suppose that a statistical decision problem is invariant under a group of transformations g?G. T (X) is equivariant if there exists $\text{g}{}^1\text{? G}{}^1$ such that $\text{T(g(X)) = g}{}^1\text{(T((X))}$. We show that the minimal sufficient statistic is equivalent and that if T(X) is an equivariant sufficient statistics and d(X) is invariant under G, then $\text{d}{}^1\text{(T) = Ed(X)∥T}$ is invariant under $\text{G}{}^1$.