Zur Beziehung zwischen Basen und Vektoren kürzester Länge in Gittern

LetR be an order of an algebraic number field of degreen over ,V ann-dimensional real vector space and the class of lattices inV which are free rank 1 modules overR. For certain ordersR and distance functionsd onV a method of computingd-minimal vectors of is described; further it is shown how to constructs anR-basis for by comparing thed-length of vectors of . An application to the computation of fundamental units and class numbers of real abelian number fields is mentioned.     

Krasnosel'skii numbers for bounded finitely starlike sets inR d

For eachk andd, 1kd, definef(d, d)=d+1 andf(d, k)=2d if 1kd–1. The following results are established:Let be a uniformly bounded collection of compact, convex sets inR ^d . For a fixedk, 1kd, dim {MM in }k if and only if for some > 0, everyf(d, k) members of contain a commonk-dimensional set of measure (volume) at least.LetS be a bounded subset ofR ^d . Assume that for some fixedk, 1kd, there exists a countable family of (k–l)-flats {H _i :i1} inR ^d such that clS S {H_i i 1 } and for eachi1, (clS S) H _i has (k–1) dimensional measure zero. Every finite subset ofS sees viaS a set of positivek-dimensional measure if and only if for some>0, everyf(d,k) points ofS see viaS a set ofk-dimensional measure at least .The numbers off(d,d) andf(d, 1) above are best possible.Supported in part by NSF grant DMS-8705336.     

Representation of linearly additive random fields

Summary Chentsov type representation theorem is proved for stochastically continuous, linearly additive, infinitely divisible random field without Gaussian component, where a random fieldX={X(t), tR ^d } is called linearly additive if the stochastic process defined by ()=X(a+b), R, has independent increments for every pair(a, b), a, bR ^d . In passing it is shown that there exists a natural one-to-one correspondence between stochastically continuous, linearly additive Poisson random fields onR ^d and locally finite, bundleless measures on the space of all (d-1)-hyperplanes inR ^d . The latter result is closely related to Ambartzumian's theorem on the representation of linearly additive pseudometrics in the plane.     

Hypersurface variations are maximal,I

Summary The variation of Hodge structure defined by the natural family of hypersurfaces of degreed and dimensionn is maximal if the cohomology has Hodge level >1. There is a small list of hypersurfaces of level one which give non-maximal variations: plane curves of degreed5, cubics of dimension 3 and 5, and quartic threefolds.Research partially supported by the National Science Foundation     

The tree number of a graph with a given girth

A family of subtrees of a graphG whose edge sets form a partition of the edge set ofG is called atree decomposition ofG. The minimum number of trees in a tree decomposition ofG is called thetree number ofG and is denoted by(G). It is known that ifG is connected then(G) |G|/2. In this paper we show that ifG is connected and has girthg 5 then(G) |G|/g + 1. Surprisingly, the case wheng = 4 seems to be more difficult. We conjecture that in this case(G) |G|/4 + 1 and show a wide class of graphs that satisfy it. Also, some special graphs like complete bipartite graphs andn-dimensional cubes, for which we determine their tree numbers, satisfy it. In the general case we prove the weaker inequality(G) (|G| – 1)/3 + 1.     

Rubber bands,convex embeddings and graph connectivity

We give various characterizations ofk-vertex connected graphs by geometric, algebraic, and physical properties. As an example, a graphG isk-connected if and only if, specifying anyk vertices ofG, the vertices ofG can be represented by points of ^k–1 so that nok are on a hyper-plane and each vertex is in the convex hull of its neighbors, except for thek specified vertices. The proof of this theorem appeals to physics. The embedding is found by letting the edges of the graph behave like ideal springs and letting its vertices settle in equilibrium.As an algorithmic application of our results we give probabilistic (Monte-Carlo and Las Vegas) algorithms for computing the connectivity of a graph. Our algorithms are faster than the best known (deterministic) connectivity algorithms for allkn, and for very dense graphs the Monte Carlo algorithm is faster by a linear factor.     

On thel-connectivity of a graph

For an integerl 2, thel-connectivity of a graphG is the minimum number of vertices whose removal fromG produces a disconnected graph with at leastl components or a graph with fewer thanl vertices. A graphG is (n, l)-connected if itsl-connectivity is at leastn. Several sufficient conditions for a graph to be (n, l)-connected are established. IfS is a set ofl( 3) vertices of a graphG, then anS-path ofG is a path between distinct vertices ofS that contains no other vertices ofS. TwoS-paths are said to be internally disjoint if they have no vertices in common, except possibly end-vertices. For a given setS ofl 2 vertices of a graphG, a sufficient condition forG to contain at leastn internally disjointS-paths, each of length at most 2, is established.     

Fractional Brownian motion and packing dimension

LetX(t) (tR ^N ) be a fractional Brownian motion of index inR ^d . For any compact setER ^N , we compute the packing dimension ofX(E).Partially supported by an NSF grant.     

Matrix functions with arbitrarily prescribed left and right partial indices

We prove that ifn2 and , are two given vectors inZ ⁿ, then there exists a matrix function inL ^n×n (T) which has a right Wiener-Hopf factorization inL ² with the partial indices and a left Wiener-Hopf factorization inL ² with the partial indices .     

Ramsey families which exclude a graph

For graphsA andB the relationA(B) _r ¹ means that for everyr-coloring of the vertices ofA there is a monochromatic copy ofB inA. Forb (G) is the family of graphs which do not embedG. A familyof graphs is Ramsey if for all graphsBthere is a graphAsuch thatA(B) _r ¹ . The only graphsG for which it is not known whether Forb (G) is Ramsey are graphs which have a cutpoint adjacent to every other vertex except one. In this paper we prove for a large subclass of those graphsG, that Forb (G) does not have the Ramsey property.This research has been supported in part by NSERC grant 69-1325.     

