A construction method for generalized Room squares

A Generalized Room Square (GRS) of ordern and degreek is an \(\left( {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right) \times \left( {\begin{array}{*{20}c} {n - 1} \\ {k - 1} \\ \end{array} } \right)\) array of which each cell is either empty or contains an unorderedk-tuple of a setS, |S|=n, such that each row and each column of the array contains each element ofS exactly once and the array contains each unorderedk-tuple exactly once. A method of generating the unordered triples on the setS=GF(q) ? {∞} is given, 3 ∣ (q ∣ 1). This method is used to construct GRS's of appropriate ordern and degree 3, for alln<50.     

Unavoidable stars in 3-graphs

Suppose $\text{F}$ is a collection of 3-subsets of {1,2,…,n}. The problem of determining the least integer $\text{?(n, k)}$ with the property that if $\text{|F| > ?(n, k)}$ then $\text{F}$ contains a k-star (i.e., k 3-sets such that the intersection of any pair of them consists of exactly the same element) is studied. It is proved that, for k odd, $\text{?(n, k) = k(k ? 1)n + O(k}{}^3\text{)}$ and, for k even, $\text{?(n, k) = k(k ?}\text{3}\text{2}\text{)n + O(n + k}{}^3\text{)}$.     

Extremal uncrowded hypergraphs

Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ? t ? n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size $\text{c}{}_{\mathrm{k}}\text{(}\text{n}\text{t}\text{)(}\text{ln}\text{t)}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}$.     

A note on character sums

Let $\text{S(k) = Σ}{}_{\mathrm{n=1}}{}^{\mathrm{p?1}}\text{(}\text{n}\text{p}\text{)n}{}^{\mathrm{k}}$ where p is a prime ≡ 3 mod 4 and k is an integer ≥ 3. Then S(k) frequently takes large values of each sign.     

On the probability that k positive integers are relatively prime II

