Theory of perpendicular arrays

The cryptographical theory of unconditional secrecy and authentication is based on design-like structures called perpendicular arrays in the combinatorial literature. In order to meet the cryptographical requirements some additional and rather natural homogeneity conditions have to be satisfied. We develop a theory of these structures. Topics include bounds on the size, recursive and direct constructions using designs and permutation groups, as well as a link to Room cubes. © 1994 John Wiley & Sons, Inc.     

Difference packing arrays and systematic authentication codes

In this paper, a type of combinatorial design (called difference packing array) is proposed and used to give a construction of systematic authentication codes. Taking advantage of this construction, some new series of systematic authentication codes are obtainable in terms of existing difference packing arrays.     

Some new symmetric designs

For q, an odd prime power, we construct symmetric (2q²+2q+1,q²,½q(q-1)) designs having an automorphism group of order q that fixes 2q+1 points. The construction indicates that for each q the number of such designs that are pairwise non-isomorphic is very large.     

Random walks on highly symmetric graphs

We consider uniform random walks on finite graphs withn nodes. When the hitting times are symmetric, the expected covering time is at least 1/2n logn-O(n log logn) uniformly over all such graphs. We also obtain bounds for the covering times in terms of the eigenvalues of the transition matrix of the Markov chain. For distance-regular graphs, a general lower bound of (n-1) logn is obtained. For hypercubes and binomial coefficient graphs, the limit law of the covering time is obtained as well.     

Eigenvalue multiplicities of highly symmetric graphs

We find lower bounds on eigenvalue multiplicities for highly symmetric graphs. In particular we prove:Theorem 1. If Γ is distance-regular with valency k and girth g (g?4), and λ (λ≠±?k) is an eigenvalue of Γ, then the multiplicity of λ is at least

$\text{k(k?1)}{}^{\mathrm{<mtext>[</mtext><mtext>g</mtext><mtext>4</mtext><mtext>]?1</mtext>}}$

if g≡0 or 1 (mod 4),

$\text{2(k?1)}{}^{\mathrm{<mtext>[</mtext><mtext>g</mtext><mtext>4</mtext><mtext>]</mtext>}}$

if g≡2 or 3 (mod 4) where [ ] denotes integer part. Theorem 2. If the automorphism group of a regular graph Γ with girth g (g?4) and valency k acts transitively on s-arcs for some s, $\text{1?s?[}\text{1}\text{2}\text{g]}$, then the multiplicity of any eigenvalue λ (λ≠±?k) is at least

$\text{k(k?1)}{}^{\mathrm{<mtext>s</mtext><mtext>2?1</mtext>}}$

if s is even,

$\text{2(k?1)}{}^{\mathrm{<mtext>(</mtext><mtext>s?1)</mtext><mtext>2</mtext>}}$

if s is odd.     

Authentication perpendicular arrays APA1(2, 5, v)

Authentication perpendicular arrays APA_λ (t, k, v), as a special kind of perpendicular arrays, are introduced by D. R. Stinson in constructing authentication and secrecy codes. In this article, we improve the existence results for APA₁(2, 5, v) and show that such a design exists if and only if v ≥ 5 is odd, except v = 7 and possibly excepting v = 9, 13, 15, 17, 33, 39, 49, 53, 57, 63, 69, 73, 87, 89, 97, 113, 137, and 213. © 1996 John Wiley & Sons, Inc.     

A census of highly symmetric combinatorial designs

As a consequence of the classification of the finite simple groups, it has been possible in recent years to characterize Steiner t-designs, that is t-(v,k,1) designs, mainly for t=2, admitting groups of automorphisms with sufficiently strong symmetry properties. However, despite the finite simple group classification, for Steiner t-designs with t>2 most of these characterizations have remained long-standing challenging problems. Especially, the determination of all flag-transitive Steiner t-designs with 3≤t≤6 is of particular interest and has been open for about 40 years (cf. Delandtsheer (Geom. Dedicata 41, p. 147, 1992 and Handbook of Incidence Geometry, Elsevier Science, Amsterdam, 1995, p. 273), but presumably dating back to 1965). The present paper continues the author’s work (see Huber (J. Comb. Theory Ser. A 94, 180–190, 2001; Adv. Geom. 5, 195–221, 2005; J. Algebr. Comb., 2007, to appear)) of classifying all flag-transitive Steiner 3-designs and 4-designs. We give a complete classification of all flag-transitive Steiner 5-designs and prove furthermore that there are no non-trivial flag-transitive Steiner 6-designs. Both results rely on the classification of the finite 3-homogeneous permutation groups. Moreover, we survey some of the most general results on highly symmetric Steiner t-designs.      

Smooth circle actions on highly symmetric manifolds

We construct for the first time smooth circle actions on highly symmetric manifolds such as disks, spheres, and Euclidean spaces which contain two points with the same isotropy subgroup whose representations determined on the tangent spaces at the two points are not isomorphic to each other. This allows us to answer negatively a question of Hsiang and Hsiang [Some Problems in Differentiable Transformation Groups, Springer, Berlin, Problem 16, p. 228, 1968]. Dedicated to Prof. Yasuhiko Kitada on the occasion of his 60th birthday. Krzysztof Pawałowski was supported in part by the KBN Research Grant N 201 008 31/0524.     

