Characterizing compact unions of two starshaped sets inR d

SetS inR ^d has propertyK ₂ if and only ifS is a finite union ofd-polytopes and for every finite setF in bdryS there exist points c₁,c₂ (depending onF) such that each point ofF is clearly visible viaS from at least one c_i,i = 1,2. The following characterization theorem is established: Let , d2. SetS is a compact union of two starshaped sets if and only if there is a sequence {S _j } converging toS (relative to the Hausdorff metric) such that each setS _j satisfies propertyK ₂. For , the sufficiency of the condition above still holds, although the necessity fails.     

Dense graphs and edge reconstruction

By a well-known result of Nash-Williams if a graphG is not edge reconstructible, then for all ,|A||E(G)| mod 2 we have a permutation ofV(G) such thatE(G)E(G)=A. Here we construct infinitely many graphsG having this curious property and more than edges.Research (partially) supported by Hungarian National Foundation for Scientific Research Grant No.T016389.     

Automatic structures,rational growth,and geometrically finite hyperbolic groups

Summary We show that the set of equivalence classes of synchronously automatic structures on a geometrically finite hyperbolic groupG is dense in the product of the sets over all maximal parabolic subgroupsP. The set of equivalence classes of biautomatic structures onG is isomorphic to the product of the sets over the cusps (conjugacy classes of maximal parabolic subgroups) ofG. Each maximal parabolicP is a virtually abelian group, so and were computed in [NS1].We show that any geometrically finite hyperbolic group has a generating set for which the full language of geodesics forG is regular. Moreover, the growth function ofG with respect to this generating set is rational. We also determine which automatic structures on such a group are equivalent to geodesic ones. Not all are, though all biautomatic structures are.Oblatum 14-VI-1993 & 4-I-1994Both authors acknowledge support from the NSF for this research.     

Irrepresentability of short semilattices by euclidean subspaces

A semilatticeS isrepresentable by subspaces of R ^k if, to eachx S we can assign a subspace so thatx y=z inS if and only if . Every height-2 semilattice is representable inR ². We show that for everyk there is a height-3 semilattice which is not representable by subspaces ofR ^k.Presented by J. Berman.Research supported in part by the National Science Foundation.Research supported in part by the Office of Naval Research.     

Covering cycles andk-term degree sums

We show that if , for every stable set , then the vertex set ofG can be covered withk–1 cycles, edges or vertices. This settles a conjecture by Enomoto, Kaneko and Tuza.     

Some excluded-minor theorems for a class of polymatroids

Problems involving representability are among the most frequently studied of all the problems in matroid theory. This paper considers the corresponding class of problems for polymatroids. A polymatroidh on the setS is representable over a free matroid or is Boolean if there is a map fromS into the set of subsets of a setV which preserves rank, that is for all subsetsA ofS, . The class of Boolean polymatroids is minor-closed and in this paper we investigate the excluded minors of this class. In particular, we determine all such Boolean excluded minors that are 2-polymatroids.This research was partially supported by a grant from the Louisiana Education Quality Support Fund Through the Board of RegentsThis research was supported by a grant from the Commonwealth of Australia through the Australian Research Council     

Some results on geodesic mappings of Riemannian manifolds satisfying the conditionR.R.=Q(S,R)

In this paper geodesically corresponding metricsg and on a manifoldM, dim 5, under the assumption that the tensorsR andS of the metricg satisfyR.R=Q(S, R), are considered. It is stated that the corresponding tensors and of not necessarily must satisfy . Certain relations between the curvatures ofg and are obtained.Supported by a post-doctoral fellowship of the researchcouncil of the KU Leuven; Bitnet FGBDA3O at BLEKUL11     

Backward error analysis for totally positive linear systems