The Milnor–Totaro Theorem for Space Polygons

If denotes the curvature and the torsion of a closed, generic, and oriented polygonal space curve X in , then we show that _X (² + ²) ds = _X ds + _X | | ds > 4 if is positive. We also show that _X (² + ²) ds 2n if no four consecutive vertices lie in a plane and X has linking number n with a straight line. These extend theorems of Milnor and Totaro.     

Mixed graph colorings

A mixed graphG contains both undirected edges and directed arcs. Ak-coloring ofG is an assignment to its vertices of integers not exceedingk (also called colors) so that the endvertices of an edge have different colors and the tail of any arc has a smaller color than its head. The chromatic number (G) of a mixed graph is the smallestk such thatG admits ak-coloring. To the best of our knowledge it is studied here for the first time. We present bounds of (G), discuss algorithms to find this quantity for trees and general graphs, and report computational experience.     

Connected and alternating vectors: Polyhedra and algorithms

Given a graphG = (V, E), leta ^S, S L, be the edge set incidence vectors of its nontrivial connected subgraphs.The extreme points of = {x R ^E: a^sx |V(S)| - |S|, S L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb ^k, k K, ofG. WhenG is a tree, the extreme points ofB 0,b ^kx 1,k K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated with andA, good algorithms are given and total dual integrality of andA proven.On leave from Swiss Federal Institute of Technology, Zurich.     

Irreducibility of moduli space of harmonic 2-spheres in S4

In this paper we prove that ford3, the moduli spaces of degreed branched superminimal immersions of the 2-sphere intoS ⁴ has 2 irreducible components. Consequently, the moduli space of degreed harmonic 2-spheres inS ⁴ has 3 irreducible components.     

Subfactors with principal graph E 6 (1)

We characterize irreducible II₁ subfactorsN M with principal graphE ₆ ⁽¹⁾ as N=P Z ₃ P A ₄, whereA ₄ acts outerly on a factorP.     

A note on the independent domination number of subset graph

The independent domination number i(G) (independent number (G)) is the minimum (maximum) cardinality among all maximal independent sets of G. Haviland (1995) conjectured that any connected regular graph G of order n and degree 1/2n satisfies i(G) 2n/3 1/2. For 1 k l m, the subset graph S _m (k, l) is the bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for i(S _m (k, l)) and prove that if k + l = m then Havilands conjecture holds for the subset graph S _m (k, l). Furthermore, we give the exact value of (S _m (k, l)).This work was supported by National Natural Sciences Foundation of China (19871036).     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

The (Δ,d,d′, Δ − 1)-problem with applications to computer networks

The (,d, d, – 1)-problem is that of finding large graphs with maximum degree and diameterd such that the subgraphs obtained by deleting any set of up to – 1 vertices have diameterd. In this paper, we deduce upper bounds on the order of such graphs and present some of the largest known ones. We argue that these graphs can be used to construct extremely "robust" networks, and explain why we require this robustness property when designing transputer networks for certain applications. In particular, we investigate the suitability of the odd graphO ₄ as a topology for such networks.     

D λ -cycles in 3-cyclable graphs

Letk and be positive integers, andG a 2-connected graph of ordern with minimum degree and independence number. A cycleC ofG is called aD -cycle if every component ofG – V(C) has order smaller than. The graphG isk-cyclable if anyk vertices ofG lie on a common cycle. A previous result of the author is that if k 2, G isk-connected and every connected subgraphH ofG of order has at leastn +k ² + 1/k + 1 – vertices outsideH adjacent to at least one vertex ofH, thenG contains aD -cycle. Here it is conjectured that k-connected can be replaced by k-cyclable, and this is proved fork = 3. As a consequence it is shown that ifn 4 – 6, or ifG is triangle-free andn 8 – 10, thenG contains aD ₃-cycle orG , where denotes a well-known class of nonhamiltonian graphs of connectivity 2. As an analogue of a result of Nash-Williams it follows that ifn 4 – 6 and – 1, thenG is hamiltonian orG . The results are all best possible and compare favorably with recent results on hamiltonicity of graphs which are close to claw-free.     

Convergence proofs and error estimates for an iterative method for conformal mapping

Summary The iterative method as introduced in [8] and [9] for the determination of the conformal mapping of the unit disc onto a domainG is here described explicitly in terms of the operatorK, which assigns to a periodic functionu its periodic conjugate functionK u. It is shown that whenever the boundary curve ofG is parametrized by a function with Lipschitz continuous derivative then the method converges locally in the Sobolev spaceW of 2-periodic absolutely continuous functions with square integrable derivative. If is in a Hölder classC ²⁺, the order of convergence is at least 1+. If is inC ^l+1+ withl1, 0<<1, then the iteration converges inC ^l+. For analytic boundary curves the convergence takes place in a space of analytic functions.For the numerical implementation of the method the operatorK can be approximated by Wittich's method, which can be applied very effectively using fast Fourier transform. The Sobolev norm of the numerical error can be estimated in terms of the numberN of grid points. It isO(N ^1–l–) if is inC ^l+1+, andO (exp (–N/2)) if is an analytic curve. The number in the latter formula is bounded by logR, whereR is the radius of the largest circle into which can be extended analytically such that'(z)0 for |z|<R. The results of some test calculations are reported.