Generalized quadrangles admitting PSL(2,q) × PSL(2,q)

In this paper, we classify the generalized quadrangles of order (s,t), s ≠ 1 ≠ t, which admit the natural action of PSL(2,s) × PSL(2,s) on a subGQ of order (s,1). This generalizes a recent result of J. De Kaey and H. Van Maldeghem 3 , by whom the classification was obtained for the case s = t. © 2005 Wiley Periodicals, Inc. J Combin Designs.     

Digraphs containing every possible pair of dicycles

Let D = (V, A) be a directed graph of order n ≥ 4. Suppose that the minimum degree of D is at least (3n − 3)/2. Then for any two integers s and t with s ≥ 2, t ≥ 2 and s + t ≤ n, D contains two vertex‐disjoint directed cycles of lengths s and t, respectively. Moreover, the condition on the minimum degree is sharp. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 154–162, 2000     

On the structure of 1-designs with at most two block intersection numbers

We introduce the notion of an unrefinable decomposition of a 1-design with at most two block intersection numbers, which is a certain decomposition of the 1-designs collection of blocks into other 1-designs. We discover an infinite family of 1-designs with at most two block intersection numbers that each have a unique unrefinable decomposition, and we give a polynomial-time algorithm to compute an unrefinable decomposition for each such design from the family. Combinatorial designs from this family include: finite projective planes of order n; SOMAs, and more generally, partial linear spaces of order (s, t) on (s + 1)² points; as well as affine designs, and more generally, strongly resolvable designs with no repeated blocks.      

The existence of howell designs of siden+1 and order 2n

AHowell design of side s andorder 2n, or more briefly, anH(s, 2n), is ans×s array in which each cell either is empty or contains an unordered pair of elements from some 2n-set, sayX, such that (a) each row and each column is Latin (that is, every element ofX is in precisely one cell of each row and each column) and (b) every unordered pair of elements fromX is in at most one cell of the array. Atrivial Howell design is anH(s, 0) havingX=? and consisting of ans×s array of empty cells. A necessary condition onn ands for the existence of a nontrivialH(s, 2n) is that 0<n≦s≦2n-1. AnH(n+t, 2n) is said to contain a maximum trivial subdesign if somet×t subarray is theH(t, 0). This paper describes a recursive construction for Howell designs containing maximum trivial subdesigns and applies it to settle the existence question forH(n+1, 2n)’s: forn+1 a positive integer, there is anH(n+1, 2n) if and only ifn+1 ∉ {2, 3, 5}.     

Minimal string difference encodings

Given two strings s and t, a difference encoding is a third string that contains sufficient information to derivet t from s. An algorithm is presented which derives a difference encoding that can be represented in the fewest number of bits relative to the string edit operators insert, delete, replace, and skip. This algorithm has practical significance for distributed text processing applications.     

On decomposition of triangle-free graphs under degree constraints

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 7–9, 1998     

On the Exceptional Zeros of Rankin–Selberg L-Functions

The main objects of study in this article are two classes of Rankin–Selberg L-functions, namely L(s,f×g) and L(s, sym²(g)× sym²(g)), where f,g are newforms, holomorphic or of Maass type, on the upper half plane, and sym²(g) denotes the symmetric square lift of g to GL(3). We prove that in general, i.e., when these L-functions are not divisible by L-functions of quadratic characters (such divisibility happening rarely), they do not admit any LandauSiegel zeros. Such zeros, which are real and close to s=1, are highly mysterious and are not expected to occur. There are corollaries of our result, one of them being a strong lower bound for special value at s=1, which is of interest both geometrically and analytically. One also gets this way a good bound onthe norm of sym²(g).     

Most balanced minimum cuts

We consider the problem of finding most balanced cuts among minimum st-edge cuts and minimum st-vertex cuts, for given vertices s and t, according to different balance criteria. For edge cuts we seek to maximize . For vertex cuts C of G we consider the objectives of (i) maximizing min{|S|,|T|}, where {S,T} is a partition of V(G)?C with s∈S, t∈T and [S,T]=0?, (ii) minimizing the order of the largest component of G−C, and (iii) maximizing the order of the smallest component of G−C.All of these problems are NP-hard. We give a PTAS for the edge cut variant and for (i). These results also hold for directed graphs. We give a 2-approximation for (ii), and show that no non-trivial approximation exists for (iii) unless P=NP.To prove these results we show that we can partition the vertices of G, and define a partial order on the subsets of this partition, such that ideals of the partial order correspond bijectively to minimum st-cuts of G. This shows that the problems are closely related to Uniform Partially Ordered Knapsack (UPOK), a variant of POK where element utilities are equal to element weights. Our algorithm is also a PTAS for special types of UPOK instances.     

The Ramsey number R(3, t) has order of magnitude t2/log t

The Ramsey number R(s, t) for positive integers s and t is the minimum integer n for which every red-blue coloring of the edges of a complete n-vertex graph induces either a red complete graph of order s or a blue complete graph of order t. This paper proves that R(3, t) is bounded below by (1 – o(1))t/²/log t times a positive constant. Together with the known upper bound of (1 + o(1))t²/log t, it follows that R(3, t) has asymptotic order of magnitude t²/log t. © 1995 John Wiley & Sons, Inc.     

Zeros of Asai-Eisenstein series

We generalize a result of Max Deuring on the zeros of Zeta-function of quadratic forms to Asai's non-holomophic Eisenstein series E(z,s) of the Hilbert modular group. We prove that inside the rectangular and −1≤Re(s) ≤ 2 the function E(z,s) has only simple zeros on the line Re(s)=1/2 and two simple real zeros, if |N(y)| is large. The research was supported by a fellowship within the Post-doc-Program of the DAAD (German Academic Exchange Service)     

