Asymptotic Determination of the Last Packing Number of Quadruples

A 3-(n,4,1) packing design consists of an n-element set X and a collection of 4-element subsets of X, called blocks, such that every 3-element subset of X is contained in at most one block. The packing number of quadruples d(3,4,n) denotes the number of blocks in a maximum 3-(n,4,1) packing design, which is also the maximum number A(n,4,4) of codewords in a code of length n, constant weight 4, and minimum Hamming distance 4. In this paper the last packing number A(n,4,4) for n≡ 5(mod 6) is shown to be equal to Johnson bound with 21 undecided values n=6k+5, k∈{m: m is odd , 3≤ m≤ 35, m≠ 17,21}∪ {45,47,75,77,79,159}. AMS Classification:05B40, 94B25     

On homogeneous extensions of finite predicate systems

It is shown that any finite n-element predicate system for which any two one-element subsystems are isomorphic is embeddable in a finite (2 ⁿ − 1)-element system having a transitive automorphism group.     

The Dimension of Interior Levels of the Boolean Lattice,II

Extending an old lemma by Dushnik, we establish the dimension d(3, k; n) of the containment order generated by the 3-element and k-element subsets of an n-element set for most k between and n.     

Asymptotic bounds for irredundant and mixed Ramsey numbers

The irredundant Ramsey number s(m, n) is the smallest N such that in every red-blue coloring of the edges of K_N, either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. The definition of the mixed Ramsey number t(m, n) differs from s(m, n) in that the n-element irredundant set is replaced by an n-element independent set. We prove asymptotic lower bounds for s(n, n) and t(m, n) (with m fixed and n large) and a general upper bound for t(3, n). © 1993 John Wiley & Sons, Inc.     

On Series of Ordinals and Combinatorics

This paper deals mainly with generalizations of results in finitary combinatorics to infinite ordinals. It is well-known that for finite ordinals ∑_bT<αβ is the number of 2-element subsets of an α-element set. It is shown here that for any well-ordered set of arbitrary infinite order type α, ∑_bT<αβ is the ordinal of the set M of 2-element subsets, where M is ordered in some natural way. The result is then extended to evaluating the ordinal of the set of all n-element subsets for each natural number n ≥ 2. Moreover, series ∑_β<αf(β) are investigated and evaluated, where α is a limit ordinal and the function f belongs to a certain class of functions containing polynomials with natural number coefficients. The tools developed for this result can be extended to cover all infinite α, but the case of finite α appears to be quite problematic.     

ASYMPTOTIC BOUNDS FOR IRREDUNDANT RAMSEY NUMBERS

Abstract

The irredundant Ramsey number s(m,n) is the smallest N such that in every red-blue colouring of the edges of K_N , either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We prove an asymptotic lower bound for s(m, n).     

Bargraph statistics on words and set partitions

In this paper, we consider statistics on partitions of an n-element set represented as a subset of the bargraphs that have n horizontal steps. More precisely, we find the joint distribution of the area and up step statistics on the latter subset of bargraphs, thereby obtaining new refined counts on partitions having a fixed number of blocks. Furthermore, we give explicit formulas in terms of the Stirling numbers for the total area and number of up steps in bargraphs corresponding to partitions, providing both algebraic and combinatorial proofs. Finally, we find asymptotic estimates for the average and total values of these statistics and as a consequence obtain some new identities for the Stirling and Bell numbers.     

A new existence proof for large sets of disjoint Steiner triple systems

A Steiner triple system of order v (briefly STS(v)) consists of a v-element set X and a collection of 3-element subsets of X, called blocks, such that every pair of distinct points in X is contained in a unique block. A large set of disjoint STS(v) (briefly LSTS(v)) is a partition of all 3-subsets (triples) of X into v-2 STS(v). In 1983–1984, Lu Jiaxi first proved that there exists an LSTS(v) for any v≡1 or with six possible exceptions and a definite exception v=7. In 1989, Teirlinck solved the existence of LSTS(v) for the remaining six orders. Since their proof is very complicated, it is much desired to find a simple proof. For this purpose, we give a new proof which is mainly based on the 3-wise balanced designs and partitionable candelabra systems.     

A Note on Uniquely lntersectable Graphs

The following conjecture of Alter and Wang is proven. Consider the intersection graph G_n,m,n?2m, determined by the family of all m-element subsets of an n-element set. Then any realization of G_n,m as an intersection graph by a family of sets satisfies |∪_iA_i|?n; and if |∪_iA_i|=n, then F must be the family of all m-element subsets of ∪_iA_i.     

n-median semilattices

