Embeddings of bipartite graphs

If G is a bipartite graph with bipartition A, B then let G_m,n(A, B) be obtained from G by replacing each vertex a of A by an independent set a₁, …, a_m, each vertex b of B by an independent set b₁,…, b_n, and each edge ab of G by the complete bipartite graph with edges a_ib_j (1 ≤ i ≤ m and 1 ≤ j ≤ n). Whenever G has certain types of spanning forests, then cellular embeddings of G in surfaces S may be lifted to embeddings of G_m,n(A, B) having faces of the same sizes as those of G in S. These results are proved by the technique of “excess-current graphs.” They include new genus embeddings for a large class of bipartite graphs.     

Improved bounds on weak ε-nets for convex sets

LetS be a set ofn points in ℝ ^d . A setW is aweak ε-net for (convex ranges of)S if, for anyT⊆S containing εn points, the convex hull ofT intersectsW. We show the existence of weak ε-nets of size , whereβ ₂=0,β ₃=1, andβ _d ≈0.149·2 ^d-1(d-1)!, improving a previous bound of Alonet al. Such a net can be computed effectively. We also consider two special cases: whenS is a planar point set in convex position, we prove the existence of a net of sizeO((1/ε) log^1.6(1/ε)). In the case whereS consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of sizeO(1/ε), which improves a previous bound of Capoyleas. Work by Bernard Chazelle has been supported by NSF Grant CCR-90-02352 and the Geometry Center. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-89-21421. Work by Michelangelo Grigni has been supported by NSERC Operating Grants and NSF Grant DMS-9206251. Work by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Emo Welzl and Micha Sharir has been supported by a grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development. Work by Micha Sharir has also been supported by NSF Grant CCR-91-22103, and by a grant from the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Extremal cover times for random walks on trees

Let C_ν(T) denote the “cover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C_ν(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2n In n) by showing that C_ν(T) is minimized when T is a star and v is one of its leaves. In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).     

On Finite Complete Presentations and Exact Decompositions of Semigroups

We prove that given a finite (zero) exact right decomposition (M, T) of a semigroup S, if M is defined by a finite complete presentation, then S is also defined by a finite complete presentation. Exact right decompositions are natural generalizations to semigroups of coset decompositions in groups. As a consequence, we deduce that any Zappa–Szép extension of a monoid defined by a finite complete presentation, by a finite monoid, is also defined by such a presentation.

It is also proved that a semigroup M ⁰[A; I, J; P], where A and P satisfy some very general conditions, is also defined by a finite complete presentation.     

Generalisation des fonctions analytiques hyperboliques

We generalize the results previously given [1], by puting u = a x + ɛ b y by (a and b are real and positive, ɛ is a number of Clifford not real having a square equal to 1. Consider x and y being the coordinates of a point M, the axises being rectangular). The analytic functions f (u) are defined by

Partially Ordered Monoids Generated by Operators H , S , P , and by H , S , P f Are Isomorphic

Let I , H , S , P , P _f be the usual operators on classes of algebras of the same type (P _f for filtered products). The partially ordered monoid generated by the operators H , S , P with respect to composition of operators, I as an identity element, and a natural ordering between operators is described by Pigozzi (Algebra Universalis 2 (1972), 346—353). Let us denote by \cal M =\langle H, S, P\rangle and by \cal M _f =\langle H, S, P _f \rangle the partially ordered monoids generated by {H, S, P} and by {H, S, P _f } respectively. The aim of this paper is to prove that \cal M is isomorphic to \cal M _f . October 29, 1999     

The number of labeled graphs placeable by a given permutation