A class of highly symmetric graphs,symmetric cylindrical constructions and their spectra

In this article, we introduce the algebra of block-symmetric cylinders and we show that symmetric cylindrical constructions on base-graphs admitting commutative decompositions behave as generalized tensor products. We compute the characteristic polynomial of such symmetric cylindrical constructions in terms of the spectra of the base-graph and the cylinders in a general setting. This gives rise to a simultaneous generalization of some well-known results on the spectra of a variety of graph amalgams, as various graph products, graph subdivisions and generalized Petersen graph constructions. While our main result introduces a connection between spectral graph theory and commutative decompositions of graphs, we focus on commutative cyclic decompositions of complete graphs and tree-cylinders along with a subtle group labeling of trees to introduce a class of highly symmetric graphs containing the Petersen and the Coxeter graphs. Also, using techniques based on recursive polynomials we compute the characteristic polynomials of these highly symmetric graphs as an application of our main result.     

Some magnetohydrodynamics of a thin body in perpendicular fields

Résumé Dans cet article, on considère le mouvement d'un fluide compressible non visqueux dans un champ magnétique perpendiculaire, en présence d'un corps cylindrique dont la section dans le planx 0y forme un profil mince. La conductivité électrique est infinie. Les forces qui agissent sur le corps ont été calculées.Les équations magnéto-hydrodynamiques sont du type hyperbolique pourB ²<0 et du type hyperliptique pourB ²>0, avecB ² étant défini parB ²A ²+M ²–A ² M ² tandis queA etM représentant respectivement les nombres Alfvén et Mach. On démontre qu'il y a une discontinuité infinie dans les forces qui agissent sur le corps pour quelques valeurs deA etM, à moins qu'on ne transfère la condition Kutta du bord de fuite au bord d'attaque du corps.On démontre également que siB ² est négatif et tend vers zéro, les forces développent une discontinuité infinie, mais que siB ² est positif et tend vers zéro, les forces sont finies pour toutes les valeurs finies deA.     

Algorithms for highly symmetric linear and integer programs

This paper deals with exploiting symmetry for solving linear and integer programming problems. Basic properties of linear representations of finite groups can be used to reduce symmetric linear programming to solving linear programs of lower dimension. Combining this approach with knowledge of the geometry of feasible integer solutions yields an algorithm for solving highly symmetric integer linear programs which only takes time which is linear in the number of constraints and quadratic in the dimension.     

Some symmetric systems of minimal surfaces

In this paper we use a method of an earlier paper in order to prove the existence of some symmetric systems of minimal surfaces bounded by curves having self-intersections.     

On the chromatic number of certain highly symmetric graphs

For 1 ⩽ k ⩽ n, let V(n, k) denote the set of n(n − 1) … (n − k + 1) sequences of k distinct elements from {1, …, n}. Let us define the graph Γ(n, k) on the vertex set V(n, k) by joining two sequences if they differ at exactly one place. We investigate the chromatic number and another related parameter of these graphs. We give a sharp answer for some infinite families, using the theory of sharply transitive permutation groups. The problems discussed are related to a question of Henkin, Monk and Tarski in mathematical logic.     

Some results on symmetric double starlike trees

A tree is called starlike if it has exactly one vertex of degree greater than two. In [2] it was proved that two starlike trees are cospectral if and only if they are isomorphic. A tree is called double starlike if it has exactly two adjacent vertices of degree greater than two. We prove here that there exist no two cospectral non-isomorphic symmetric double starlike trees.     

Some problems concerning centrally symmetric convex bodies

The conjecture that among convex bodies Q in Rⁿ, with a center of symmetry at the origin, for which , the value of is a maximum when Q is the layer between two hyperplanes, is proved for n=2 and n=3. Various approaches to the problem are discussed as well as related unsolved problems. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 45, pp. 75–82, 1974.     

Some remarks on the symmetric rank-one update

We consider the symmetric rank-one, quasi-Newton formula. The hereditary properties of this formula do not require quasi-Newton directions of search. Therefore, this formula is easy to use in constrained optimization algorithms; no explicit projections of either the Hessian approximations or the parameter changes are required. Moreover, the entire Hessian approximation is available at each iteration for determining the direction of search, which need not be a quasi-Newton direction. Theoretical difficulties, however, exist. Even for a positive-definite, quadratic function with no constraints, it is possible that the symmetric rank-one update may not be defined at some iteration. In this paper, we first demonstrate that such failures of definition correspond to either losses of independence in the directions of search being generated or to near-singularity of the Hessian approximation being generated. We then describe a procedure that guarantees that these updates are well-defined for any nonsingular quadratic function. This procedure has been incorporated into an algorithm for minimizing a function subject to box constraints. Box constraints arise naturally in the minimization of a function with many minima or a function that is defined only in some subregion of the space.