Families of intersecting finite vector spaces

The following theorem is proved. It is a generalization of the problem for finite vector spaces analogous to a theorem of Kleitman for finite sets.Let V be an n-dimensional vector space over a finite field F of q elements. Suppose we have two collections, one consisting of k- and the other of m-dimensional subspaces of V with the property that the intersection of each member of one with each member of the other has dimension no less than r.Then if n ? k + m + 2 or n ? k + m + 1 and q ? 3, there are either no more than $\text{[}\text{n?r}\text{k?r}\text{]}{}_{\mathrm{q}}$ members in the first family or fewer than $\text{[}\text{n?r}\text{m?r}\text{]}{}_{\mathrm{q}}$ members in the second.The method used leads to a similar result for sets, provided that n ? r + (r + 1)(k ? r)(m ? r + 1) with k ? m.     

On approximation by polynomials increasing to the right of the interval

We obtain sufficient conditions on a real valued function ?, continuous on [0, + ∞), to insure that, for some nonnegative integer n, there is a nonnegative number r(n) so that for any r ? r(n), the polynomial of best approximation to ? on [0, r] from π_n is increasing and nonnegative on [r, + ∞). Here, π_n denotes the set of all real polynomials of degree n or less. The proofs of Theorems 1 and 2 use only properties of Lagrange interpolation while that of Theorem 3 employs results on the location of interpolation points in Chebyshev approximation.     

Hamiltonian decompositions of complete graphs

It is well known that K_{2n + 1} can be decomposed into n edge-disjoint Hamilton cycles. A novel method for constructing Hamiltonian decompositions of K_{2n + 1} is given and a procedure for obtaining all Hamiltonian decompositions of of K_{2n + 1} is outlined. This method is applied to find a necessary and sufficient condition for a decomposition of the edge set of K_r (r ≤ 2n) into n classes, each class consisting of disjoint paths to be extendible to a Hamiltonian decomposition of K_{2n + 1} so that each of the classes forms part of a Hamilton cycle.     

Multidimensional Farey partitions

The linear action of SL(n, ?₊) induces lattice partitions on the (n − 1)-dimensional simplex †n−1. The notion of Farey partition raises naturally from a matricial interpretation of the arithmetical Farey sequence of order r. Such sequence is unique and, consequently, the Farey partition of order r on A 1 is unique. In higher dimension no generalized Farey partition is unique. Nevertheless in dimension 3 the number of triangles in the various generalized Farey partitions is always the same which fails to be true in dimension n > 3. Concerning Diophantine approximations, it turns out that the vertices of an n-dimensional Farey partition of order r are the radial projections of the lattice points in ?₊ⁿ ∩ [0, r]ⁿ whose coordinates are relatively prime. Moreover, we obtain sequences of multidimensional Farey partitions which converge pointwisely.     

Extremal Problems in Some Classes of Holomorphic Functions

Let PRΛ_n be the class of holomorphic functions with positive real part and real Taylor coefficients the first m + 1 of which are common for all these functions. We find: a) The extreme points of the class PRΛ_n. b) The extrema of {f(r): f ∈ PRΛ_n}, {f′(r): f ∈ PRΛ_n} and {f′(r): f ∈ PRΛ_n}. We also solve respective problems for typical real functions.     

The number of Hamiltonian decompositions of regular graphs

