Resolvable Mendelsohn designs with block size 4

Summary Letv andK be positive integers. A (v, k, 1)-Mendelsohn design (briefly (v, k, 1)-MD) is a pair (X,B) whereX is av-set (ofpoints) andB is a collection of cyclically orderedk-subsets ofX (calledblocks) such that every ordered pair of points ofX are consecutive in exactly one block ofB. A necessary condition for the existence of a (v, k, 1)-MD isv(v–1) 0 (modk). If the blocks of a (v, k, 1)-MD can be partitioned into parallel classes each containingv/k blocks wherev ) (modk) or (v – 1)/k blocks wherev 1 (modk), then the design is calledresolvable and denoted briefly by (v, k, 1)-RMD. It is known that a (v, 3,1)-RMD exists if and only ifv 0 or 1 (mod 3) andv 6. In this paper, it is shown that the necessary condition for the existence of a (v, 4, 1)-RMD, namelyv 0 or 1 (mod 4), is also sufficient, except forv = 4 and possibly exceptingv = 12. These constructions are equivalent to a resolvable decomposition of the complete symmetric directed graphK _v ^* onv vertices into 4-circuits.Research supported by the Natural Sciences and Engineering Research Council of Canada under Grant A-5320.     

Geometrical implications of the existence of very smooth bump functions in Banach spaces

We show that ifX is a Banach space and if there is a non-zero real-valuedC ^∞-smooth function onX with bounded support, then eitherX contains an isomorphic copy ofc ₀(N), or there is an integerk greater than or equal to 1 such thatX is of exact cotype 2k and, in this case,X contains an isomorphic copy ofl ^2k(N). We also show that ifX is a Banach space such that there is onX a non-zero real-valuedC ⁴-smooth function with bounded support and ifX is of cotypeq forq<4, thenX is isomorphic to a Hilbert space.     

Any Banach space has an equivalent norm with trivial isometries

For any Banach spaceX there is a norm |||·||| onX, equivalent to the original one, such that (X, |||·|||) has only trivial isometries. For any groupG there is a Banach spaceX such that the group of isometries ofX is isomorphic toG × {− 1, 1}. For any countable groupG there is a norm ‖ · ‖ _G onC([0, 1]) equivalent to the original one such that the group of isometries of (C([0, 1]), ‖ · ‖ _G ) is isomorphic toG × {−1, + 1}.     

The existence of resolvable Steiner quadruple systems

A Steiner quadruple system of order v is a set X of cardinality v, and a set Q, of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in a unique block. A Steiner quadruple system is resolvable if Q can be partitioned into parallel classes (partitions of X). A necessary condition for the existence of a resolvable Steiner quadruple system is that v≡4 or 8 (mod 12). In this paper we show that this condition is also sufficient for all values of v, with 24 possible exceptions.     

Packings of the complete directed graph with m-circuits

A packing of the complete directed symmetric graph DKv with m-circuits, denoted by(v,m)-DCP, is defined to he a family of are-disjoint m-circuits of DK, such that any one arc of DKv occurs in at most one m circuit. The packing number P(v,m) is the maximum number of m-circults in such a packing. The packing problem is to determine the value P(v,m) for everyinteger v ≥ m. In this paper, the problem is reduced to the case m 6 ≤v≤2m-[(4m-3的平方极) 1/2],for any fixed even integer m≥4,In particular,the values of P（v,m） are completely determined for m=12,14 and 16.     

Characterization of minimal elements in minimization problems with constraints

LetX be a compact Hausdorff space andC(X) be the set of all continuous functions defined onX. LetVC(X), and consider the problem of minimizing sup _xX W[x,v(x)], withvV. The functionW is a generalized weight function and can be chosen such that certain constraints are included.The notions of critical point and extremal signature are used to formulate characterization theorems for a minimal element inV. It is shown that these theorems hold only under certain conditions ofV andW. The results obtained are applied to the problem of the Chebyshev approximation with constraints and to the problem of optimization with strictly quasiconvex constraints.The work of the second author was supported in part by the Alexander von Humboldt Stiftung and the DAAD.     

Facets for the cut cone II: Clique-web inequalities

We study new classes of facets for the cut coneC _n generated by the cuts of the complete graph onn vertices. This cone can also be interpreted as the cone of all semi-metrics onn points that are isometricallyl ₁-embeddable and, in fact, the study of the facets of the cut polytope is in some sense equivalent to the study of the facets ofC _n . These new facets belong to the class of clique-web inequalities which generalize the hypermetric and cycle inequalities as well as the bicycle odd wheel inequalities.     

Über Bewertungen,welche unter einer reduktiven Gruppe invariant sind