Let S be a finite set and σ a permutation on S. The permutation σ* on the set of 2-subsets of S is naturally induced by σ. Suppose G is a graph and V(G), E(G) are the vertex set, the edge set, respectively. Let V(G) = S. If E(G) and σ*(E(G)), the image of E(G) by σ*, have no common element, then G is said to be placeable by σ. This notion is generalized as follows. If any two sets of {E(G), (σ¹)*(E(G)),…,(σ^l−1)* (E(G))} have no common element, then G is said to be I-placeable by σ. In this paper, we count the number of labeled graphs which are I-placeable by a given permutation. At first, we introduce the interspaced Ith Fibonacci and Lucas numbers. When I = 2 these numbers are the ordinary Fibonacci and Lucas numbers. It is known that the Fibonacci and Lucas numbers are rounded powers. We show that the interspaced Ith Fibonacci and Lucas numbers are also rounded powers when I = 3. Next, we show the number of labeled graphs which are I-placeable by a given permutation is a product of the interspaced Ith Lucas numbers. Finally, using a property of the generalized binomial series, we count the number of labeled graphs of size k which are I-placeable by σ. © 1996 John Wiley & Sons, Inc.     

Automatic continuity of intertwining linear operators on Banach spaces

We extend the automatic continuity theory for linear operators θ:X→Y which intertwine two given bounded linear operatorsT∈L X andS∈L Y on Banach spacesX andY, respectively. This is done both by relaxing the intertwining conditionSθ=θT and by enlarging the classes of operatorsT, resp.S, well beyond the decomposable operators. Among the operatorsS captured by these extensions are multipliers on commutative semi-simple Banach algebras. dedicated to George Maltese on his 60th birthday     

Vertical decompositions for triangles in 3-space

