On Ramsey numbers involving starlike multipartite graphs

The Ramsey number r(G, H) is evaluated exactly in certain cases in which both G and H are complete multipartite graphs K(n,₁, n₂, …. n_k). Specifically, each of the following cases is handled whenever n is sufficiently large: r(K(1, m₁, …. m_k), K(1, n)), r(K(1, m), K(n₁, …. n_k, n)), provided m ≧ 4, and r(K(1, 1, m), K(n_k, …, n_k, n)).     

An Almost Accurate Location of the Maximum Stirling Number(s) of the Second Kind

The Stirling number of the second kind S(n, k) is the number of ways of partitioning a set of n elements into k nonempty subsets. It is well known that the numbers S(n, k) are unimodal in k, and there are at most two consecutive values K _n such that (for fixed n) S(n, K _n ) is maximal. We determine asymptotic bounds for K _n , which are unexpectedly good and improve earlier results. The method used here shows a possible strategy for obtaining numerical bounds such that in almost all cases K _n can be uniquely determined.     

Contributions to zero-sum problems

A prototype of zero-sum theorems, the well-known theorem of Erd?s, Ginzburg and Ziv says that for any positive integer n, any sequence a₁,a₂,…,a_2n-1 of 2n-1 integers has a subsequence of n elements whose sum is 0 modulo n. Appropriate generalizations of the question, especially that for (Z/pZ)^d, generated a lot of research and still have challenging open questions. Here we propose a new generalization of the Erd?s-Ginzburg-Ziv theorem and prove it in some basic cases.     

On the covering multiplicity of lattices

Let the lattice Λ have covering radiusR, so that closed balls of radiusR around the lattice points just cover the space. The covering multiplicityCM(Λ) is the maximal number of times the interiors of these balls overlap. We show that the least possible covering multiplicity for ann-dimensional lattice isn ifn≤8, and conjecture that it exceedsn in all other cases. We determine the covering multiplicity of the Leech lattice and of the latticesI _n, A_n, D_n, E_n and their duals for small values ofn. Although it appears thatCM(I _n)=2 ⁿ⁻¹ ifn≤33, asn → ∞ we haveCM(I _n)∼2.089... ⁿ . The results have application to numerical integration.     

Brauer algebras of simply laced type

The diagram algebra introduced by Brauer that describes the centralizer algebra of the n-fold tensor product of the natural representation of an orthogonal Lie group has a presentation by generators and relations that only depends on the path graph A _{n − 1} on n − 1 nodes. Here we describe an algebra depending on an arbitrary graph Q, called the Brauer algebra of type Q, and study its structure in the cases where Q is a Coxeter graph of simply laced spherical type (so its connected components are of type A _{n − 1}, D _n , E₆, E₇, E₈). We find its irreducible representations and its dimension, and show that the algebra is cellular. The algebra is generically semisimple and contains the group algebra of the Coxeter group of type Q as a subalgebra. It is a ring homomorphic image of the Birman-Murakami-Wenzl algebra of type Q; this fact will be used in later work determining the structure of the Birman-Murakami-Wenzl algebras of simply laced spherical type.     

Classification of solvable Lie algebras with a given nilradical by means of solvable extensions of its subalgebras

We construct all solvable Lie algebras with a specific n-dimensional nilradical n_n,3 which contains the previously studied filiform (n-2)-dimensional nilpotent algebra n_n-2,1 as a subalgebra but not as an ideal. Rather surprisingly it turns out that the classification of such solvable algebras can be deduced from the classification of solvable algebras with the nilradical n_n-2,1. Also the sets of invariants of coadjoint representation of n_n,3 and its solvable extensions are deduced from this reduction. In several cases they have polynomial bases, i.e. the invariants of the respective solvable algebra can be chosen to be Casimir invariants in its enveloping algebra.     

On the invariance principle for U-statistics

Let T_n be a U-statistic and S_n its projection (in the sense of Hájek). Limit theory for U-statistics is usually considered in two disjoint cases, termed degenerate and nondegenerate. The traditional method is to treat the cases separately, using different techniques in each to obtain a solution. Here we present a unified treatment based on a joint invariance principle for the vector (T_n, T_n – S_n), from which the invariance principles in both the degenerate and nondegenerate cases follow as easy corollaries.     

Limit theorems for induced extreme values

For a bivariate sample (X_i, Y_i) of size n, let (U(x), V(x)) denote the following pair of induced extreme values: U(x) is the maximum of those Y_i-values with corresponding X_i-value less than x and V(x) is the maximum of the remaining Y_i-values. In the paper, we study the asymptotic behavior of the (suitably normalized) random vector (U(x), V(x)), and we consider several cases. First, we consider nonrandom x and let x=x_n so that as n→∞, x_n tends to the endpoint of F_X(x), or so that x_n tends to x₀, a point in the support of F_X(x). The second important situation appears when x=X_k∶n, i.e., we select Y-values on the basis of the random variable X_k∶n, the k-th order-statistic of the X-sample. Here we also consider two cases: (i) k=n−j with fixed j, and (ii) k=[np], where 0<p<1. The paper generalizes the earlier results of David, Joshi, and Nagaraja, where it is assumed that (X, Y) is in the bivariate (max-) domain of attraction of a bivariate stable law with independent marginals. Proceedings of the XVI Seminar on Stability Problems for Stochastic Models, Part I, Eger, Hungary, 1994.     

