Strongly Regular Semi-Cayley Graphs

We consider strongly regular graphs = (V, E) on an even number, say 2n, of vertices which admit an automorphism group G of order n which has two orbits on V. Such graphs will be called strongly regular semi-Cayley graphs. For instance, the Petersen graph, the Hoffman–Singleton graph, and the triangular graphs T(q) with q 5 mod 8 provide examples which cannot be obtained as Cayley graphs. We give a representation of strongly regular semi-Cayley graphs in terms of suitable triples of elements in the group ring Z G. By applying characters of G, this approach allows us to obtain interesting nonexistence results if G is Abelian, in particular, if G is cyclic. For instance, if G is cyclic and n is odd, then all examples must have parameters of the form 2n = 4s ² + 4s + 2, k = 2s ² + s, = s ² – 1, and = s ²; examples are known only for s = 1, 2, and 4 (together with a noncyclic example for s = 3). We also apply our results to obtain new conditions for the existence of strongly regular Cayley graphs on an even number of vertices when the underlying group H has an Abelian normal subgroup of index 2. In particular, we show the nonexistence of nontrivial strongly regular Cayley graphs over dihedral and generalized quaternion groups, as well as over two series of non-Abelian 2-groups. Up to now these have been the only general nonexistence results for strongly regular Cayley graphs over non-Abelian groups; only the first of these cases was previously known.     

Partial geometries and the triality quadric

Up to now there are eight partial geometries pg(7,8,4) known. Their point graphs as well as their block graphs are all related to the triality quadric Q⁺(7,2). We prove that some of these graphs are the point graph of (up to isomorphism) exactly one partial geometry. We investigate the relations among some of these eight partial geometries. Generalizing our results, we construct two new families of partial geometries pg(2^2n–1– 1, 2^2n–1, 2^2n–2).The second author is a Research Fellow supported by the Flemish Institute for the Promotion of Scientific and Technological Research in Industry (IWT), grant No. IWT/SB/971002.     

Regularities in congruential random number generators

Summary This paper suggests, as did an earlier one, [1] that points inn-space produced by congruential random number generators are too regular for general Monte Carlo use. Regularity was established in [1] for multiplicative congruential generators by showing that all the points fall in sets of relatively few parallel hyperplanes. The existence of many containing sets of parallel hyperplanes was easily established, but proof that the number of hyperplanes was small required a result of Minkowski from the geometry of numbers—a symmetric, convex set of volume 2 ⁿ must contain at least two points with integral coordinates. The present paper takes a different approach to establishing the coarse lattice structure of congruential generators. It gives a simple, self-contained proof that points inn-space produced by the general congruential generatorr _i+1 ar _i +b modm must fall on a lattice with unit-cell volume at leastm ^n–1 There is no restriction ona orb; this means thatall congruential random number generators must be considered unsatisfactory in terms of lattices containing the points they produce, for a good generator of random integers should have ann-lattice with unit-cell volume 1.     

On a Class of Symmetric Balanced Generalized Weighing Matrices

Let q be a prime power and m a positive integer. A construction method is given to multiply the parametrs of an -circulant BGW(v=1+q+q ₂+·+q ^m , q ^m , q ^m –q ^m–1) over the cyclic group C _n of order n with (q–1)/n being an even integer, by the parameters of a symmetric BGW(1+q ^m+1, q ^m+1, q ^m+1–q ^m ) with zero diagonal over a cyclic group C _vn to generate a symmetric BGW(1+q+·+q ^2m+1,q ^2m+1,q ^2m+1–q ^2m) with zero diagonal, over the cyclic group C _n . Applications include two new infinite classes of strongly regular graphs with parametersSRG(36(1+25+·+25^2m+1),15(25)^2m+1,6(25)^2m+1,6(25)^2m+1), and SRG(36(1+49+·+49^2m+1),21(49)^2m+1,12(49)^2m+1,12(49)^2m+1).     

Algebraic surfaces with an infinite set of planes of oblique symmetry. II

Suppose that G is an infinite group generated by obliquereflections with respect to hyperplanes in the real spaceE ^m and that theµ _j-planes II^µj = II^dj II^j (j = G(u) -orbits of directions of symmetryu (hyperplanes of symmetry conjugate to vectors II^dj pass through _j-planesII ^j). A complete solution of the problem of the mutual position of three II^j is given. Systems of generatrices of the rings of invariants of a series of groups G are found.Translated from Ukrainskii Geometricheskii Sbornik, No. 34, pp. 42–51, 1991.     

The complexity of many cells in arrangements of planes and related problems

We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m ^2/3 n logn +n ²); we can calculatem such cells specified by a point in each, in worst-case timeO(m ^2/3 n log³ n+n ² logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m ^2/3 n logn+n ²), but this number is onlyO(m ^3/5– n ^4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m ^3/4– n ^3/4+3 +m) log² n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m ^3/4– n ^3/4+3 +m] log² n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m ^2/3 n ^d/3 logn+n ^d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. An abstract of this paper has appeared in theProceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147.     

