Block-transitive designs in affine spaces

This paper deals with block-transitive t-(v, k, λ) designs in affine spaces for large t, with a focus on the important index λ = 1 case. We prove that there are no non-trivial 5-(v, k, 1) designs admitting a block-transitive group of automorphisms that is of affine type. Moreover, we show that the corresponding non-existence result holds for 4-(v, k, 1) designs, except possibly when the group is 1-D affine. Our approach involves a consideration of the finite 2-homogeneous affine permutation groups.     

Decomposition of complete multigraphs into crown graphs

Let λ K _v be the complete multigraph, G a finite simple graph. A G-design of λ K _v is denoted by GD(v,G,λ). The crown graph Q _n is obtained by joining single pendant edge to each vertex of an n-cycle. We give new constructions for Q _n -designs. Let v and λ be two positive integers. For n=4, 6, 8 and λ≥1, there exists a GD(v,Q _n ,λ) if and only if either (1) v>2n and λ v(v?1)≡0 (mod 4n), or (2) v=2n and λ≡0 (mod 4). Let n≥4 be even. Then (1) there exists a GD(2n,Q _n ,λ) if and only if λ≡0 (mod 4). (2) There exists a GD(2n+1,Q _n ,λ) when λ≡0 (mod 4).     

A bijective enumeration of labeled trees with given indegree sequence

For a labeled tree on the vertex set {1,2,…,n}, the local direction of each edge (ij) is from i to j if i<j. For a rooted tree, there is also a natural global direction of edges towards the root. The number of edges pointing to a vertex is called its indegree. Thus the local (resp. global) indegree sequence λ=e₁¹e₂²… of a tree on the vertex set {1,2,…,n} is a partition of n−1. We construct a bijection from (unrooted) trees to rooted trees such that the local indegree sequence of a (unrooted) tree equals the global indegree sequence of the corresponding rooted tree. Combining with a Prüfer-like code for rooted labeled trees, we obtain a bijective proof of a recent conjecture by Cotterill and also solve two open problems proposed by Du and Yin. We also prove a q-multisum binomial coefficient identity which confirms another conjecture of Cotterill in a very special case.     

A reduction theorem for the McKay conjecture

The McKay conjecture asserts that for every finite group G and every prime p, the number of irreducible characters of G having p’-degree is equal to the number of such characters of the normalizer of a Sylow p-subgroup of G. Although this has been confirmed for large numbers of groups, including, for example, all solvable groups and all symmetric groups, no general proof has yet been found. In this paper, we reduce the McKay conjecture to a question about simple groups. We give a list of conditions that we hope all simple groups will satisfy, and we show that the McKay conjecture will hold for a finite group G if every simple group involved in G satisfies these conditions. Also, we establish that our conditions are satisfied for the simple groups PSL₂(q) for all prime powers q≥4, and for the Suzuki groups Sz(q) and Ree groups R(q), where q=2 ^e or q=3 ^e respectively, and e>1 is odd. Since our conditions are also satisfied by the sporadic simple group J ₁, it follows that the McKay conjecture holds (for all primes p) for every finite group having an abelian Sylow 2-subgroup.     

Modular Hadamard matrices and related designs,III

This paper continues the investigations presented in two previous papers on the same subject by the author and A. T. Butson. Modular Hadamard matrices havingn odd andh ≡ ? 1 (modn) are studied for a few values of the parametersn andh. Also, some results are obtained for the two related combinatorial designs. These results include: a discussion on the known techniques for constructing pseudo (v, k, λ)-designs; the fact that the existence of one of the two related designs always implies the existence of the other; and some information about the column sums of the incidence matrix of each of the two ‘maximal’ cases of (m, v, k ₁,λ ₁,k ₂,λ ₂,f, λ ₃)-designs.     

The resolvent of a dilation-analytic three-particle system

If the potential in a three-particle system is the boundary value of an analytic function, the physical Hamiltonian H(0) has a dilation-analytic continuation H(φ). The continuous spectrum of H(φ) consists of half-lines Y(λ_p, φ) starting at the thresholds λ_p of scattering channels and making angles 2φ with the positive real axis. If the interaction is the sum of local two-body potentials in suitable $\text{L}$^p-spaces, each half-line Y(λ_p, φ) is associated with an operator P(λ_p, φ) that projects onto an invariant subspace of H(φ). Suppose Y(λ_p, φ) does not pass through any two- or three-particle eigenvalues λ ≠ λ_p when φ runs through some interval $\text{0 < α ? φ ? β <}\text{π}\text{2}$. For φ in [α, β], this paper shows that the resolvent R(λ, φ) has smoothness properties near Y(λ_p, φ) that are sufficient for P(λ_p, φ)[H(φ) ? λ_p] e^?2iφ to be spectral and to generate a strongly differentiable group. The projection, the group, and the spectral resolution operators are norm continuous in φ. These results are not affected by any spurious poles of the resolvent equation. At a spurious pole λ = λ_p + ze^2iφ, the resolvent R(λ_p + ze^2iφ,φ) is examined by a method that uses two resolvent equations in succession and shows that there is norm continuity in z, φ. The case of spurious poles on Y(λ_p, φ) is included.     