Summary LetG be a reductive group defined over an algebraically closed fieldk and letX be aG-variety. In this paper we studyG-invariant valuationsv of the fieldK of rational functions onX. These objects are fundamental for the theory of equivariant completions ofX. LetB be a Borel subgroup andU the unipotent radical ofB. It is proved thatv is uniquely determined by its restriction toK ^U . Then we study the set of invariant valuations having some fixed restrictionv ₀, toK ^B . Ifv ₀ is geometric (i.e., induced by a prime divisor) then this set is a polyhedron in some vector space. In characteristic zero we prove that this polyhedron is a simplicial cone and in fact the fundamental domain of finite reflection groupW ^X . Thus, the classification of invariant valuations is almost reduced to the classification of valuations ofK ^B .

Unterstützt durch den Schweizerischen Nationalfonds zur Förderung der wissenschaftlichen Forschung.     

When isf(x,y) = u(x) + v(y)?

LetX andY be arbitrary non-empty sets and letS a non-empty subset ofX ×Y. We give necessary and sufficient conditions onS which ensure that every real valued function onS is the sum of a function onX and a function onY.     

On some extremal problems in graph theory

The author proves that ifC is a sufficiently large constant then every graph ofn vertices and [Cn ^3/2] edges contains a hexagonX ₁,X ₂,X ₃,X ₄,X ₅,X ₆ and a seventh vertexY joined toX ₁,X ₃ andX ₅. The problem is left open whether our graph contains the edges of a cube, (i.e. an eight vertexZ joined toX ₂,X ₄ andX ₆).     

Der allgemeine Approximationssatz für Manisbewertungen

In this paper we examine under which circumstances the general approximation theorem holds for Manis-valuations of a commutative ringR. In the first part we establish a sufficient condition and a (weaker) necessary condition onR, such that for arbitrary valuationsv ₁,...,v _n ofR the approximation theorem, is valid. In the second part we show that the approximation theorem holds forv ₁,...,v _n ,if the intersection of their valuation rings is anR-Prüferring.     

Uniformities,hyperspaces, and normality

LetX be a completely regular space and 2 ^X the hyperspace ofX. It is shown that the uniform topologies on 2 ^X arising from Nachbin uniformity onX, which is the weak uniformity generated byC(X, ), and from Tukey—Shirota uniformity onX, generated by all countable open normal coverings ofX, agree. They, both, coincide with a Vietoris-type topology on 2 ^X , the countable locally finite topology, iffX is normal.     

Chaos caused by a strong-mixing measure-preserving transformation

The chaos caused by a strong-mixing preserving transformation is discussed and it is shown that for a topological spaceX satisfying the second axiom of countability and for an outer measurem onX satisfying the conditions: (i) every non-empty open set ofX ism-measurable with positivem-measure; (ii) the restriction ofm on Borel σ-algebra ℬ(X) ofX is a probability measure, and (iii) for everyY⊂X there exists a Borel setB⊂ℬ(X) such thatB⊃Y andm(B) =m(Y), iff:X→X is a strong-mixing measure-preserving transformation of the probability space (X, ℬ(X),m), and if {m}, is a strictly increasing sequence of positive integers, then there exists a subsetC⊂X withm (C) = 1, finitely chaotic with respect to the sequence {m _i}, i.e. for any finite subsetA ofC and for any mapF:A→X there is a subsequencer _i such that lim_i→∞ f ^r i(a) =F(a) for anya ∈A. There are some applications to maps of one dimension. the National Natural Science Foundation of China.     

Orientations of circle graphs

Let C(v₁, …,v_n) be a system consisting of a circle C with chords v₁, …,v_n on it having different endpoints. Define a graph G having vertex set V(G) = {v₁, …,v_n} and for which vertices v_i and v_j are adjacent in G if the chords v_i and v_j intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v₁, …,v_n) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v₁, …,v_n) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.     

Distance in stratified graphs

A graph G is stratified if its vertex set is partitioned into classes, called strata. If there are k strata, then G is k-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color X in a stratified graph G, the X-eccentricity e _X(v) of a vertex v of G is the distance between v and an X-colored vertex furthest from v. The minimum X-eccentricity among the vertices of G is the X-radius rad_X G of G and the maximum X-eccentricity is the X-diameter diam_X G. It is shown that for every three positive integers a, b and k with ab, there exist a k-stratified graph G with rad_X G = a and diam_X G = b. The number s _X denotes the minimum X-eccetricity among the X-colored vertices of G. It is shown that for every integer t with rad_X G t diam_X G, there exist at least one vertex v with e _X(v) = t; while if rad_X G t s _X, then there are at least two such vertices. The X-center C _X(G) is the subgraph induced by those vertices v with e _X(v) = rad_X G and the X-periphery P _X (G) is the subgraph induced by those vertices v with e _X(G) = diam_X G. It is shown that for k-stratified graphs H ₁, H ₂,..., H _k with colors X ₁, X ₂,..., X _k and a positive integer n, there exists a k-stratified graph G such that C X _i(G) H _i (1 ; i ; k1) and for i j. Those k-stratified graphs that are peripheries of k-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.     