Skew-symmetric association schemes with two classes and strongly regular graphs of type L 2n−1(4n−1)

A construction of a pair of strongly regular graphs ⁿ and ⁿ of type L _2n–1(4n–1) from a pair of skew-symmetric association schemes W, W of order 4n–1 is presented. Examples of graphs with the same parameters as ⁿ and ⁿ, i.e., of type L _2n–1(4n–1), were known only if 4n–1=p ³, where p is a prime. The first new graph appearing in the series has parameters (v, k, )=(225, 98, 45). A 4-vertex condition for relations of a skew-symmetric association scheme (very similar to one for the strongly regular graphs) is introduced and is proved to hold in any case. This has allowed us to check the 4-vertex condition for ⁿ and ⁿ, thus to prove that ⁿ and ⁿ are not rank three graphs if n>2.     

On Strongly Regular Graphs with k=2μ and Their Extensions

We obtain a convenient expression for the parameters of a strongly regular graph with k=2 in terms of the nonprincipal eigenvalues x and –y. It turns out in particular that such graphs are pseudogeometric for pG _x(2x,y–1). We prove that a strongly regular graph with parameters (35,16,6,8) is a quotient of the Johnson graph (8,4). We also find the parameters of strongly regular graphs in which the neighborhoods of vertices are pseudogeometric graphs for pG _x(2x,t),x3. In consequence, we establish that a connected graph in which the neighborhoods of vertices are pseudogeometric graphs for pG ₃(6,2) is isomorphic to the Taylor graph on 72 vertices or to the alternating form graph Alt(4,2) with parameters (64,35,18,20).     

Subsquares in orthogonal latin squares as subspaces in affine geometries: A generalization of an equivalence of bose

The combinatorial properties of subsquares in orthogonal latin squares are examined. Using these properties it is shown that in appropriate orthogonal latin squares of orderm ^h blocks of subsquares of orderm ^h(i–1)/i , wherei dividesh, form the hyperplanes of the affine geometryAG (2i, m ^h/i ). This means that a given set of mutually orthogonal latin squares may be equivalent simultaneously to a number of different geometries depending on the order of the subsquares used to form the hyperplanes. In the case thati=1, the subsquares become points, the hyperplanes become lines, and the equivalence reduces to the well known result of Bose relating orthogonal latin squares and affine planes.The author would like to thank the Natural Sciences and Engineering Research Council of Canada for partial support under grant no. OGP0014645.     

Symmetric balanced ternary designs with ϱ1 = 1 or 2

Summary We prove the following two non-existence theorems for symmetric balanced ternary designs. If ₁ = 1 and 0 (mod 4) then eitherV = + 1 or 4₂ – + 1 is a square and (4₂ – + 1) divides ² – 1. If ₁ = 2 thenV = ((m + 1)/2) ² + 2,K = (m ² + 7)/4 and = ((m – 1)/2)² + 1 wherem 3 (mod 4). An example belonging to the latter series withV = 18 is constructed.     

Evolution Equations for Special Lagrangian 3-Folds in C3

This is the third in a series of papers constructing explicit examples of special Lagrangian submanifolds in C ^m . The previous paper (Math. Ann. 320 (2001), 757–797), defined the idea of evolution data, which includes an (m – 1)-submanifold P in R ⁿ , and constructed a family of special Lagrangian m-folds N in C ^m , which are swept out by the image of P under a 1-parameter family of affine maps _t : R ⁿ C ^m , satisfying a first-order o.d.e. in t. In this paper we use the same idea to construct special Lagrangian 3-folds in C³. We find a one-to-one correspondence between sets of evolution data with m = 3 and homogeneous symplectic 2-manifolds P. This enables us to write down several interesting sets of evolution data, and so to construct corresponding families of special Lagrangian 3-folds in C³.Our main results are a number of new families of special Lagrangian 3-foldsin C³, which we write very explicitly in parametric form. Generically these are nonsingular as immersed 3-submanifolds, and diffeomorphic to R³ or ¹× R². Some of the 3-folds are singular, and we describe their singularities, which we believe are of a new kind.We hope these 3-folds will be helpful in understanding singularities ofcompact special Lagrangian 3-folds in Calabi–Yau 3-folds. This will beimportant in resolving the SYZ conjecture in Mirror Symmetry.     

Salem Numbers and Growth Series of Some Hyperbolic Graphs

