A short proof of the nonuniform Ray-Chaudhuri-Wilson inequality

LetL be a set ofs nonnegative integers and a family of subsets of ann-element setX. Suppose that for any two distinct membersA,B we have¦A B¦ L. Assuming in addition that, is uniform, i.e. each member of has the same cardinality, a celebrated theorem of D. K. Ray-Chaudhuri and R. M. Wilson asserts that ¦¦ P. Frankl and R. M. Wilson proved that without the uniformity assumption, we have.We give a short proof of this latter result.     

Some intersection theorems on two-valued functions

Let be a family of two-valued functions defined on ann-element set in which each pair of functions in satisfy a given intersection condition. For certain intersection conditions we determine the maximal value of .     

The classification of distance-regular graphs of type IIB

The distance-regular graphs of type IIB in Bannai and Ito [1] have intersection numbers of the form whered is the diameter of , andh, x, andt are complex constants. In this paper we show a graph of type IIB and diameterd (3d) is either the antipodal quotient of the Hamming graphH(2d+1,2), or has the same intersection numbers as the antipodal quotient ofH(2d, 2).     

Structures of polyhedra determined by submodular functions on crossing families

The present paper shows that for any submodular functionf on a crossing family with , if the polyhedron is nonempty, then there exist a unique distributive lattice with and a unique submodular function with such thatB(f) coincides with the base polyhedron associated with the submodular system . Here, iff is integer-valued, thenf ₁ is also integer-valued. Based on this fact, we also show the relationship between the independent-flow problem considered by the author and the minimum cost flow problem considered by J. Edmonds and R. Giles.     

Eulerian numbers with fractional order parameters

Summary The aim of this paper is to generalize the well-known Eulerian numbers, defined by the recursion relationE(n, k) = (k + 1)E(n – 1, k) + (n – k)E(n – 1, k – 1), to the case thatn is replaced by . It is shown that these Eulerian functionsE(, k), which can also be defined in terms of a generating function, can be represented as a certain sum, as a determinant, or as a fractional Weyl integral. TheE(, k) satisfy recursion formulae, they are monotone ink and, as functions of , are arbitrarily often differentiable. Further, connections with the fractional Stirling numbers of second kind, theS(, k), > 0, introduced by the authors (1989), are discussed. Finally, a certain counterpart of the famous Worpitzky formula is given; it is essentially an approximation ofx in terms of a sum involving theE(, k) and a hypergeometric function.Dedicated to the memory of Alexander M. Ostrowski on the occasion of the 100th anniversary of his birth.     

Stochastic dilations of uniformly continuous completely positive semigroups

For an arbitrary uniformly continuous completely positive semigroup ( _t :t0) on the space of bounded operators on a Hilbert space, we construct a family (U(t)t0) of unitary operators on a Hilbert space and a conditional expectation from to, such that, for arbitraryt0,. The unitary operatorsU(t) satisfy a stochastic differential equation involving a noncommutative generalisation of infinite dimensional Brownian motion. They do not form a semigroup.Part of this work was completed when the first author was visiting research associate at the Center for Relativity, Physics Department, The University of Texas at Austin, Austin, TX 78712, U.S.A., supported in part by NSF PHY 81-01381.     

Intersections of curve systems and the crossing number ofC 5 ×C 5

It and are two families of pairwise disjoint simple closed curves in the plane such that each curve in intersects each curve in , then the total number of points of intersection in is at least 2(m−1)n, where , and this bound is best possible. We use this to show that the cartesian product of two 5-cycles has crossing number 15.     

Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice

Let _i(L), _i(L^*) denote the successive minima of a latticeL and its reciprocal latticeL ^*, and let [b₁,..., b _n ] be a basis ofL that is reduced in the sense of Korkin and Zolotarev. We prove that and, where and _j denotes Hermite's constant. As a consequence the inequalities are obtained forn7. Given a basisB of a latticeL in ^m of rankn andx ^m , we define polynomial time computable quantities(B) and(x,B) that are lower bounds for ₁(L) and(x,L), where(x,L) is the Euclidean distance fromx to the closest vector inL. If in additionB is reciprocal to a Korkin-Zolotarev basis ofL ^*, then ₁(L) _n ^* (B) and.The research of the second author was supported by NSF contract DMS 87-06176. The research of the third author was performed at the University of California, Berkeley, with support from NSF grant 21823, and at AT&T Bell Laboratories.     

Extended dyer-lashof algebras and modular coinvariants

Given an increasing sequence of integersN=(0,n ₁,n ₂,...), a functorG _N is constructed from the category of based spaces of the homotopy type ofCW compleces and based maps to a subcategory of in analogy to May's approximation modelC. A family of homology operationsRN is associated toG _N and its algebraic structure is described in terms of modular coinvariants of parabolic subgroups.     

Large sample theory for distributions on the hypersphere with rotational symmetries

Summary A distribution on the unit sphere inℝ ^q with a densityf(‖x _v ‖) is considered where is ans(<q) dimensional subspace andx _v is the part ofx in . For a large sample the estimation of , a test that and a test for rotational symmetry within is given. For several samples with possibly different subspaces but the samef, a test that is given. For all tests power functions for contiguous alternatives are given. For the special density proportional to expk‖x _v ‖ ², additional results are given. Research supported in part by a Contract with the Office of Naval Research N00014-81-K-0146 awarded to Princeton University, Princeton, New Jersey 08544.     