Summary Gauss elimination applied to ann×n matrixA in floating point arithmetic produces (if successful) a factorization which differs fromA by no more than , for some of ordern times the unit roundoff. IfA is totally positive, then both computed factors and are nonnegative for sufficiently small unit roundoff and one obtains pleasantly small bounds for the perturbation inA which would account for the rounding errors committed in solvingAx=b forx by Gauss eliminationwithout pivoting. It follows that the banded linear system for the B-spline coefficients of an interpolating spline function can be solved safely by Gauss elimination without pivoting.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MPS72-00381 A01.     

A vector-sum theorem in two-dimensional space

Given a finite setX of vectors from the unit ball of the max norm in the twodimensional space whose sum is zero, it is always possible to writeX = {x₁, , x_n} in such a way that the first coordinates of each partial sum lie in [–1, 1] and the second coordinates lie in [–C, C] whereC is a universal constant.     

The number oft-wise balanced designs

We prove that the number oft-wise balanced designs of ordern is asymptotically , provided that blocks of sizet are permitted. In the process, we prove that the number oft-profiles (multisets of block sizes) is bounded below by and above by for constants c₂>c₁>0.     

The partial complement of graphs

For a graphG, the switched graphS _v (G) ofG at a vertexv is the graph obtained fromG by deleting the edges ofG incident withv and adding the edges of incident withv. Properties of graphs whereS _v (G) G or are studied. This concept is extended to the partial complementS _H (G) where H . The investigation here centers around the existence of setsH for whichS _H (G) G. A parameter is introduced which measures how near a graph is to being self-complementary.     

Visible shorelines inR d

Summary LetC be a closed set inR ^d and letj be a fixed integer,j 1. The setS R ^d ~C is said to have aj-partition relative toC if there existj or fewer pointsc ₁,, c _j ofC such that each point ofS sees via the complement ofC at least one pointc _i. For every triple of integersd, p, j withd 0, p d + 1, j 1, there exists a smallest integerf(d, p, j) such that the following is true: IfC is a convexd-polytope inR ^d havingp vertices and ifS R ^d ~C, S has aj-partition relative toC if and only if everyf(d, p, j)-member subset of S has such a partition.ForC a convex polytope inR ² andS R ² ~C, all points ofS see via the complement ofC a common neighborhood in the boundary ofC if and only if every three points ofS see via the complement ofC such a neighborhood.A weak analogue of this result holds for arbitrary compact convex sets inR ^d .     

Remarks on power structures

Chris Brink, in his paper,Power Structures, describes the construction ofgeneralized quotient algebras. IfA is any algebra, the corresponding generalized quotient algebraA/R is defined for every value-preserving relation . As we will see in the present paper, in order to make the corresponding operations on the setA/R well-defined, it is not enough forR to be value-preserving. The only redundancy in the definition of the usual quotient algebra is symmetry.Presented by G. Grätzer.     

Inclusion-exclusion: Exact and approximate

It is often required to find the probability of the union of givenn eventsA ₁ ,...,A _n . The answer is provided, of course, by the inclusion-exclusion formula: Pr(A _i )= _i – _i<j Pr(A _i A _j )±.... Unfortunately, this formula has exponentially many terms, and only rarely does one manage to carry out the exact calculation. From a computational point of view, finding the probability of the union is an intractable, #P-hard problem, even in very restricted cases. This state of affairs makes it reasonable to seek approximate solutions that are computationally feasible. Attempts to find such approximate solutions have a long history starting already with Boole [1]. A recent step in this direction was taken by Linial and Nisan [4] who sought approximations to the probability of the union, given the probabilities of allj-wise intersections of the events forj=1,...k. The developed a method to approximate Pr(A _i ), from the above data with an additive error of exp . In the present article we develop an expression that can be computed in polynomial time, that, given the sums _|S|=j Pr( _iS A _i ) forj=1,...k, approximates Pr(A _i ) with an additive error of exp . This error is optimal, up to the logarithmic factor implicit in the notation.The problem of enumerating satisfying assignments of a boolean formula in DNF formF=v _l ^m C _i is an instance of the general problem that had been extensively studied [7]. HereA _i is the set of assignments that satisfyC _i , and Pr( _iS A _i )=a _S /2ⁿ where _iS C _i is satisfied bya _S assignments. Judging from the general results, it is hard to expect a decent approximation ofF's number of satisfying assignments, without knowledge of the numbersa _S for, say, all cardinalities . Quite surprisingly, already the numbersa _S over |S|log(n+1)uniquely determine the number of satisfying assignments for F.We point out a connection between our work and the edge-reconstruction conjecture. Finally we discuss other special instances of the problem, e.g., computing permanents of 0,1 matrices, evaluating chromatic polynomials of graphs and for families of events whose VC dimension is bounded.Work supported in part by a grant of the Binational Israel-US Science Foundation.Work supported in part by a grant of the Binational Israel-US Science Foundation and by the Israel Science Foundation.     