Nondegeneracy and uniqueness for boundary blow-up elliptic problems

In this paper, we use for the first time linearization techniques to deal with boundary blow-up elliptic problems. After introducing a convenient functional setting, we show that the problem Δu=λa(x)u^p+g(x,u) in Ω, with u=+∞ on ∂Ω, has a unique positive solution for large enough λ, and determine its asymptotic behavior as λ→+∞. Here p>1, a(x) is a continuous function which can be singular near ∂Ω and g(x,u) is a perturbation term with potential growth near zero and infinity. We also consider more general problems, obtained by replacing u^p by e^u or a “logistic type” function f(u).     

Optimal graphs for chromatic polynomials

Let F(n,e) be the collection of all simple graphs with n vertices and e edges, and for G∈F(n,e) let P(G;λ) be the chromatic polynomial of G. A graph G∈F(n,e) is said to be optimal if another graph H∈F(n,e) does not exist with P(H;λ)?P(G;λ) for all λ, with strict inequality holding for some λ. In this paper we derive necessary conditions for bipartite graphs to be optimal, and show that, contrarily to the case of lower bounds, one can find values of n and e for which optimal graphs are not unique. We also derive necessary conditions for bipartite graphs to have the greatest number of cycles of length 4.     

Infinite families of 2- and 3-designs with parameters v = p + 1, k = (p − 1)/2i + 1, where p odd prime, 2e T (p − 1), e ≥ 2, 1 ≤ i ≤ e

Let p be an odd prime number such that p − 1 = 2^em for some odd m and e ≥ 2. In this article, by using the special linear fractional group PSL(2, p), for each i, 1 ≤ i ≤ e, except particular cases, we construct a 2-design with parameters v = p + 1, k = (p − 1)/2ⁱ + 1 and λ = ((p − 1)/2ⁱ+1)(p − 1)/2 = k(p − 1)/2, and in the case i = e we show that some of these 2-designs are 3-designs. Likewise, by using the linear fractional group PGL(2,p) we construct an infinite family of 3-designs with the same v k and λ = k(k − 2). These supplement a part of [4], in which we gave an infinite family of 3-designs with parameters v = q + 1, k = (q + 1)/2 = (q − 1)/2 + 1 and λ = (q + 1)(q − 3)/8 = k(k − 2)/2, where q is a prime power such that q − 1 = 2m for some odd m and q > 7. Some of the designs given in this article and in [4] fill in a few blanks in the table of Chee, Colbourn, and Kreher [2]. © 1997 John Wiley & Sons, Inc.     

Extending t-designs

Three extension theorems for t-designs are proved; two for t even, and one for t odd. Another theorem guaranteeing that certain t-designs be (t + 1)-designs is presented. The extension theorem for odd t is used to show that every group of odd order 2k + 1, k ≠ 2^r ? 1, acts as an automorphism group of a 2-(2k + 2, k + 1, λ) design consisting of exactly one half of the (k + 1)-settled, Although the question of the existence of a 6-(14, 7, 4) design is not settled, certain requisite properties of the 4-designs on 12 elements derived from such a design are established. All of these results depend heavily upon generalizations of block intersection number equations of N. S. Mendelsohn.     

Super-simple, Pan-orientable, and Pan-decomposable BIBDs with Block Size 4 and Related Structures

Let v, k, and μ be positive integers. A tournament T of order k, briefly k-tournament, is a directed graph on k vertices in which there is exactly one directed edge between any two vertices. A (v, k, λ = 2μ)-BIBD is called T-orientable if for each of its blocks B, it is possible to replace B by a copy of T on the set B so that every ordered pair of distinct points appears in exactly μ k-tournaments. A (v, k, λ = 2μ)-BIBD is called pan-orientable if it is T-orientable for every possible k-tournament T. In this paper, we continue the earlier investigations and complete the spectrum for (v, 4, λ = 2μ)-BIBDs which possess both the pan-orientable property and the pan-decomposable property first introduced by Granville et al. (Graphs Comb 5:57–61, 1989). For all μ, we are able to show that the necessary existence conditions are sufficient. When λ = 2 and v > 4, our designs are super-simple, that is they have no two blocks with more than two common points. One new corollary to this result is that there exists a (v, 4, 2)-BIBD which is both super-simple and directable for all v ≡ 1, 4 (mod 6), v > 4. Finally, we investigate the existence of pan-orientable, pan-decomposable (v, 4, λ = 2μ)-BIBDs with a pan-orientable, pan-decomposable (w, 4, λ = 2μ)-BIBD as a subdesign; here we obtain complete results for λ = 2, 4, but there remain several open cases for λ = 6 (mostly for v < 4w), and the case λ = 12 still has to be investigated.     