Determination of generalized quadrangles with distinct elation points

In this paper, we classify the finite generalized quadrangles of order (s,t), s,t > 1, which have a line L of elation points, with the additional property that there is a line M not meeting L for which {L, M} is regular. This is a first fundamental step towards the classification of those generalized quadrangles having a line of elation points. Mathematics Subject Classification (2000): 51E12, 51E20, 20B25, 20E42     

On Strassen's version of the law of the iterated logarithm for the two-parameter Gaussian process

Strassen's version of the law of the iterated logarithm is extended to the two-parameter Gaussian process {X(s, t); ε(s, t) [0, ∞)²} with the covariance function R((s₁,t₁),(s₂,t₂)) = min(s₁,s₂)min(t₁,t₂).     

Constant tolerance intersection graphs of subtrees of a tree

A chordal graph is the intersection graph of a family of subtrees of a host tree. In this paper we generalize this. A graph G=(V,E) has an (h,s,t)-representation if there exists a host tree T of maximum degree at most h, and a family of subtrees {S_v}_v∈V of T, all of maximum degree at most s, such that uv∈E if and only if |S_u∩S_v|?t. For given h,s, and t, there exist infinitely many forbidden induced subgraphs for the class of (h,s,t)-graphs. On the other hand, for fixed h?s?3, every graph is an (h,s,t)-graph provided that we take t large enough. Under certain conditions representations of larger graphs can be obtained from those of smaller ones by amalgamation procedures. Other representability and non-representability results are presented as well.     

Directed star decompositions of the complete directed graph

An (s, t)-directed star is a directed graph with s + t + 1 vertices and s + t arcs; s vertices have indegree zero and outdegree one, t have indegree one and outdegree zero, and one has indegree s and outdegree t. An (s, t)-directed star decomposition is a partition of the arcs of a complete directed graph of order n into (s, t)-directed starsx. We establish necessary and sufficient conditions on s, t, and n for an (s, t)-directed star decomposition of order n to exist.     

A generalized quadrangle of order (s, t) with center of transitivity is an elation quadrangle if s ≤ t

We show that a generalized quadrangle of order (s, t) with a center of transitivity is an elation generalized quadrangle if s ≤ t. In order to obtain this result, we generalize Frohardt’s result on Kantor’s conjecture from elation quadrangles to the more general case of quadrangles with a center of transitivity.      

A Uniform Approach to the Analysis of Trie Structures That Store Prefixing-Keys

Triesare data structures for storing sets where each element is represented by a key that can be viewed as a string of characters over a finite alphabet. These structures have been extensively studied and analyzed under several probability models. All of these models, however, preclude the occurrence of sets in which the key of one element is a prefix of that of another—such a key is called aprefixing-key. This paper presents an average case analysis of several trie varieties, which we generically calledprefixing-tries, for representing sets with “unrestricted” keys, that is, sets in which the key of one element may be a prefix of that of another. The underlying probability model, which we call theprefix model, _{h, n, m}assumes as equally likely alln-element sets whose keys are composed of at mosthcharacters from a fixed alphabet of sizem. For each of the trie varieties analyzed, we derive exact formulas for the expected space required to store such a set, and the average time required to retrieve an element given its key, as functions ofh,n, andm. Our approach to the analysis is of interest in its own right. It provides a unifying framework for computing the expectations of a wide class of random variables with respect to the prefix model. This class includes the cost functions of the trie varieties analyzed here.     

Optimal boundary displacement control of string vibrations with a nonlocal evenness condition of the second kind

We study the behavior of a string with the nonlocal boundary condition u _x (l, t) = u _x ($ x^\circ $ x^\circ , t). A displacement control u(0, t) = μ(t) bringing the string from an arbitrarily given initial state to an arbitrarily given terminal state is applied at the left endpoint of the string. For the initial and terminal functions, we find necessary and sufficient conditions for the controllability of the string. Under these conditions, we carry out optimization; i.e., of all admissible controls, we choose a control minimizing the boundary energy integral.     

Construction of Williamson type matrices

Recent advances in the construction of Hadamard matrices have depeaded on the existence of Baumert-Hall arrays and four (1, ?1) matrices A B C Dof order m which are of Williamson type, that is they pair-wise satisfy

i) MN^T = NM^T , ∈ {A B C D} and

ii) AA^T + BB^T + CC^T + DD^T = 4mI_m .

It is shown that Williamson type matrices exist for the orders m = s(4 ? 1)m = s(4s + 3) for s∈ {1, 3, 5, …, 25} and also for m = 93. This gives Williamson matrices for several new orders including 33, 95,189.

These results mean there are Hadamard matrices of order

i) 4s(4s ?1)t, 20s(4s ? 1)t,s ∈ {1, 3, 5, …, 25};

ii) 4s(4:s + 3)t, 20s(4s + 3)t s ∈ {1, 3, 5, …, 25};

iii) 4.93t, 20.93t

for

t ∈ {1, 3, 5, … , 61} ∪ {1 + 2 ^a 10 ^b 26 ^c a b c nonnegative integers}, which are new infinite families.

Also, it is shown by considering eight-Williamson-type matrices, that there exist Hadamard matrices of order 4(p + 1)(2p + l)r and 4(p + l)(2p + 5)r when p ≡ 1 (mod 4) is a prime power, 8ris the order of a Plotkin array, and, in the second case 2p + 6 is the order of a symmetric Hadamard matrix. These classes are new.