A note on the 5-person traveling salesman game

LetN=1,2,...,n be a set of customers andG=(N {0},E) an undirected connected graph with non-negative edge lengths. 0 is the home location of a salesman who visits the customers inN. Each subset can invite the salesman to visit its members only. The costc(S) of coalitionS is the length of a shortest tour that starts in 0, visits each customer inS at least once and returns to 0. The cooperative cost game defined in this way is called a (symmetric) traveling salesman game (TSG).The core of a TSG can be empty when ¦N¦ 6 and it was proved that it always has a non-empty core when ¦N¦ 4. In this note we shall prove that a TSG always has a non-empty core when ¦N¦=5.     

On the isomorphisms and automorphism groups of circulants

Denote byC _n(S) the circulant graph (or digraph). LetM be a minimal generating element subset ofZ _n, the cyclic group of integers modulon, and In this paper, we discuss the problems about the automorphism group and isomorphisms ofC _n(S). When M S , we determine the automorphism group ofC _n(S) and prove that for any T if and only ifT = S, where is an integer relatively prime ton. The automorphism groups and isomorphisms of some other types of circulant graphs (or digraphs) are also considered. In the last section of this paper, we give a relation between the isomorphisms and the automorphism groups of circulants.     

On a theorem of Seidel and Walsh

Given a sequence ( _n ) _n in with there are functions such that , is a dense subset of , and the set of functions with this property is residual in . We will show that in and some related Banach spaceX there are functionsf with is dense in , and we will give a sufficient condition when the set of such functions is residual inX.     

A stability test for real polynomials

Summary By the argument principle the number of zeros inside of the unit circle of a real polynomial , can be estimated by the variation of the argument ofp _n (exp(it)) ift varies from 0 to . This variation has its maximal value n iff then distinct zeros of are separated by then–1 distinct zeros of . Now from Sturm sequence techniques in connection with special properties of the Chebyshev polynomials there results a very simple stability test.Dedicated to Professor Dr. Wilhelm Niethammer on his sixtieth birthday (December 2, 1993)     

On semianalytic subsets of rigid analytic varieties

We show some topological properties of semianalytic subsets of rigid analytic varieties: curve selection lemma, the closure of a semianalytic subsetS is semianalytic, for every quasi-compact morphismf. As an application we show that a morphismf: X Y of rigid analytic varieties is open at a pointx X if and only if SpecO _X,x SpecO _Y,f(x) is surjective.     

Extensions of thep-adic fields generated by the roots of a single polynomial in two variables

One of the generalizations of the Hilbert's Irreducibility Theorem states that if F(X, Y) is irreducible in Q _p [X, Y] then, for almost every n N, F(n, Y) is irreducible in Q _p [Y]. Let E{p, d} be the set of all the extensions of Q _p of degree d. We shall prove that for each subset S E{p, d}there exist polynomials F(X, Y) such that the set of extensions of Q _p generated by the roots of F (n, Y)is exactly S. Moreover we shall prove that all the functions f are induced by polynomials F(X) Z[X].M. S. C. N. 11S05, (11S15).The author would like to thank Prof. Roberto Dvornicich for several useful conversations and advices.