The parabolic map f1/e(z)=(1/e)e

We consider the exponential maps ?_λ : ? → ? defined by the formula ?_λ (z) = λe^z, λ(0,1/e]. Let J_r(?_λ) be the subset of the Julia set consisting of points that do not escape to infinity under forward iterates of ?. Our main result is that the function λh_λ :=HD(J_r(?_λ),)), λ(0, 1/e], is continuons at the point 1/e. As a preparation for this result we deal with the map ?₁/e itself. We prove that the h₁/e-dimensional Hausdorff measure of J_r(?₁/e) is positive and finite on each horizontal strip, and that the h₁/e-dimensional packing measure of J_r(?_λ) is locally infinite at each point of J_r(?_λ). Our main technical devices are formed by the, associated with ?_λ, maps F_λ defined on some strip P of height 2π and also associated with them tonformal measures.     

Computational complexity of reconstruction and isomorphism testing for designs and line graphs

Graphs with high symmetry or regularity are the main source for experimentally hard instances of the notoriously difficult graph isomorphism problem. In this paper, we study the computational complexity of isomorphism testing for line graphs of t-(v,k,λ) designs. For this class of highly regular graphs, we obtain a worst-case running time of O(vlogv+O(1)) for bounded parameters t, k, λ.In a first step, our approach makes use of the Babai-Luks algorithm to compute canonical forms of t-designs. In a second step, we show that t-designs can be reconstructed from their line graphs in polynomial-time. The first is algebraic in nature, the second purely combinatorial. For both, profound structural knowledge in design theory is required. Our results extend earlier complexity results about isomorphism testing of graphs generated from Steiner triple systems and block designs.     

On a composition of cyclic 2-designs

A CB(v,k,λ) means a cyclic 2-design of block size k coincidence number λ, and with v points. In this paper, a recursive construction of a CB(v,k,λ) from two or three cyclic 2-designs is given.     

p-cyclic matrices and the symmetric successive overrelaxation method

In this paper, the new functional equation, [λ?(1?ω)²]^p=λ[λ+1?ω]^p-2(2?ω)²ω^pμ^p, which connects the eigenvalues μ of a particular weakly cyclic (of index p) Jacobi matrix B to the eigenvalues λ of its associated symmetric successive overrelaxation (SSOR) matrix S_ω, is derived. This functional equation is then applied to the problem of determining bounds for the intervals of convergence and divergence of the SSOR iterative method for classes of H-matrices.     

On the maximum number of permutations with given maximal or minimal distance

Let us denote by R(k, ? λ)[R(k, ? λ)] the maximal number $\text{M}$ such that there exist $\text{M}$ different permutations of the set {1,…, k} such that any two of them have at least λ (at most λ, respectively) common positions. We prove the inequalities R(k, ? λ) ? kR(k ? 1, ? λ ? 1), R(k, ? λ) ? R(k, ? λ ? 1) ? k!, R(k, ? λ) ? kR(k ? 1, ? λ ? 1). We show: R(k, ? k ? 2) = 2, R(k, ? 1) = (k ? 1)!, R(p^m, ? 2) = (p^m ? 2)!, R(p^m + 1, ? 3) = (p^m ? 2)!, $\text{R(k, ? k ? 3) =}\text{k!}\text{2}$, R(k, ? 0) = k, R(p^m, ? 1) = p^m(p^m ? 1), R(p^m + 1, ? 2) = (p^m + 1)p^m(p^m ? 1). The exact value of R(k, ? λ) is determined whenever k ? k₀(k ? λ); we conjecture that R(k, ? λ) = (k ? λ)! for k ? k₀(λ). Bounds for the general case are given and are used to determine that the minimum of |R(k, ? λ) ? R(k, ? λ)| is attained for $\text{λ = (}\text{k}\text{2}\text{) + O(}\text{k}\text{log}\text{k}\text{)}$.     

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.      

Resolvable t-Designs

A general group theoretic approach is used to find resolvable designs. Infinitely many resolvable 3-designs are obtained where each is block transitive under some PSL(2, p ^f ) or PGL(2, p ^f ). Some known Steiner 5-designs are assembled from such resolvable 3-designs such that they are also resolvable. We give some visualizations of Steiner systems which make resolvability obvious.     

The existence of matrices with prescribed characteristic and permanental polynomials

Let d(λ) and p(λ) be monic polynomials of degree n?2 with coefficients in F, an algebraically closed field or the field of all real numbers. Necessary and sufficient conditions for the existence of an n-square matrix A over F such that det(λI?A)=d(λ) and per(λI?A=p(λ) are given in terms of the coefficients of d(λ) and p(λ).     

On counting Sperner families

It is proved that balanced 3-designs B₃[k, λ, v] exist for k = 5, λ = 30 and every v ? 5.