Partitions of finite vector spaces into subspaces

Let V_n(q) denote a vector space of dimension n over the field with q elements. A set of subspaces of V_n(q) is a partition of V_n(q) if every nonzero element of V_n(q) is contained in exactly one element of . Suppose there exists a partition of V_n(q) into x_i subspaces of dimension n_i, 1 ≤ i ≤ k. Then x₁, …, x_k satisfy the Diophantine equation . However, not every solution of the Diophantine equation corresponds to a partition of V_n(q). In this article, we show that there exists a partition of V_n(2) into x subspaces of dimension 3 and y subspaces of dimension 2 if and only if 7x + 3y = 2ⁿ ? 1 and y ≠ 1. In doing so, we introduce techniques useful in constructing further partitions. We also show that partitions of V_n(q) induce uniformly resolvable designs on qⁿ points. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 329–341, 2008     

On vector space partitions and uniformly resolvable designs

Let V _n (q) denote a vector space of dimension n over the field with q elements. A set of subspaces of V _n (q) is a partition of V _n (q) if every nonzero vector in V _n (q) is contained in exactly one subspace in . A uniformly resolvable design is a pairwise balanced design whose blocks can be resolved in such a way that all blocks in a given parallel class have the same size. A partition of V _n (q) containing a _i subspaces of dimension n _i for 1 ≤ i ≤ k induces a uniformly resolvable design on q ⁿ points with a _i parallel classes with block size , 1 ≤ i ≤ k, and also corresponds to a factorization of the complete graph into -factors, 1 ≤ i ≤ k. We present some sufficient and some necessary conditions for the existence of certain vector space partitions. For the partitions that are shown to exist, we give the corresponding uniformly resolvable designs. We also show that there exist uniformly resolvable designs on q ⁿ points where corresponding partitions of V _n (q) do not exist. A. D. Blinco—Part of this research was done while the author was visiting Illinois State University.     

Helly-type theorems for appropriate colorings of visibility sets

Summary. For positive integers q and n, think of P as the vertex set of a (qn + r)-gon, 0 ￡ r ￡ q - 1 0 \leq r \leq q - 1 . For 1 ￡ i ￡ qn + r 1 \leq i \leq qn + r , define V(i) to be a set of q consecutive points of P, starting at p(i), and let S be a subset of {V(i) : 1 ￡ i ￡ qn + r } \lbrace V(i) : 1 \leq i \leq qn + r \rbrace . A q-coloring of P = P(q) such that each member of S contains all q colors is called appropriate for S, and when 1 ￡ j ￡ q 1 \leq j \leq q , the definition may be extended to suitable subsets P(j) of P. If for every 1 ￡ j ￡ q 1 \leq j \leq q and every corresponding P(j), P(j) has a j-coloring appropriate for S, then we say P = P(q) has all colorings appropriate for S. With this terminology, the following Helly-type result is established: Set P = P(q) has all colorings appropriate for S if and only if for every (2n + 1)-member subset T of S, P has all colorings appropriate for T. The number 2n + 1 is best possible for every r 3 1 r \geq 1 . Intermediate results for q-colorings are obtained as well.     

Partitions of the 8‐dimensional vector space over GF(2)

Let V = V(n, q) denote the vector space of dimension n over GF(q). A set of subspaces of V is called a partition of V if every nonzero vector in V is contained in exactly one subspace of V. Given a partition 𝒫 of V with exactly a_i subspaces of dimension i for 1≤i≤n, we have , and we call the n‐tuple (a_n, a_{n − 1}, …, a₁) the type of 𝒫. In this article we identify all 8‐tuples (a₈, a₇, …, a₂, 0) that are the types of partitions of V(8, 2). © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 462–474, 2010     

Ovoids and spreads of finite classical polar spaces

LetP be a finite classical polar space of rankr, r2. An ovoidO ofP is a pointset ofP, which has exactly one point in common with every totally isotropic subspace of rankr. It is proved that the polar spaceW _n (q) arising from a symplectic polarity ofPG(n, q), n odd andn > 3, that the polar spaceQ(2n, q) arising from a non-singular quadric inPG(2n, q), n > 2 andq even, that the polar space Q^–(2n + 1,q) arising from a non-singular elliptic quadric inPG(2n + 1,q), n > 1, and that the polar spaceH(n,q ²) arising from a non-singular Hermitian variety inPG(n, q ²)n even andn > 2, have no ovoids.LetS be a generalized hexagon of ordern (1). IfV is a pointset of order n³ + 1 ofS, such that every two points are at distance 6, thenV is called an ovoid ofS. IfH(q) is the classical generalized hexagon arising fromG ₂ (q), then it is proved thatH(q) has an ovoid iffQ(6, q) has an ovoid. There follows thatQ(6, q), q=3^2h+1, has an ovoid, and thatH(q), q even, has no ovoid.A regular system of orderm onH(3,q ²) is a subsetK of the lineset ofH(3,q ²), such that through every point ofH(3,q ²) there arem (> 0) lines ofK. B. Segre shows that, ifK exists, thenm=q + 1 or (q + l)/2.If m=(q + l)/2,K is called a hemisystem. The last part of the paper gives a very short proof of Segre's result. Finally it is shown how to construct the 4-(11, 5, 1) design out of the hemisystem with 56 lines (q=3).     