Given a set S of positive integers let $\text{Z}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(t)}$ denote the number of k-tuples 〈m₁, …, m_k〉 for which $\text{m}{}_{\mathrm{i}}\text{∈ S ? [1, t]}$ and (m₁, …, m_k) = 1. Also let $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n)}$ denote the probability that k integers, chosen at random from $\text{S ? [1, n]}$, are relatively prime. It is shown that if P = {p₁, …, p_r} is a finite set of primes and S = {m : (m, p₁ … p_r) = 1}, then $\text{Z}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(t) = (td(S))}{}^{\mathrm{k}}\text{Π}{}_{\mathrm{\nu ?P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{) + O(t}{}^{\mathrm{k?1}}\text{)}$ if k ≥ 3 and $\text{Z}{}_2{}^{\mathrm{S}}\text{(t) = (td(S))}{}^2\text{Π}{}_{\mathrm{p?P}}\text{(1 ?}\text{1}\text{p}{}^2\text{) + O(t}\text{log}\text{t)}$ where d(S) denotes the natural density of S. From this result it follows immediately that $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n) → Π}{}_{\mathrm{p?P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{) = (ζ(k))}{}^{\mathrm{?1}}\text{Π}{}_{\mathrm{p\in P}}\text{(1 ?}\text{1}\text{p}{}^{\mathrm{k}}\text{)}{}^{\mathrm{?1}}$ as n → ∞. This result generalizes an earlier result of the author's where $\text{P = ?}$ and S is then the whole set of positive integers. It is also shown that if S = {p₁^x₁ … p_r^x_r : x_i = 0, 1, 2,…}, then $\text{P}{}_{\mathrm{k}}{}^{\mathrm{S}}\text{(n) → 0}$ as n → ∞.     

Cup products in Grassmannians

This note calculates the height of the first Stiefel-Whitney class in the cohomology of the real Grassmannians and determines the length of the longest nontrivial cup-product in $\text{H}{}^1\text{(G}{}_{\mathrm{k}}\text{(R}{}^{\mathrm{n+k}}\text{);Z}{}_2\text{) (k?n)}$ with k?4.     

All directed BIBDs with k = 3 exist

A directed BIBD with parameters ($\text{υ, b, r, k, λ}{}^1$) is a BIBD with parameters ($\text{υ, b, r, k, 2λ}{}^1$) in which each ordered pair of varieties occurs together in exactly $\text{λ}{}^1$ blocks. It is shown that $\text{λ}{}^1\text{υ(υ ? 1) ≡ 0}$ (mod 3) is a necessary and sufficient condition for the existence of a directed ($\text{υ, b, r, k, λ}{}^1$) BIBD with k = 3.     

A note on Ramsey numbers

Upper bounds are found for the Ramsey function. We prove $\text{R(3, x) <}\text{cx}{}^2\text{ln}\text{x}$ and, for each k ? 3, $\text{R(k, x) <}\text{c}{}_{\mathrm{k}}\text{x}{}^{\mathrm{k\; ?\; 1}}\text{(}\text{ln}\text{x)}{}^{\mathrm{k\; ?\; 2}}$ asymptotically in x.     

Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.     

Equivalence of Room designs. II

The relation of equivalence of Room designs is investigated with respect to the class of Room designs formed from starters with adders in the conventional way. It is shown that, if p^k = 3 + 4t, $\text{s = t ? 2[}\text{t}\text{2}\text{]}$, and $\text{I = (}\text{1}\text{k}\text{) ∑}{}_{\mathrm{<mtext>d</mtext><mtext>k</mtext>}}\text{P}{}^{\mathrm{d}}\text{φ}$ ($\text{k}\text{d}$), then it is possible to construct, without duplication, at least $\text{(I + (?3)}{}^{\mathrm{1–8}}\text{)}\text{8}$ inequivalent patterned Room designs of side p^k. This result implies, for instance, the existence of at least 11 equivalence classes of Room designs of side 87 which contain a patterned Room design; it also implies the existence of at least 5 · 10⁵ equivalence classes of Room designs of side 7⁹ which contain a patterned Room design. Some additional results are obtained.     

2-Colored triangles in edge-colored complete graphs

If each edge of complete graph K_n is colored with one of k colors then it contains a triangle having two colors if $\text{k < 1 + n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$. The result is best possible when n is the square of a prime.     

On the number of line separations of a finite set in the plane

Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S?S′. We let f_k(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of f_k(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on f_k(n) is established. Both are nontrivial and improve bounds known before. In particular, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = Ω(n}\text{log}\text{k)}$ is shown by exhibiting special point-sets which realize that many k-sets. In addition, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = O(nk}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ is proved by the study of a combinatorial problem which is of interest in its own right.     

Infinite Eulerian tessellations

An Eulerian path in a graph G is a path π such that (1) π traverses each edge of G exactly once in each direction, and (2) π does not traverse any edge once in one direction and then immediately after in the other direction. A tessellation T of the plane is Eulerian if its l-skeleton G admits an Eulerian path. It is shown that the three regular tessellations of the Euclidean plane are Eulerian. More generally, if T is a tessellation of the plane such that each face has 2t least p sides and each vertex has degree (number of incident edges) at least q, where $\text{1/p+1/q≤}\text{1}\text{2}$, then, except possibly for the case p = 3 and q = 6, T is Eulerian. Let $\text{T}{}^1$ be the truncation of T. If every vertex of T has degree 3, then $\text{T}{}^1$ is not Eulerian. If every vertex has degree 4, or degree at least 6, then T is Eulerian.     

On the closability of some positive definite symmetric differential forms on c0∞(ω)

Let $\text{S}$ be a Dirichlet form in $\text{L}{}^2\text{(Ω; m)}$, where Ω is an open subset of $\text{R}$ⁿ, n ? 2, and m a Radon measure on Ω; for each integer k with 1 ? k < n, let $\text{S}$_k be a Dirichlet form on some k-dimensional submanifold $\text{Ω}{}_{\mathrm{k}}$ of Ω. The paper is devoted to the study of the closability of the forms E with domain $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$ and defined by: $\text{(?,g)=}$$\text{E}$$\text{(?, g)+}\text{∑}\text{i}\text{p}\text{=1}$$\text{E}$k_i where 1 ? k_p < ? < n, and where , g^k_i denote restrictions of ?, g in $\text{C}{}_0{}^{\mathrm{\infty }}\text{(Ω)}$ to . Conditions are given for E to be closable if, for each i = 1,…, p, one has k_i = n ? i. Other conditions are given for E to be nonclosable if, for some i, k_i < n ? i.     

Starting in maximum-polynomial-degree Nordsieck-Gear methods

The intent of this paper is to show that the Nordsieck-Gear methods with maximum polynomial degree k+1, first described in [1], admit of matched starting methods which are exact for all polynomials of degree ?k+1. In general, it is shown that these starting methods yield starting errors of the required order, O(h^k+2), for all initial-value problems

$\text{y}{}^{\mathrm{(P)}}\text{(x)=f(x,y,y}{}^{\mathrm{(1)}}\text{,y}{}^{\mathrm{(2)}}\text{,…,y}{}^{\mathrm{(p?1)}}\text{),}$

$\text{y(0)=y}{}_0\text{, y}{}^{\mathrm{i}}\text{(0)=y}{}_0{}^{\mathrm{(i)}}\text{, i=1,2,…,p?1,}$

where f is k+1 times continuously differentiable in a neighborhood of the graph of the exact solution (x,?(x)), x?[0,X]. Two theorems are proved. The first is the constructive existence of an algorithm which requires (k-p+1)(k-p+2)/2 evaluations of the function f to obtain approximations of the method's required higher-order scaled derivatives at the origin:

$\text{h}{}^{\mathrm{p+1}}\text{y}\text{?}{}^{\mathrm{(p+1)}}\text{(0)}\text{(p+1)!}\text{,…,}\text{h}{}^{\mathrm{k}}\text{y}\text{?}{}^{\mathrm{(k)}}\text{(0)}\text{k!}\text{,}$

each of which is accurate to O(h^k+2). The second, less general theorem, shows that when f is a polynomial in x, y, and its higher order derivatives y⁽¹⁾,y⁽²⁾,…,y(^p?1), an algorithm can be constructed for obtaining the higher-order scaled derivatives exactly. These results lay to rest once and for all any heuristic arguments against varying corrector minus predictor coefficients for preserving maximal order (polynomial degree) because starting values are inexact. Furthermore, and perhaps most importantly, the maximum-polynomial-degree Nordsieck-Gear methods are shown to have a unique property of zero starting error for an important class of ordinary differential equations.     

On the series Σk = 1∞(k2k)−1k−n and related sums

Series of the form $\text{Σ}{}_{\mathrm{k\; =\; 1}}{}^{\mathrm{\infty }}\text{(}\text{2k}\text{2k}\text{)}{}^{\mathrm{?1}}\text{k}{}^{\mathrm{?n}}$ may be expressed as log sin integrals and are shown to be summable exactly in terms of Dirichlets L-series for values of n up to and including 5. Other related series are also discussed and several exact results are given.     

Votes and a half-binomial

In two party elections with popular vote ratio $\text{p}\text{q}\text{,}\text{1}\text{2}\text{≤p=1 ?q}$, a theoretical model suggests replacing the so-called MacMahon cube law approximation $\text{(}\text{p}\text{q}\text{)}{}^3$, for the ratio $\text{P}\text{Q}$ of candidates elected, by the ratio $\text{?}{}_{\mathrm{k}}\text{(p)}\text{?}{}_{\mathrm{k}}\text{(q)}$ of the two half sums in the binomial expansion of (p+q)^2k+1 for some k. This ratio is nearly $\text{(}\text{p}\text{q}\text{)}{}^3$ when k = 6. The success probability $\text{g}{}_{\mathrm{k}}\text{(p)=(}\text{p}{}^{\mathrm{a}}\text{(p}{}^{\mathrm{a}}\text{+q}{}^{\mathrm{a}}\text{)}$ for the power law $\text{(}\text{p}\text{q}\text{)}{}^{\mathrm{a}}\text{?}\text{P}\text{Q}$ is shown to so closely approximate $\text{?}{}_{\mathrm{k}}\text{(p)=Σ}{}_0{}^{\mathrm{k}}\text{(}{}_{\mathrm{r}}{}^{\mathrm{2k+1}}\text{)p}{}^{\mathrm{2k+1?r}}\text{q}{}^{\mathrm{r}}$, if we choose $\text{a = a}{}_{\mathrm{k}}\text{=}\text{(2k+1)!}\text{4}{}^{\mathrm{k}}\text{k!k!}$, that $\text{1≤}\text{?}{}_{\mathrm{k}}\text{(p)}\text{g}{}_{\mathrm{k}}\text{(p)}\text{≤1.01884086}$ for $\text{k≥1}\text{if}\text{1}\text{2}\text{≤p≤1}$. Computationally, we avoid large binomial coefficients in computing $\text{?}{}_{\mathrm{k}}\text{(p)}$ for k>22 by expressing $\text{2?}{}_{\mathrm{k}}\text{(p)?1}$ as the sum $\text{(p?q) Σ}{}_0{}^{\mathrm{k}}\text{(4pq)}{}^{\mathrm{s}}\text{a}{}_{\mathrm{s}}\text{(2s+1)}$, whose terms decrease by the factors $\text{(4pq)(1?}\text{1}\text{2s}\text{)}$. Setting K = 4k+3, we compute a_k for the large k using a continued fraction $\text{πa}{}_{\mathrm{k}}{}^2\text{=}\text{K+1}{}^2\text{(}\text{2K+3}{}^2\text{(}\text{2K+5}{}^2\text{(2K+…)}\text{)}\text{)}$ derived from the ratio of π to the finite Wallis product approximation.     

Factorizing the complete graph into factors with large star number

The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that $\text{c}{}_1{}^{\mathrm{n}}\text{k ≤ f(n, k) < c}{}_2{}^{\mathrm{n}}\text{k}$.