Extending the analogous result of Cannon and Wagreich for the fundamental groups of surfaces, we show that, for the -regular graphs associated to regular tessellations of the hyperbolic plane by m-gons, the denominators of the growth series (which are rational and were computed by Floyd and Plotnick) are reciprocal Salem polynomials. As a consequence, the growth rates of these graphs are Salem numbers. We also prove that these denominators are essentially irreducible (they have a factor of X + 1 when m 2 mod 4; and when = 3 and m 4 mod 12, for instance, they have a factor of X ² – X + 1). We then derive some regularity properties for the coefficients f _n of the growth series: they satisfy K ⁿ – R < f _n < K ⁿ + R for some constants K, R < 0, < 1.     

On the stability of rational approximations to the cosine with only imaginary poles

Letr(z) be a rational approximation to cosz with only imaginary poles ±i ₁ ^–1/2 , ±i ₂ ^–1/2 , ..., ±i _m ^–1/2 such that |cozz –r(z)| C|z|^2m+2 as |z| 0. If the degree of the numerator ofr(z) is less than or equal to 2m and _i m/4,i=1, ...,m, then we show that |r(z)|1 for all realz.     

Sets of Type (a, b) From Subgroups of ΓL(1, pR)

In this paper k-sets of type (a, b) with respect to hyperplanes are constructed in finite projective spaces using powers of Singer cycles. These are then used to construct further examples of sets of type (a, b) using various disjoint sets. The parameters of the associated strongly regular graphs are also calculated. The construction technique is then related to work of Foulser and Kallaher classifying rank three subgroups of AL(1, p ^R). It is shown that the sets of type (a, b) arising from the Foulser and Kallaher construction in the case of projective spaces are isomorphic to some of those constructed in the present paper.     

Oval Designs in Desarguesian Projective Planes

Given any protective plane of even order q containing a hyperoval , a Steiner design can be constructed. The 2-rank of this design is bounded above by rank₂() – q – 1. Using a result of Blokhuis and Moorhouse [3], we show that this bound is met when is desarguesian and is regular. We also show that the block graph of the Steiner 2-design in this case produces a Hadamard design which is such that the binary code of the associated 3-design contains a copy of the first-order Reed-Muller code of length 2^2m , where q = 2 ^m .     

On the Location of Roots of Independence Polynomials

The independence polynomial of a graph G is the function i(G, x) = _k0 i _k x ^k, where i _k is the number of independent sets of vertices in G of cardinality k. We prove that real roots of independence polynomials are dense in (–, 0], while complex roots are dense in , even when restricting to well covered or comparability graphs. Throughout, we exploit the fact that independence polynomials are essentially closed under graph composition.     

Hanlon and Stanley's Conjecture and the Milnor Fibre of a Braid Arrangement

Let A be a real arrangement of hyperplanes. Let B = B(q) be Varchenko's quantum bilinear form of A, introduced [15], specialized so that all hyperplanes have weight q. B(q) is nonsingular for all complex q except certain roots of unity. Here, we examine the kernel of B at roots of unity in relation to the topology of the hyperplane singularity.We use Varchenko's work [16] to relate B(q) to a Salvetti complex for the Milnor fibration of A. This paper's main result is specific to the arrangement of reflecting hyperplanes associated with the A _{n – 1} root system. We use a geometric property of the Milnor fibre to resolve a conjecture due to Hanlon and Stanley regarding the -module structure of the kernel of B(q) at certain roots of unity.     

Building Symmetric Designs With Building Sets

We introduce a uniform technique for constructing a family of symmetric designs with parameters (v(q ^m+1-1)/(q-1), kq ^m ,q ^m), where m is any positive integer, (v, k, ) are parameters of an abelian difference set, and q = k ²/(k - ) is a prime power. We utilize the Davis and Jedwab approach to constructing difference sets to show that our construction works whenever (v, k, ) are parameters of a McFarland difference set or its complement, a Spence difference set or its complement, a Davis–Jedwab difference set or its complement, or a Hadamard difference set of order 9 · 4 ^d , thus obtaining seven infinite families of symmetric designs.     

Paley type partial difference sets in non <Emphasis Type="Italic">p</Emphasis>-groups

By modifying a construction for Hadamard (Menon) difference sets we construct two infinite families of negative Latin square type partial difference sets in groups of the form where p is any odd prime. One of these families has the well-known Paley parameters, which had previously only been constructed in p-groups. This provides new constructions of Hadamard matrices and implies the existence of many new strongly regular graphs including some that are conference graphs. As a corollary, we are able to construct Paley–Hadamard difference sets of the Stanton-Sprott family in groups of the form when is a prime power. These are new parameters for such difference sets.      

On theA 0-acceptability of rational approximations to the exponential function with only real poles

We consider rational approximations to the exponential function with real poles, ₁ ^–1 ,..., _m ^–1 , that correspond to implicit Runge-Kutta collocation methods. We show that if _i 1/2,i=1,...,m, the rational approximation isA ₀-acceptable.