Limit theorems for trimmed sums

This paper studies the heavily trimmed sums (*) _{[ns] + 1} ^[nt] X _j ⁽ⁿ⁾ , where {X _j ⁽ⁿ⁾ } _{j = 1} ⁿ are the order statistics from independent random variables {X ₁,...,X _n } having a common distributionF. The main theorem gives the limiting process of (*) as a process oft. More smoothly trimmed sums like _{j = 1} ^[nt] J(j/n)X _j ⁽ⁿ⁾ are also discussed.     

Optimal inverse Littlewood–Offord theorems

Let ηi, i=1,…,n, be iid Bernoulli random variables, taking values ±1 with probability . Given a multiset V of n integers v₁,…,vn, we define the concentration probability as A classical result of Littlewood–Offord and Erd?s from the 1940s asserts that, if the vi are non-zero, then ρ(V) is O(n−1/2). Since then, many researchers have obtained improved bounds by assuming various extra restrictions on V.About 5 years ago, motivated by problems concerning random matrices, Tao and Vu introduced the inverse Littlewood–Offord problem. In the inverse problem, one would like to characterize the set V, given that ρ(V) is relatively large.In this paper, we introduce a new method to attack the inverse problem. As an application, we strengthen the previous result of Tao and Vu, obtaining an optimal characterization for V. This immediately implies several classical theorems, such as those of Sárközy and Szemerédi and Halász.The method also applies to the continuous setting and leads to a simple proof for the β-net theorem of Tao and Vu, which plays a key role in their recent studies of random matrices.All results extend to the general case when V is a subset of an abelian torsion-free group, and ηi are independent variables satisfying some weak conditions.     

A remark on Nesterenko’s theorem for Ramanujan functions

We study the algebraic independence of values of the Ramanujan q-series $A_{2j+1}(q)=\sum_{n=1}^{\infty}n^{2j+1}q^{2n}/(1-q^{2n})$ or S _2j+1(q) (j≥0). It is proved that, for any distinct positive integers i, j satisfying $(i,j)\not=(1,3)$ and for any $q\in \overline{ \mathbb{Q}}$ with 0<|q|<1, the numbers A ₁(q), A _2i+1(q), A _2j+1(q) are algebraically independent over $\overline{ \mathbb{Q}}$ . Furthermore, the q-series A _2i+1(q) and A _2j+1(q) are algebraically dependent over $\overline{ \mathbb{Q}}(q)$ if and only if (i,j)=(1,3).     

Generalized steinhaus graphs

