Classes de Chern Des Ensembles Analytiques

Let V be a compact complex analytic subset of a non-singular holomorphic manifold M. Assume that V has pure complex dimension n. Denote by V₀ its regular part, and by [V] its fundamental class in H_2n(V; ). If V is a locally complete intersection (LCI), it is known that the normal bundle N_{V_0} in M to V₀ in M has a natural extension N_V to all of V, so that we can define its Chern classes c^(*)(N_V) in cohomology, as well as the Chern classes c_vir^(*). If V is a locally complete intersection (LCI), it is known that the normal bundle N_{V_0} in M to V₀ in M has a natural extension N_V to all of V, so that we can define its Chern classes c^(*)(N_V) in cohomology, as well as the Chern classes c_vir^(*) (V) of the virtual tangent bundle T_vir(V):=[TM|_V - N_V] in the K-theory K⁰(V). This has applications

Approximating Probability Distributions Using Small Sample Spaces

We formulate the notion of a "good approximation" to a probability distribution over a finite abelian group ?. The quality of the approximating distribution is characterized by a parameter ɛ which is a bound on the difference between corresponding Fourier coefficients of the two distributions. It is also required that the sample space of the approximating distribution be of size polynomial in and 1/ɛ. Such approximations are useful in reducing or eliminating the use of randomness in certain randomized algorithms. We demonstrate the existence of such good approximations to arbitrary distributions. In the case of n random variables distributed uniformly and independently over the range , we provide an efficient construction of a good approximation. The approximation constructed has the property that any linear combination of the random variables (modulo d) has essentially the same behavior under the approximating distribution as it does under the uniform distribution over . Our analysis is based on Weil's character sum estimates. We apply this result to the construction of a non-binary linear code where the alphabet symbols appear almost uniformly in each non-zero code-word. Received: September 22, 1990/Revised: First revision November 11, 1990; last revision November 10, 1997     

On the Sparsity Order of a Graph and Its Deficiency in Chordality

Given a graph G on n nodes, let denote the cone consisting of the positive semidefinite matrices (with real or complex entries) having a zero entry at every off-diagonal position corresponding to a non edge of G. Then, the sparsity order of G is defined as the maximum rank of a matrix lying on an extreme ray of the cone . It is known that the graphs with sparsity order 1 are the chordal graphs and a characterization of the graphs with sparsity order 2 is conjectured in [1] in the real case. We show in this paper the validity of this conjecture. Moreover, we characterize the graphs with sparsity order 2 in the complex case and we give a decomposition result for the graphs with sparsity order in both real and complex cases. As an application, these graphs can be recognized in polynomial time. We also indicate how an inequality from [17] relating the sparsity order of a graph and its minimum fill-in can be derived from a result concerning the dimension of the faces of the cone . Received August 31, 1998/Revised April 26, 2000     

Deterministic Routing With Bounded Buffers: Turning Offline Into Online Protocols

In this paper we present a deterministic protocol for routing arbitrary permutations in arbitrary networks. The protocol is analyzed in terms of the size of the network and the routing number of the network. Given a network H of n nodes, the routing number of H is defined as the maximum over all permutations on {1, ..., n} of the minimal number of steps to route offline in H. We show that for any network H of size n with routing number R our protocol needs time to route any permutation in H using only constant size edge buffers. This significantly improves all previously known results on deterministic routing. In particular, our result yields optimal deterministic routing protocols for arbitrary networks with diameter or bisection width , constant. Furthermore we can extend our result to deterministic compact routing. This yields, e.g., a deterministic routing protocol with runtime O(R logn) for arbitrary bounded degree networks if only O(logn) bits are available at each node for storing routing information. Our protocol is a combination of a generalized ``routing via simulation' technique with an new deterministic protocol for routing h-relations in an extended version of a multibutterfly network. This protocol improves upon all previous routing protocols known for variants of the multibutterfly network. The ``routing via simulation' technique used here extends a method previously introduced by the authors for designing compact routing protocols. Received July 18, 1997     

The Clique Complex and Hypergraph Matching

The width of a hypergraph is the minimal for which there exist such that for any , for some . The matching width of is the minimal such that for any matching there exist such that for any , for some . The following extension of the Aharoni-Haxell matching Theorem [3] is proved: Let be a family of hypergraphs such that for each either or , then there exists a matching such that for all . This is a consequence of a more general result on colored cliques in graphs. The proofs are topological and use the Nerve Theorem. Received June 14, 1999     

Approximate Homomorphisms II: Group Homomorphisms

Received October 13, 1998     

Totally Odd -subdivisions in 4-chromatic Graphs

We prove the conjecture made by Bjarne Toft in 1975 that every 4-chromatic graph contains a subdivision of in which each edge of corresponds to a path of odd length. As an auxiliary result we characterize completely the subspace of the cycle space generated by all cycles through two fixed edges. Toft's conjecture was proved independently in 1995 by Wenan Zang. Received May 26, 1998     

Tame group actions on central simple algebras

We study actions of linear algebraic groups on finite-dimensional central simple algebras. We describe the fixed algebra for a broad class of such actions.