Resolutions of PG(5, 2) with point‐cyclic automorphism group

A t‐(υ, k, λ) design is a set of υ points together with a collection of its k‐subsets called blocks so that all subsets of t points are contained in exactly λ blocks. The d‐dimensional projective geometry over GF(q), PG(d, q), is a 2‐(q^d + q^d−1 + … + q + 1, q + 1, 1) design when we take its points as the points of the design and its lines as the blocks of the design. A 2‐(υ, k, 1) design is said to be resolvable if the blocks can be partitioned as ℛ = {R₁, R₂, …, R_s}, where s = (υ − 1)/(k−1) and each R_i consists of υ/k disjoint blocks. If a resolvable design has an automorphism σ which acts as a cycle of length υ on the points and ℛ^σ = ℛ, then the design is said to be point‐cyclically resolvable. The design associated with PG(5, 2) is known to be resolvable and in this paper, it is shown to be point‐cyclically resolvable by enumerating all inequivalent resolutions which are invariant under a cyclic automorphism group G = 〈σ〉 where σ is a cycle of length 63. These resolutions are the only resolutions which admit a point‐transitive automorphism group. Furthermore, some necessary conditions for the point‐cyclic resolvability of 2‐(υ, k, 1) designs are also given. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 2–14, 2000     

Locally s‐distance transitive graphs

We give a unified approach to analyzing, for each positive integer s, a class of finite connected graphs that contains all the distance transitive graphs as well as the locally s‐arc transitive graphs of diameter at least s. A graph is in the class if it is connected and if, for each vertex v, the subgroup of automorphisms fixing v acts transitively on the set of vertices at distance i from v, for each i from 1 to s. We prove that this class is closed under forming normal quotients. Several graphs in the class are designated as degenerate, and a nondegenerate graph in the class is called basic if all its nontrivial normal quotients are degenerate. We prove that, for s≥2, a nondegenerate, nonbasic graph in the class is either a complete multipartite graph or a normal cover of a basic graph. We prove further that, apart from the complete bipartite graphs, each basic graph admits a faithful quasiprimitive action on each of its (1 or 2) vertex‐orbits or a biquasiprimitive action. These results invite detailed additional analysis of the basic graphs using the theory of quasiprimitive permutation groups. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:176‐197, 2012     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A Steiner 5-Design on 36 Points

Up to now, all known Steiner 5-designs are on q + 1 points where q 3 (mod 4) is a prime power and the design is admitting PSL(2, q) as a group of automorphisms. In this article we present a 5-(36,6,1) design admitting PGL(2, 17) × C ₂ as a group of automorphisms. The design is unique with this automorphism group and even for the commutator group PSL(2, 17) × Id ₂ of this automorphism group there exists no further design with these parameters. We present the incidence matrix of t-orbits and block orbits.     

Some reproducing identities for families of mean values

Gini, Lehmer, Beckenbach, and others studied the meanG _s (a, b) = (a ^s +b ^s )/(a ^{s 1} +b ^s-1 ) We proveTheorem 1 The identity (ina, b)G _s (G _t ,G _u ) =G _v holds if and only if (s, t, u, v) is (s, t, t, t) (the trivial solution) or one of (1, 1 –k, 1 +k, 1), (1/2, 1 –k, k, 1/2), or (0,–k, k, 0) (the exotic solutions,k is any real number)Theorem 2 IfP _s (a, b) is the power mean [(a ^s +b ^s )/2]^1/s , thenP _s (P _t ,P _u ) =P _v has only the trivial solution (s, t, u, v) = (s, t, t, t) and the exotic solution (0,t, –t, 0) The family of meansG _s (respP _s ) includes the classical arithmetic, geometric, and harmonic means     

A combinatorial approach to transitive extensions of generously unitransitive permutation groups

Motivated by symmetric association schemes (which are known to approximate generously unitransitive group actions), we formulate combinatorial approximations to transitive extensions of generously unitransitive permutation groups. Specifically, the notions of compatible and coherent partitions are suggested and investigated in terms of the orbits of an ambient group (H, Ω) on the k‐subsets of Ω, k=2, 3, 4. We apply these ideas to investigate transitive extensions of the automorphism groups of the classical Johnson and Hamming schemes. In the latter case, we further provide algorithmic details and computer‐generated data for the particular series of Hamming schemes H(m, 3), m⩾2. Finally, our approach is compared to the concept of a symmetric association scheme on triples in the sense of Mesner and Bhattacharya. © 2010 Wiley Periodicals, Inc. J Combin Designs 18:369–391, 2010     

A constructive approach for the lower bounds on the Ramsey numbers R (s,t)