An n-median semilattice (n3) is a meet-semilattice such that (i) every principal ideal is a distributive lattice and (ii) any n-element set of elements is bounded above whenever each of its (n-1)-element subsets has an upper bound. A 3-median semilattice is thus a median semilattice in the classical sense. In this note we demonstrate how the characteristic features of median semilattices carry over to the more general case of n-median semilattices.Research supported in part by ONR Grant N00014-90-1008.     

COLORING SUBGRAPHS OF THE RADO GRAPH

Given a universal binary countable homogeneous structure U and n∈ω, there is a partition of the induced n-element substructures of U into finitely many classes so that for any partition C₀,C₁, . . .,C_m−1 of such a class Q into finitely many parts there is a number k∈m and a copy U* of U in U so that all of the induced n-element substructures of U* which are in Q are also in C_k. The partition of the induced n-element substructures of U is explicitly given and a somewhat sharper result as the one stated above is proven. * Supported by NSERC of Canada Grant # 691325.     

The irredundant ramsey number s(3, 7)

The irredundant Ramsey number s(m, n) is the smallest p such that for every graph G with p vertices, either G contains an n-element irredundant set or its complement G contains an m-element irredundant set. Cockayne, Hattingh, and Mynhardt have given a computer-assisted proof that s(3, 7) = 18. The purpose of this paper is to give a self-contained proof of this result. © 1995 John Wiley & Sons, Inc.     

Enumeration of order preserving maps

Three results are obtained concerning the number of order preserving maps of an n-element partially ordered set to itself. We show that any such ordered set has at least 2 ^2n/3 order preserving maps (and 2 ² in the case of length one). Precise asymptotic estimates for the numbers of self-maps of crowns and fences are also obtained. In addition, lower bounds for many other infinite families are found and several precise problems are formulated.Supported by ONR Contract N00014-85-K-0769.Supported by NSF Grant DMS-9011850.Supported by NSERC Grants 69-3378 and 69-0259.     

On irredundant Ramsey numbers for graphs

The irredundant Ramsey number s(m, n) is the smallest p such that in every two-coloring of the edges of K_p using colors red (R) and blue (B), either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We develop techniques to obtain upper bounds for irredundant Ramsey numbers of the form s(3, n) and prove that 18 ≤ s(3,7) ≤ 19.     

The maximum number of second smallest distances in finite planar sets

It is proved that the maximum numbers ₂ of second smallest distances in anyn-element point set of the plane is less than 24/7n, where the constant 24/7 is best possible.     

Proof of a conjecture on partitions of a Boolean lattice

Let n and c be positive integers. We show that if n is sufficiently large given c then the Boolean lattice consisting of all subsets of an n-element set can be partitioned into chains of size c except for at most c — 1 elements which also form a chain. This settles a conjecture of Griggs.     

Cutting a graph into two dissimilar halves

Given a graph G and a subset S of the vertex set of G, the discrepancy of S is defined as the difference between the actual and expected numbers of the edges in the subgraph induced on S. We show that for every graph with n vertices and e edges, n < e < n(n ? 1)/4, there is an n/2-element subset with the discrepancy of the order of magnitude of \documentclass{article}\pagestyle{empty}\begin{document}$\sqrt {ne}$\end{document} For graphs with fewer than n edges, we calculate the asymptotics for the maximum guaranteed discrepancy of an n/2-element subset. We also introduce a new notion called “bipartite discrepancy” and discuss related results and open problems.     

Classification of 8-Dimensional Trilinear Alternating Forms over GF(2)

Let V be an n-dimensional vector space over a finite field and let f be a trilinear alternating form over V. For such forms we introduce a new invariant called radical polynomial and investigate its behaviour, in particular in the case of the 2-element field. We show that it is compatible with direct products of forms and how it is related to its values on dimension n ? 1. Moreover, it turns out that it is full up to dimension 7. On the other hand, on higher dimensions it is no more full and it is necessary to generalize it to obtain (using computer) a classification of forms on dimension 8 over the 2-element field. This classification is provided, together with the sizes of stabilizers of the corresponding forms.     

On the number of non-isomorphic matroids

Let f(n) denote the number of non-isomorphic matroids on an n-element set. In 1969, Welsh conjectured that, for all non-negative integers m and n, f(m+n)f(m)f(n). In this paper, we prove this conjecture.     

A classification of algorithms for multiplying polynomials of small degree over finite fields

It is shown that any optimal algorithm for computing the product of two degree-n polynomials over the q-element field, where n ≤ q, is based on the Chinese Remainder Theorem, with linear and quadratic polynomials presented as the moduli.