A generalized Steinhaus graph of order n and type s is a graph with n vertices whose adjacency matrix (a_i,j) satisfies the relation where 2 ≦i≦n?1, i + s(i ? 1 ≦ j ≦ n, c_r,i,j ? {0,1} for all 0 ≦ r ≦ s(i) ?1 and c_s(i)?1,i,j = 1. The values of s(i) and c_r,i,j are fixed but arbitrary. Generalized Steinhaus graphs in which each edge has probability ½ are considered. In an article by A. Blass and F. Harary [“Properties of Almost All Graphs and Complexes,” Journal of Graph Theory, Vol. 3 (1976), pp. 225–240], a collection of first-order axioms are given from which any first-order property in graph theory or its negation can be deduced. We show that almost all generalized Steinhaus graphs satisfy these axioms. Thus the first-order theory of random generalized Steinhaus graphs is identical with the theory of random graphs. Quasi-random properties of graphs are described by F. R. K. Chung, R. L. Graham, and R. M. Wilson, [“Quasi-Random Graphs,” Combinatorica, Vol. 9 (1989), pp. 345–362]. We conclude by demonstrating that almost all generalized Steinhaus graphs obey Property 2 and hence all equivalent quasi-random properties. © 1996 John Wiley & Sons, Inc.     

Independence of Likelihood Ratio Criteria for Homogeneity of Several Populations

Let _i be an i-tb population with a probability density function f(· | _i ) with one dimensional unknown parameter _i = 1, 2, ... , k. Let n _i sample be drawn from each _i . The likelihood ratio criteria _j|(j–1) for testing hypothesis that the first j parameters are equal against alternative hypothesis that the first (j – 1) parameters are equal and the j-th parameter is different with the previous ones are defined, j = 2, 3, ... , k. The paper shows the asymptotic independence of _j|(j–1)'s up to the order 1/n under a hypothesis of equality of k parameters, where n is a number of total samples.     

The phase transition in the cluster‐scaled model of a random graph

For 0 < p < 1 and q > 0 let G_q(n,p) denote the random graph with vertex set [n]={1,…,n} such that, for each graph G on [n] with e(G) edges and c(G) components, the probability that G_q(n,p)=G is proportional to . The first systematic study of G_q(n,p) was undertaken by 6 , who analyzed the phase transition phenomenon corresponding to the emergence of the giant component. In this paper we describe the structure of G_q(n,p) very close the critical threshold. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Non-local Dirichlet forms generated by pseudodifferential operators on compact abelian groups

Let G_i, 1 ≤ i ≤ n, be compact abelian groups and let Γ_i , 1 ≤ i ≤ n, be countable dual groups. We consider G = G₁ ⊕ G₂ ⊕ … ⊕ G_n and Γ = Γ₁ ⊕ Γ₂ ⊕ … ⊕ Γ_n . For 1 ≤ j ≤ n, let a_j be a negative definite function on Γ_j and a (γ) = . For φ ∈ S (G), the set of all generalized trigonometrical polynomials on G, we define , where (γ) = a_j (γ_j) (γ), 1 ≤ j ≤ n. Then is a Dirichlet form with the domain on L² (G). (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Limit Laws for Sums of Independent Random Products: the Lattice Case

Let {V _i,j ;(i,j)∈ℕ²} be a two-dimensional array of independent and identically distributed random variables. The limit laws of the sum of independent random products

Parametrization of Triangle Groups as Subgroups of PSL(2, q)

In this paper we are interested in triangle groups (j, k, l) where j = 2 and k = 3. The groups (j, k, l) can be considered as factor groups of the modular group PSL(2, Z) which has the presentation x, y : x² = y³ = 1. Since PSL(2,q) is a factor group of G^k,l,m if -1 is a quadratic residue in the finite field F_q, it is therefore worthwhile to look at (j, k, l) groups as subgroups of PSL(2, q) or PGL(2, q). Specifically, we shall find a condition in form of a polynomial for the existence of groups (2, 3, k) as subgroups of PSL(2, q) or PGL(2, q).Mathematics Subject Classification: Primary 20F05 Secondary 20G40.     

Interacting Brownian particles and the Wigner law

Summary In this paper, we study interacting diffusing particles governed by the stochastic differential equationsdX _j (t)= _n dB _j (t) –D _jØ_n(X ₁,...,X _n)dt,j=1, 2,...,n. Here theB _jare independent Brownian motions in ^d , and Ø _n (X ₁,...,X _n)= _{n ij} V(X _iX _j) + _ni U(X ₁). The potentialV has a singularity at 0 strong enough to keep the particles apart, and the potentialU serves to keep the particles from escaping to infinity. Our interest is in the behaviour as the number of particles increases without limit, which we study through the empirical measure process. We prove tightness of these processes in the case ofd=1,V(x)=–log|x|,U(x)=x ²/2 where it is possible to prove uniqueness of the limiting evolution and deduce that a limiting measure-valued process exists. This process is deterministic, and converges to the Wigner law ast. Some information on the rates of convergence is derived, and the case of a Cauchy initial distribution is analysed completely.Supported by SERC grant number GR/H 00444     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Root Configurations for Hyperbolic Polynomials of Degree 3, 4, and 5

A real polynomial of one real variable is (strictly) hyperbolic if it has only real (and distinct) roots. There are 10 (resp. 116) possible non-degenerate configurations between the roots of a strictly hyperbolic polynomial of degree 4 (resp. 5) and of its derivatives (i.e., configurations without equalities between roots). The standard Rolle theorem allows 12 (resp. 286) such configurations. The result is based on the study of the hyperbolicity domain of the family P(x,a)=x ⁿ+a ₁ x ^n-1+...+a _n for n=4,5 (i.e., of the set of values of aⁿ for which the polynomial is hyperbolic) and its stratification defined by the discriminant sets Res(P ⁽ⁱ⁾,P ^(j))=0, 0 i < jn-1.     

A power law for connectedness of some random graphs at the critical point

We consider P(G is connected) when G is a graph with vertex set Z⁺ = {1,2, …}, and the edge between i and j is present with probability p(i, j) = min(λ h(i, j), 1) for certain functions h(i, j) homogeneous of degree -1. It is known that there is a critical value λ_c of λ such that . We show that the probability, at the critical point λ_c, that n₁, and n₂ are connected satisfies a power law, in the sense that for n₂ ≧ n_t ≧ 1 for any δ > 0 and certain constants c₁ and c₂.     

On a characterization of the exponential distribution by spacings

Summary LetX be a non-negative random variable with probability distribution functionF. SupposeX _i,n (i=1,…,n) is theith smallest order statistics in a random sample of sizen fromF. A necessary and sufficient condition forF to be exponential is given which involves the identical distribution of the random variables (n−i)(X _i+1,n−X_i,n) and (n−j)(X _j+1,n−X_j,n) for somei, j andn, (1≦i<j<n). The work was partly completed when the author was at the Dept. of Statistics, University of Brasilia, Brazil.