Graph G is a (k, p)‐graph if G does not contain a complete graph on k vertices K_k, nor an independent set of order p. Given a (k, p)‐graph G and a (k, q)‐graph H, such that G and H contain an induced subgraph isomorphic to some K_k?1‐free graph M, we construct a (k, p + q ? 1)‐graph on n(G) + n(H) + n(M) vertices. This implies that R (k, p + q ? 1) ≥ R (k, p) + R (k, q) + n(M) ? 1, where R (s, t) is the classical two‐color Ramsey number. By applying this construction, and some its generalizations, we improve on 22 lower bounds for R (s, t), for various specific values of s and t. In particular, we obtain the following new lower bounds: R (4, 15) ≥ 153, R (6, 7) ≥ 111, R (6, 11) ≥ 253, R (7, 12) ≥ 416, and R (8, 13) ≥ 635. Most of the results did not require any use of computer algorithms. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 231–239, 2004     

Planar embeddings with infinite faces

We investigate vertex‐transitive graphs that admit planar embeddings having infinite faces, i.e., faces whose boundary is a double ray. In the case of graphs with connectivity exactly 2, we present examples wherein no face is finite. In particular, the planar embeddings of the Cartesian product of the r‐valent tree with K₂ are comprehensively studied and enumerated, as are the automorphisms of the resulting maps, and it is shown for r = 3 that no vertex‐transitive group of graph automorphisms is extendable to a group of homeomorphisms of the plane. We present all known families of infinite, locally finite, vertex‐transitive graphs of connectivity 3 and an infinite family of 4‐connected graphs that admit planar embeddings wherein each vertex is incident with an infinite face. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 257–275, 2003     

Linkage between Adiabatic Invariance and Symmetry of Solutions

In this article, for the symmetric pendulum equation and the symmetric bisuperlinear equation respectively, we show that there are two one-parameter families of solutions, y_s and y_a, so that one is adiabatically symmetric, y_s(?t)=y_s(t)+o(ε^k) for all k≥0, and the other adiabatically antisymmetric, y_a(?t)=?y_a(t)+o(ε^k) for all k≥0. By using the techniques of exponential asymptotics to calculate y′_s(0) and y_a(0), we demonstrate that, in general, they are not genuinely symmetric or antisymmetric, because these quantities are in fact exponentially small. Finally, after establishing a relationship between the total change in the leading-order adiabatic invariant and the quantity y′_s(0) for the family of solutions y_s of the bisuperlinear equation, we are able to reveal explicitly how the behavior of the adiabatic invariant depends on the complex singularities of the equation.      

An Optimal Multisecret Threshold Scheme Construction

A multisecret threshold scheme is a system which protects a number of secret keys among a group of n participants. There is a secret s_K associated with every subset K of k participants such that any t participants in K can reconstruct the secret s_K, but a subset of w participants cannot get any information about a secret they are not associated with. This paper gives a construction for the parameters t = 2, k = 3 and for any n and w that is optimal in the sense that participants hold the minimal amount of information. Communicated by: P. Wild     

Smooth automorphisms and path-connectedness in Borel dynamics

Let Aut(X, B) be the group of all Borel automorphisms of a standard Borel space (X, B). We study topological properties of Aut(X, B) with respect to the uniform and weak topologies, τ and p, defined in [Bezuglyi S., Dooley A.H., Kwiatkowski J., Topologies on the group of Borel automorphisms of a standard Borel space, Preprint 2003]. It is proved that the class of smooth automorphisms is dense in (Aut(X, B), p). Let Ctbl(X) denote the group of Borel automorphisms with countable support. It is shown that the topological group Aut₀(X, B) = Aut(X, B)/Ctbl(X) is path-connected with respect to the quotient topology τ₀. It is also proved that Aut₀(X, B) has the Rokhlin property in the quotient topology p₀, i.e., the action of Aut₀(X,B) on itself by conjugation is topologically transitive.     

Direct decompositions of torsion-free Abelian groups of finite rank

It is proved that ifr ₁ ,r ₂ , ...,r _s ;l ₁ ,l ₂ , ...,l _t are the ranks of the indecomposable summands of two direct decompositions of a torsion-free Abelian group of finite rank and if s₀ is the number of units among the numbers r_i, while t₀ is the number of units among the numbers l_j, thenr _i ⩽n - t ₀ ,l _j ⩽n−s ₀ for all i, j. Moreover, if for some i we have r_i=n−t₀, then among the l_j's only one term is different from 1 and it is equal to n−t₀; similarly if l_j=n−s₀ for some j. In addition, a construction is presented, allowing to form, from several indecomposable groups, a new group, called a flower group, and it is proved that a flower group is indecomposable under natural restrictions on its defining parameters. Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 160, pp. 272–285, 1987.     

Oscillation in Linear Differential Equations with Continuous Distribution of Time Lag

The purpose of this paper is to study oscillation of solutions of the following equation where D_k ? B (C[-r, 0], R ), k = 0, 1,…,n, r > 0, const, x_t(s) = x(t + s). Under very generic conditions, we show that the oscillatory property of (1) can be determined from the behavior of the characteristic.     