On the sequence of partial maxima of some random sequences

Let {X_n, n ? 1} be a sequence of identically distributed random variables, Z_n = max {X₁,…, X_n} and {u_n, n ? 1 } an increasing sequence of real numbers. Under certain additional requirements, necessary and sufficient conditions are given to have, with probability one, an infinite number of crossings of {Z_n} with respect to {u_n}, in two cases: (1) The X_n's are independent, (2) {X_n} is stationary Gaussian and satisfies a mixing condition.     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

Large deviations of the extreme eigenvalues of random deformations of matrices

Consider a real diagonal deterministic matrix X _n of size n with spectral measure converging to a compactly supported probability measure. We perturb this matrix by adding a random finite rank matrix, with delocalized eigenvectors. We show that the joint law of the extreme eigenvalues of the perturbed model satisfies a large deviation principle in the scale n, with a good rate function given by a variational formula. We tackle both cases when the extreme eigenvalues of X _n converge to the edges of the support of the limiting measure and when we allow some eigenvalues of X _n , that we call outliers, to converge out of the bulk. We can also generalise our results to the case when X _n is random, with law proportional to e ^{?n Tr V(X)} dX, for V growing fast enough at infinity and any perturbation of finite rank.     

Zero Divisor Graph for the Ring of Gaussian Integers Modulo n

This article studies the zero divisor graph for the ring of Gaussian integers modulo n, Γ (? _n [i]). For each positive integer n, the number of vertices, the diameter, the girth and the case when the dominating number is 1 or 2 is found.

Complete characterizations, in terms of n, are given of the cases in which Γ (? _n [i]) is complete, complete bipartite, planar, regular or Eulerian.     

Cross-intersecting families of permutations

For positive integers r and n with r?n, let Pr,n be the family of all sets {(1,y₁),(2,y₂),…,(r,yr)} such that y₁,y₂,…,yr are distinct elements of [n]={1,2,…,n}. Pn,n describes permutations of [n]. For r<n, Pr,n describes permutations of r-element subsets of [n]. Families A₁,A₂,…,Ak of sets are said to be cross-intersecting if, for any distinct i and j in [k], any set in Ai intersects any set in Aj. For any r, n and k?2, we determine the cases in which the sum of sizes of cross-intersecting sub-families A₁,A₂,…,Ak of Pr,n is a maximum, hence solving a recent conjecture (suggested by the author).     

On ordinary planes

Given a set of n points which span an ordered projective space P₃, W. Bonnice and L.M. Kelly have shown that the number of ordinary planes determined by this set is at least 3n/11. In this paper, it is shown that this lower bound can be improved to n/3 in general and in some cases to 4n/9 or even to n/2.     

Upsets in round robin tournaments

LetT(R) be the class of tournaments having monotone score vectorR = (r₁,…, r_n). For a givenn, upper and lower bounds are given for the minimum number and maximum number of upsets for tournaments inT(R) withR strong. The cases of equality are characterized.     

On weak asymptotic isomorphy of memoryless correlated sources

Let {(X _i,Z _i)} be an i.i.d. sequence of random pairs in a finite set × x ℒ; we will call it a discrete memoryless stationary correlated (DMSC) source with generic distribution dist(X ₁,Z ₁). Two DMSC sources {(X _i,Z _i)} and {(X _i′,Z _i′)} are called asymptotically isomorphic in the weak sense if for every ε>0 and sufficiently largen, there exists a joint distribution dist(X ⁿ,Z ⁿ,X′ ⁿ,Z′ ⁿ) ofn-length blocks of the two sources such that . For single sources of equal entropy, McMillan’s theorem implies asymptotic isomorphy in the sense suggested by this definition. For correlated sources, however, no nontrivial cases of weak asymptotic isomorphy are known. We show that some spectral properties of the generic distributions are invariant for weak asymptotic isomorphy, and these properties wholly determine the generic distribution in many cases.     

Multicolor Ramsey numbers involving graphs with long suspended paths

Let G₁,…,G_c be graphs and let H be a connected graph. Let H_n be a graph on n points which is homeomorphic to H. It is proved that if n is large enough, the Ramsey number r(G₁,…,G_c,H_n) has the form (X?1)(n?1)+T. Here X and T are two Ramsey-type functons involving G₁,…,G_c only. The properties of these functions are studied, leading to explicit evaluations in a number of cases.     

Pattern avoiding partitions and Motzkin left factors

Let L _n , n ≥ 1, denote the sequence which counts the number of paths from the origin to the line x = n ? 1 using (1, 1), (1, ?1), and (1, 0) steps that never dip below the x-axis (called Motzkin left factors). The numbers L _n count, among other things, certain restricted subsets of permutations and Catalan paths. In this paper, we provide new combinatorial interpretations for these numbers in terms of finite set partitions. In particular, we identify four classes of the partitions of size n, all of which have cardinality L _n and each avoiding a set of two classical patterns of length four. We obtain a further generalization in one of the cases by considering a pair of statistics on the partition class. In a couple of cases, to show the result, we make use of the kernel method to solve a functional equation arising after a certain parameter has been introduced.     

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.     

A certain family of summation-integral type operators

In the present paper, the authors introduce and investigate a new sequence of linear positive operators G_n,c, which includes some well-known operators as its special cases. The results obtained here include an estimate on the rate of convergence of G_n,c (f, x) by means of the decomposition technique for functions of bounded variation.