Gauge group and gauge transformation in the continual theory of defects

A representation of the algebra (3)=t(3) S0(3, ) by differential Schaefer's operators is proposed, and an external algebra of (3)-valued differential forms is constructed. The requirement of local gauge invariance is formulated in the model of the (3)-valued field, which enables a group of gauge transformations of the continual theory of defects to be obtained.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 190, pp. 173–184, 1991.I wish to thank V. N. Popov for his interest.     

Compact Hopf hypersurfaces of constant mean curvature in complex space forms

We prove that every connected compact Hopf hypersurface of a complex space form, contained in a geodesic ball of radius strictly smaller than the injectivity radius of, having constant mean curvature and with if if < 0 is a geodesic sphere of.Work partially supported by DGICYT Grant No. PB91-0324.     

On a certain nonstationary problem in a dihedral angle. I

An initial-boundary value problem is considered for the heat conduction equation in a dihedral angleD Rⁿ, on one face of which the classical Neumann boundary condition is satisfied, while on the other one the condition where x > 0, h 0, b_j are real constants. The unique solvability of such a problem is proved in weighted Sobolev spaces and estimates of the solution are obtained under natural restrictions on the opening of the dihedral angle.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad Nauk SSSR, Vol. 188, pp. 159–177, 1991.     

Inductive definitions,models of comprehension and invariant definability

The connections between inductive definability and models of comprehension are studied. Let = 〈A, R _l, ...,R _n 〉 be an infinite structure and letI _φ be a set inductively defined by a formulaφ of the second order language . We prove that if is a model of Δ ₁ ¹ -Comprehension relativized toφ, andφ is -absolute, then for everyη smaller than the height of (h( )),I _φ is in . If is aβ-structure which satisfies Σ ₁ ¹ -Comprehension relativized toφ and WF(X), and φ is -absolute, thenI _φ is in and ‖φ| <h ( ). These results imply that Barwise-Grilliot theorem is false in the case of uncountable acceptable structures. We also study the notion of invariant definability over models₁ of Δ ₁ ¹ -Comprehension. This paper is registered as Report ZW 69/76 of the Mathematical Centre.     

Best-possible one-sided approximations in the classes 688-01688-01688-01by trigonometric polynomials in the metric of L1

The quantities are calculated, where is the best approximation from above of the function f by trigonometric polynomials of order ⩽n—1 in the metric of L₁. Translated from Matematicheskie Zametki, Vol. 22, No. 3, pp. 357–370, September, 1977.     

Isoperimetric inequalities for infinite hyperplane systems

Let be an infinite discrete system ofk-dimensional flats inn-dimensional Euclidean space. If the totalk-dimensional volume of the flats in intersected with the ball of center 0 and radiusr, divided by the volume of that ball, tends to a limit forr→∞, then this limit is called thedensity of . We consider isoperimetric problems of the following kind. If is a hyperplane system of positive density, find sharp upper bounds for the density of the system ofk-flats (k∈{0, ...,n−2}) that are generated as intersections of hyperplanes in . Ideas from the theory of uniform distribution of sequences are employed to define a large class of hyperplane systems, calleduniform, for which all necessary densities exist, isperimetric inequalities can be proved, and systems with extremal intersection densities can be characterized.     

A decomposition of 2-weak vertex-packing polytopes

The 2-weak vertex-packing polytope of a loopless graphG withd vertices is the subset of the unitd-cube satisfyingx _i +x _j ≤1 for every edge (i,j) ofG. The dilation by 2 of this polytope is a polytope with integral vertices. We triangulate with lattice simplices of minimal volume and label the maximal simplices with elements of the hyperoctahedral groupB _d . This labeling gives rise to a shelling of the triangulation of , where theh-vector of (and the Ehrharth ^*-vector of can be computed as a descent statistic on a subset ofB _d defined in terms ofG. A recursive way of computing theh-vector of is also given, and a recursive formula for the volume of . This work was partially supported by grants from the Icelandic Council of Science and the Royal Swedish Academy of Sciences, respectively.     

Valuations and polarity

Given a collection of convex polytopes, let() denote the set of all convex transversals of. If and are two such collections, of finite cardinality, then there is a simple, arithmetical condition which holds precisely when ()=(). Another such condition, involving what we call the Sallee-Shephard mapping, characterizes those pairs and for which (())=().As these results are established, several distributive lattices involving convex sets are introduced, and relationships between their valuation modules are determined. In particular, it is proven that the Sallee-Shephard mapping is an isomorphism of the additive, abelian group of simple functions generated by the characteristic functions of the open, convex sets and that generated by those of the closed, convex sets.     

Infinite highly arc transitive digraphs and universal covering digraphs

A digraph (that is a directed graph) is said to be highly arc transitive if its automorphism group is transitive on the set ofs-arcs for eachs0. Several new constructions are given of infinite highly arc transitive digraphs. In particular, for a connected, 1-arc transitive, bipartite digraph, a highly arc transitive digraphDL() is constructed and is shown to be a covering digraph for every digraph in a certain classD() of connected digraphs. Moreover, if is locally finite, thenDL() is a universal covering digraph forD(). Further constructions of infinite highly arc transitive digraphs are given.The second author wishes to acknowledge the hospitality of the Mathematical Institute of the University of Oxford, and the University of Auckland, during the period when the research for this paper was doneResearch supported by the Australian Research Council     

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.