Multicommodity flows in graphs

Suppose that G is a graph, and (s_i,t_i) (1≤i≤k) are pairs of vertices; and that each edge has a integer-valued capacity (≥0), and that q_i≥0 (1≤i≤k) are integer-valued demands. When is there a flow for each i, between s_i and t_i and of value q_i, such that the total flow through each edge does not exceed its capacity? Ford and Fulkerson solved this when k=1, and Hu when k=2. We solve it for general values of k, when G is planar and can be drawn so that s₁,…, s_l, t₁, …, t_l,…,t_l are all on the boundary of a face and s_l+1, …,S_k, t_l+1,…,t_k are all on the boundary of the infinite face or when t₁=?=t_l and G is planar and can be drawn so that s_l+1,…,s_k, t₁,…,t_k are all on the boundary of the infinite face. This extends a theorem of Okamura and Seymour.     

A note on k‐shortest paths problem

It is well‐known that in a directed graph, if deleting any edge will not affect the shortest distance between two specific vertices s and t, then there are two edge‐disjoint paths from s to t and both of them are shortest paths. In this article, we generalize this to shortest k edge‐disjoint s‐t paths for any positive integer k. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 34‐37, 2011     

On a class of Besicovitch functions to have exact box dimension: A necessary and sufficient condition

Let 1 < s < 2, λ_k > 0 with λ_k → ∞ satisfy λ_k+1/λ_k ≥ λ > 1. For a class of Besicovich functions B(t) = sin λ_kt, the present paper investigates the intrinsic relationship between box dimension of their graphs and the asymptotic behavior of {λ_k}. We show that the upper box dimension does not exceed s in general, and equals to s while the increasing rate is sufficiently large. An estimate of the lower box dimension is also established. Then a necessary and sufficient condition is given for this type of Besicovitch functions to have exact box dimensions: for sufficiently large λ, dim _BΓ(B) = dim _BΓ(B) = s holds if and only if lim_n→∞ = 1. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Class of Simple Derivations of k[x,y]

If k is a field of characteristic zero, c ∈ k?{0}, s, t ≥ 1, and r ≥ 0 are integers, then it is shown that the k-derivation y ^r ? _x  + (y ^s x ^t  + c)? _y of the polynomial algebra k[x, y] is simple.     

Dissipative parabolic equations in locally uniform spaces

The Cauchy problem for a semilinear second order parabolic equation u_t = Δu + f (x, u,?u), (t, x) ∈ ?⁺ × ?^N , is considered within the semigroup approach in locally uniform spaces (?^N ). Global solvability, dissipativeness and the existence of an attractor are established under the same assumptions as for problems in bounded domains. In particular, the condition sf (s, 0 ) < 0, |s | > s₀ > 0, together with gradient's “subquadratic” growth restriction, are shown to guarantee the existence of an attractor for the above mentioned equation. This result cannot be located in the previous references devoted to reaction‐diffusion equations in the whole of ?^N . (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Designs of ϕ-optimal control for second-order processes

Consider a realization of the process on the intervalT=[0,1] for functionsf ₁(t),f ₂(t),...,f _n (t) inH(R), the reproducing kernel Hilbert space with reproducing kernelR(s,t) onT×T, whereR(s,t)=E[ξ(s)ξt)] is assumed to be continuous and known. Problems of the selection of functions {f _k (t)} _k=1 ⁿ to be ϕ-optimal design are given, and an unified approach to the solutions ofD-,A-,E- andD _s-optimal design problems are discussed.     

2-Spreads and Transitive and Orthogonal 2-Parallelisms of PG(5, 2)

A 2-spread is a set of two-dimensional subspaces of PG(d, q), which partition the point set. We establish that up to equivalence there exists only one 2-spread of PG(5, 2). The order of the automorphism group preserving it is 10584. A 2-parallelism is a partition of the set of two-dimensional subspaces by 2-spreads. There is a one-to-one correspondence between the 2-parallelisms of PG(5, 2) and the resolutions of the 2-(63,7,15) design of the points and two-dimensional subspaces. Sarmiento (Graphs and Combinatorics 18(3):621–632, 2002) has classified 2-parallelisms of PG(5, 2), which are invariant under a point transitive cyclic group of order 63. We classify 2-parallelisms with automorphisms of order 31. Among them there are 92 2-parallelisms with full automorphism group of order 155, which is transitive on their 2-spreads. Johnson and Montinaro (Results Math 52(1–2):75–89, 2008) point out that no transitive t-parallelisms of PG(d, q) have been constructed for t > 1. The 92 transitive 2-parallelisms of PG(5, 2) are then the first known examples. We also check them for mutual orthogonality and present a set of ten mutually orthogonal resolutions of the geometric 2-(63,7,15) design.