We prove that, for any constant ɛ>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n ^2+ɛ +K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to beO(n ^2+ɛ ). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n ² logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations. The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(nλ _q (n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, λ _q (n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the first algorithm. Mark de Berg was supported by the Dutch Organization for Scientific Research (N.W.O.), and by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity). Leonidas Guibas was supported by NSF Grant CCR-9215219, by a grant from the Stanford SIMA Consortium, by NSF/ARPA Grant IRI-9306544, and by grants from the Digital Equipment, Mitsubishi, and Toshiba Corporations. Dan Halperin was supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. A preliminary version of this paper appeared inProc. 10th ACM Symposium on Computational Geometry, 1994, pp. 1–10.     

Automorphisms of Relatively Free Nilpotent Lie Algebras

Let L be a relatively free nilpotent Lie algebra over ? of rank n and class c, with n ≥ 2; freely generated by a set 𝒵. Give L the structure of a group, denoted by R, by means of the Baker–Campbell–Hausdorff formula. Let G be the subgroup of R generated by the set 𝒵 and N _Aut(L)(G) the normalizer in Aut(L) of the set G. We prove that the automorphism group of L is generated by GL _n (?) and N _Aut(L)(G). Let H be a subgroup of finite index in Aut(G) generated by the tame automorphisms and a finite subset X of IA-automorphisms with cardinal s. We construct a set Y consisting of s + 1 IA-automorphisms of L such that Aut(L) is generated by GL _n (?) and Y. We apply this particular method to construct generating sets for the automorphism groups of certain relatively free nilpotent Lie algebras.     

Book Reviews

Book reviewed in this article: What Can It Be? series Jacqueline A. Ball and Ann D. Hardy NOVAbook series The City Kid's Field Guide by Ethan Herberman Signs of the Apes, Songs of the Whales: Adventuresin Human-Animal Communicationsby George & Linda Harvar Junk in Space by Richard Maurer Peak Performance; Sports, Science, and the Body in Action by Emily Isberg Simon & Shuster Discovering Robert Scott Root-Bernstein     

Local error estimation for singly-implicit formulas by two-step Runge-Kutta methods

In this paper it is shown that the local discretization error ofs-stage singly-implicit methods of orderp can be estimated by embedding these methods intos-stage two-step Runge-Kutta methods of orderp+1, wherep=s orp=s+1. These error estimates do not require any extra evaluations of the right hand side of the differential equations. This is in contrast with the error estimation schemes based on embedded pairs of two singly-implicit methods proposed by Burrage.The work of A. Bellen and M. Zennaro was supported by the CNR and MPI. The work of Z. Jackiewicz was supported by the CNR and by the NSF under grant DMS-8520900.     

Superpolynomial Size Set-systems with Restricted Intersections mod 6 and Explicit Ramsey Graphs

Dedicated to the memory of Paul Erdős We construct a system of subsets of a set of n elements such that the size of each set is divisible by 6 but their pairwise intersections are not divisible by 6. The result generalizes to all non-prime-power moduli m in place of m=6. This result is in sharp contrast with results of Frankl and Wilson (1981) for prime power moduli and gives strong negative answers to questions by Frankl and Wilson (1981) and Babai and Frankl (1992). We use our set-system to give an explicit Ramsey-graph construction, reproducing the logarithmic order of magnitude of the best previously known construction due to Frankl and Wilson (1981). Our construction uses certain mod m polynomials, discovered by Barrington, Beigel and Rudich (1994). Received January 15, 1996/Revised August 2, 1999     

Parallel Dixon Matrices by Bracket

It is known that the Dixon matrix can be constructed in parallel either by entry or by diagonal. This paper presents another parallel matrix construction, this time by bracket. The parallel by bracket algorithm is the fastest among the three, but not surprisingly it requires the highest number of processors. The method also shows analytically that the Dixon matrix has a total of m(m+1)²(m+2)n(n+1)²(n+2)/36 brackets but only mn(m+1)(n+1)(mn+2m+2n+1)/6 of them are distinct.     

On two questions about feasibly constructive arithmetic

IPV is the intuitionistic theory axiomatized by Cook's equational theory PV plus PIND on NP‐formulas. Two extensions of IPV were introduced by Buss and by Cook and Urquhart by adding PIND for formulas of the form A(x) ∨ B, respectively ¬¬A(x), where A(x) is NP and x is not free in B. Cook and Urquhart posed the question of whether these extensions are proper. We show that in each of the two cases the extension is proper unless the polynomial hierarchy collapses.     

Localisation in rings equipped with a solvable Lie algebra action

Let k be an algebraically closed uncountable field of characteristic 0,g a finite dimensional solvable k-Lie algebraR a noetherian k-algebra on which g acts by k-derivationsU(g) the enveloping algebra of g,A=R*g the crossed product of R by U(g)P a prime ideal of A and Ω(P) the clique of P. Suppose that the prime ideals of the polynomial ring R[x] are completely prime. If R is g-hypernormal, then Ω(P) is classical. Denote by A_T the localised ring and let M be a primitive ideal of A_T Set Q=P∩R In this note, we show that if R is a strongly (R,g)-admissible integral domain and if QR_Q is generated by a regular g-centralising set of elements, then

(1)M is generated by a regular g-semi-invariant normalising set of elements of cardinald = dim (R_Q 0 + ∣X_A (P)∣

(2)d gldim(A_T ) = Kdim(A_T ) = ht(M) = ht(P).     

On Genuine Bernstein–Durrmeyer Operators

We continue the studies on the so–called genuine Bernstein–Durrmeyer operators U _n by establishing a recurrence formula for the moments and by investigating the semigroup T(t) approximated by U _n . Moreover, for sufficiently smooth functions the degree of this convergence is estimated. We also determine the eigenstructure of U _n , compute the moments of T(t) and establish asymptotic formulas. Received: January 26, 2007.     

Embedding nearly-spanning bounded degree trees

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1 − ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 − ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above. Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Sharpening the LYM inequality

The level sequence of a Sperner familyF is the sequencef(F)={f _i (F)}, wheref _i (F) is the number ofi element sets ofF . TheLYM inequality gives a necessary condition for an integer sequence to be the level sequence of a Sperner family on ann element set. Here we present an indexed family of inequalities that sharpen theLYM inequality.Research supported in part by Alexander v. Humboldt-StiftungResearch supported in part by NSF under grant DMS-86-06225 and AFOSR grant OSR-86-0078Research supported in part by NSF grant CCR-8911388Research supported in part by OTKA 327 0113     

Topological properties of the multifunction space <Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">X</Emphasis>) of cusco maps

A set-valued mapping F from a topological space X to a topological space Y is called a cusco map if F is upper semicontinuous and F(x) is a nonempty, compact and connected subset of Y for each x ∈ X. We denote by L(X), the space of all subsets F of X × ℝ such that F is the graph of a cusco map from the space X to the real line ℝ. In this paper, we study topological properties of L(X) endowed with the Vietoris topology. The second author is supported by the SPM fellowship awarded by the Council of Scientific and Industrial Research, India.