A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph K _n on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r = cn for some fixed c > 1/2 has a Hamiltonian decomposition, provided n = n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ) = r ^(1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of K _n is \({n^{\left( {1 + o\left( 1 \right)} \right){n^2}/2}}\).     

On the number of cycles possible in digraphs with large girth

We consider directed graphs which have no short cycles. In particular, if n is the number of vertices in a graph which has no cycles of length less than n ? k, for some constant k < ?n, then we show that the graph has no more than 3^k cycles. In addition, we show that for k ≤ ½n, there are graphs with exactly 3^k cycles. We thus are able to show that it is possible to bound the number of cycles possible in a graph which has no cycles of length less than f(n) by a polynomial in n if and only if f(n) ≥ n ? rlog(n) for some r.     

On Tverberg partitions

A theorem of Tverberg from 1966 asserts that every set X ? ? ^d of n = T(d, r) = (d + 1)(r ? 1) + 1 points can be partitioned into r pairwise disjoint subsets, whose convex hulls have a point in common. Thus every such partition induces an integer partition of n into r parts (that is, r integers a ₁,..., a _r satisfying n = a ₁ + ··· + a _r ), in which the parts a _i correspond to the number of points in every subset. In this paper, we prove that for any partition of n where the parts satisfy a _i ≤ d + 1 for all i = 1,..., r, there exists a set X ? ? of n points, such that every Tverberg partition of X induces the same partition on n, given by the parts a ₁,..., a _r .     

Construction of lattice rules with a trigonometric <Emphasis Type="Italic">d</Emphasis>-property on the basis of extreme lattices

Lattice rules with the trigonometric d-property that are optimal with respect to the number of points are constructed for the approximation of integrals over an n-dimensional unit cube. An extreme lattice for a hyperoctahedron at n = 4 is used to construct lattice rules with the trigonometric d-property and the number of points

$0.80822 \ldots \cdot \Delta ^4 (1 + o(1)), \Delta \to \infty $

(d = 2Δ ? 1 ≥ 3 is an arbitrary odd number). With few exceptions, the resulting lattice rules have the highest previously known effectiveness factor.

     

A simple heuristic approach to simplex efficiency

Consider the standard linear program:

$\text{Minimize}\text{cx}\text{subject to}\text{Ax=b, x?0}$

where A is an m × n matrix. The simplex algorithm solves this linear program by moving from an extreme point of the feasibility region to a better (in terms of the objective function cx) extreme point (via the pivot operation) until the optimal is reached. In order to obtain a feel for the number of necessary iterations, we consider a simple probabilistic (Markov chain) model as to how the algorithm moves along the extreme points. At first we suppose that if at any time the algorithm is at the jth best extreme point then after the next pivot the resulting extreme point is equally likely to be any of the j?1 best. Under this assumption, we show that the time to get from the Nth best to the best extreme point has approximately, for large N, a Poisson distribution with mean equal to the algorithm (base e) of N. We also consider a more general probabilistic model in which we drop the uniformity assumption and suppose that when at the jth best the next one is chosen probabilistically according to weights w_i, i = 1, …, j?1.     

Strongly regular graphs and finite Ramsey theory

Some connections between strongly regular graphs and finite Ramsey theory are drawn. Let B_n denote the graph K₂+K?_n. If there exists a strongly regular graph with parameters (υ, k, λ, μ), then the Ramsey number r(B_λ+1, B_{υ?2k+μ ?1})?υ+1. We consider the implications of this inequality for both Ramsey theory and the theory of strongly regular graphs.     

Higher order alternating sequences

Sequences which are alternating of a (finite) higher order n, appropriately normalized, are shown to form a Bauer simplex, and its countably many extreme points are identified. For \(\, n = 2 \,\) we are dealing with increasing concave sequences. The proof makes use of multivariate co-survival functions of (not necessarily finite) Radon measures.     

On a geometrical method of construction of maximal t-linearly independent sets

The problem of constructing a maximal t-linearly independent set in V(r; s) (called a maximal L_t(r, s)-set in this paper) is a very important one (called a packing problem) concerning a fractional factorial design and an error correcting code where V(r; s) is an r-dimensional vector space over a Galois field GF(s) and s is a prime or a prime power. But it is very difficult to solve it and attempts made by several research workers have been successful only in special cases.In this paper, we introduce the concept of a {Σ_α=1^kw_α, m; t, s}-min · hyper with weight (w₁, w₂,…, w_k) and using this concept and the structure of a finite projective geometry PG(n ? 1, s), we shall give a geometrical method of constructing a maximal L_t(t + r, s)-set with length t + r + n for any integers r, n, and s such that n ? 3, n ? 1 ? r₀ ? n + s ? 2 and r₁ ? 1, where r = (r₁ + 1)v_n?1 ? r₀ and $\text{v}{}_{\mathrm{n}}\text{=}\text{(s}{}^{\mathrm{n}}\text{? 1)}\text{(s ? 1)}$.     

An inequality for pseudo-subplanes of sets of orthogonal latin squares

Let L₁, L₂,…, L_t be a given set of t mutually orthogonal order-n latin squares defined on a symbol set S, |S| = n. The squares are equivalent to a (t + 2)-netN of order n which has n² points corresponding to the n² cells of the squares. A line of the net N defined by the latin square L_i comprises the n points of the net which are specified by a set of n cells of L_i all of which contain the same symbol x of S. If we pick out a particular r × r block B of cells, a line which contains points corresponding to r of the cells of B will be called an r-cell line. If there exist r(r ? 1) such lines among the tn lines of N, we shall say that they form a pseudo-subplane of order r-the “pseudo” means that these lines need not belong to only r ? 1 of the latin squares. The purpose of the present note is to prove that the hypothesis that such a pseudo-plane exists in N implies that $\text{r}{}^3\text{? (t + 2)r}{}^2\text{+ r + nt ?}{}^1\text{0}$.     

Automorphism groups of finite posets

For any finite group G, we construct a finite poset (or equivalently, a finite T₀-space) X, whose group of automorphisms is isomorphic to G. If the order of the group is n and it has r generators, X has n(r+2) points. This construction improves previous results by G. Birkhoff and M.C. Thornton. The relationship between automorphisms and homotopy types is also analyzed.     

On the degree of points and lines in a restricted linear space

In this paper we show that, with the exception of a few easily characterized linear spaces, all restricted linear spaces of square order n have the maximal degree of the lines equal to n + 1, the degree of every point at least n + 1, and further we show that p ? n² + n + 1 ? q, where p is the number of points and q the number of lines.     

ɛ-nets and simplex range queries

We demonstrate the existence of data structures for half-space and simplex range queries on finite point sets ind-dimensional space,d≥2, with linear storage andO(n ^α ) query time, $$\alpha = \frac{{d(d - 1)}}{{d(d - 1) + 1}} + \gamma for all \gamma > 0$$ . These bounds are better than those previously published for alld≥2. Based on ideas due to Vapnik and Chervonenkis, we introduce the concept of an ?-net of a set of points for an abstract set of ranges and give sufficient conditions that a random sample is an ?-net with any desired probability. Using these results, we demonstrate how random samples can be used to build a partition-tree structure that achieves the above query time.     

Extremal non-bipartite regular graphs of girth 4

Let f(r) denote the smallest number of points in a non-bipartite r-regular graph of girth 4. It is known that $\text{f(r) ≥}\text{5r}\text{2}$ and that $\text{f(r) =}\text{5r}\text{2}$ if r is even. It is proved that $\text{f(r) ～}\text{5r}\text{2}$ and exact values for f(r) are provided for odd integers of the form r = 4n ? 1. Tight bounds for f(r) for odd integers of the form r= 4n + 1 are given.     

A Solution to the Generalized Cevian Problem Using Forest Polynomials

In this paper, we examine the effect of dissecting an n-dimensional simplex using cevians (cross-sections passing through n−1 of the vertices of the simplex). We describe a formula for the number of pieces the simplex is dissected into using a polynomial involving only the number of each type of cevian. The polynomial in question involves terms involving the edges of the simplex, but discarding those terms involving cycles of the underlying graph. Thus, we call such a polynomial a “forest polynomial.”