On the Expected Number of Shadow Vertices of the Convex Hull of Random Points

Leta₁, . . . ,a_mbe independent random points in ⁿthat are independent and identically distributed spherically symmetrical in ⁿ. Moreover, letXbe the random polytope generated as the convex hull ofa₁, . . . ,a_mand letL_kbe an arbitraryk-dimensional subspace of ⁿwith 2 ≤k≤n− 1. LetX_kbe the orthogonal projection image ofXinL_k. We call those vertices ofXwhose projection images inL_kare vertices ofX_kshadow vertices ofXwith respect to the subspaceL_k. We derive a distribution independent sharp upper bound for the expected number of shadow vertices ofXinL_k.     

C-Cosine Functions and the Abstract Cauchy Problem, II

For a bounded linear injectionCon a Banach spaceXand a closed linear operatorA : D(A) X → Xwhich commutes withCwe prove that (1) the abstract Cauchy problem,u″(t) = Au(t),t R,u(0) = Cx,u′(0) = Cy, has a unique strong solution for everyx,y D(A) if and only if (2)A₁ = AD(A²) generates aC₁-cosine function onX₁(D(A) with the graph norm), if (and only if, in caseAhas nonempty resolvent set) (3)Agenerates aC-cosine function onX. HereC₁ = CX₁. Under the assumption thatAis densely defined andC⁻¹AC = A, statement (3) is also equivalent to each of the following statements: (4) the problemv″(t) = Av(t) + C(x + ty) + ∫^t₀ Cg(r) dr,t R,v(0) = v′(0) = 0, has a unique strong solution for everyg L¹_locandx, y X; (5) the problemw″(t) = Aw(t) + Cg(t),t R,w(0) = Cx,w′(0) = Cy, has a unique weak solution for everyg L¹_locandx, y X. Finally, as an application, it is shown that for any bounded operatorBwhich commutes withCand has range contained in the range ofC,A + Bis also a generator.     

Sobolev embeddings into BMO, VMO, andL ∞

LetX be a rearrangement-invariant Banach function space onR ⁿ and letV ¹ X be the Sobolev space of functions whose gradient belongs toX. We give necessary and sufficient conditions onX under whichV ¹ X is continuously embedded into BMO or intoL _∞. In particular, we show thatL _{n, ∞} is the largest rearrangement-invariant spaceX such thatV ¹ X is continuously embedded into BMO and, similarly,L _{n, 1} is the largest rearrangement-invariant spaceX such thatV ¹ X is continuously embedded intoL _∞. We further show thatV ¹ X is a subset of VMO if and only if every function fromX has an absolutely continuous norm inL _{n, ∞} . A compact inclusion ofV ¹ X intoC ⁰ is characterized as well.     

Dual spaces of C∞ (X)

ForX a locally compact Stonian Space, letC _∞ (X) denote the universally complete Riesz space of all extended-real-valued continuous functionsf onX for which {x∈X| |f (x)|=∞} is nowhere dense. In this paper the dual spaces ofC _∞ (X) (i.e. the spaces of order bounded; of σ-order continuous; of order continuous linear forms onC _∞ (X), and the extended order dual ofC _∞ (X) denote here byC _∞ (X)^ρ (introduced by W.A.J. Luxemburg and J.J. Masterson)) are characterized. It is shown thatC _∞ (X)^ρ can be identified in a canonical way with the inductive limitM _q (X) of the Riesz spaces of all normal Radon measures defined on the dense open subsets ofX. More generally, ifY is a locally compact space thenM _q (Y) is the extended order dual of the inductive limit of the Riesz spaces of all real-valued continuous functions defined on the dense open subsets ofY. IfX is locally compact and hyperstonian, then it is proved thatC _∞ (X) andC _∞ (X)^ρ are isomorphic, and a criterion forC _∞ (X)^ρ to be the universal completion of the space of order continuous linear forms onC _∞ (X) is given.     

Packing tight Hamilton cycles in 3‐uniform hypergraphs

Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ? H is a collection of n edges for which there is an ordering of the vertices v₁,…,v_n such that every triple of consecutive vertices {v_i,v_i+1,v_i+2} is an edge of C (indices are considered modulo n ). We develop new techniques which enable us to prove that under certain natural pseudo‐random conditions, almost all edges of H can be covered by edge‐disjoint tight Hamilton cycles, for n divisible by 4. Consequently, we derive the corollary that random 3‐uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo‐random digraphs with even numbers of vertices. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011