ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 1, Issue 3, 1995

SOME RESULTS ON THE m(4) PROBLEM OF ERDÖS AND HAJNAL.

GREGORY M. MANNING

(Communicated by Ronald Graham)

Abstract. A recursive computer program has shown that m(4) ≥ 20.

Define m(4) to be the minimum number of 4-sets of an n-set neccessary to insure a 4-set of one color exists no matter how the points of the n-set are colored, using two colors, where n is allowed to vary. Any set of quadruples satisfying the definition is called a design. Paul Seymour found a design with 23 quads on 11 points, hence m(4) ≤ 23. In 1993, J. L. Selfridge and G. M. Manning were able to show that there exists no design with 18 quads on 13 points. Using a recursive computer program Manning has shown that there are no designs with 19 quads on 13 or 14 points. The program also verified the results of Russell and Goldberg that there are no designs with 19 quads on 11 or 12 points. It is easy, though non-trivial, to rule out the cases with less than 11 or more than 14 points. It follows that m(4) ≥ 20.

Description of Algorithm for m(4) Problem

The algorithm is a large backtrack which checks a minimal list of combinations of letters against a large database of bicoloring rules.

Given the number of quads k, number of letters n, the program considers each partition of 4k, the number of blanks in the initial k × 4 diagram. Let A be the letter occuring most often. Initialize diagram D with A, leaving the blank rows at the bottom. If a bicoloring rule applies to D then we are done. If not, make a plan to show that the remaining letters must intersect the non-blank rows of D in such a way that it overflows the available spaces.

The following example illustrates the “plan” used to overflow the following diagram with k = 10 quads, n = 9 letters, and partition {6,6,6,5,5,3,3,3,3}:

\begin{matrix}c \\ ◯ \end{matrix}1995 American Mathematical Society

Received by the editors June 10, 1995, and, in revised form, October 9, 1995.

1991 Mathematics Subject Classification. 05A05; 05B30, 05D05.

SOME RESULTS ON THE m(4) PROBLEM OF ERDÖS AND HAJNAL. 113

\begin{matrix}A & B & C & . \\ A & B & . & . \\ A & C & . & . \\ A & . & . & . \\ A & . & . & . \\ A & . & . & . \\ B & . & . & . \\ C & . & . & . \\ . & . & . & . \\ . & . & . & . \end{matrix}

The dots are places where the remaining letters can go. Since A, B, and C occur respectively 6, 3, and 3 times in the diagram, the number of occurrences of the remaining letters D—I are {6,6,5,5,3,3}. In our plan we concentrate on the number of intersections of each remaining letter with the nonblank rows of the diagram, that is, the number of times each letter appears in rows 1–8. We first show that if these intersections are bounded by {4,4,3,3,1,1} then the diagram cannot yield a design. It follows that the intersections of letters D—I must be at least {5,5,4,4,2,2}, so that the 6 remaining letters take up 22 spaces, which exceeds the 20 spaces available on the nonblank rows. Thus the diagram cannot be completed to make a design.

The routine runs through all possible ways of placing each letter from the remaining letter list on the diagram D which is passed to it. For each combination the list of bicoloring rules is checked to see if the new diagram D′ can be bicolored, no matter how the remaining letters are placed. If such a rule is found, then try the next combination or the next letter. If no rule applies, then the routine recurses, this time using D′ and starting the process again with a new list of remaining letters. If all letters are added and no bicoloring rule can be applied, then we have a design. Otherwise, the search program will eventually end, implying that no design is possible with n letters and k quads.

Department of Mathematical Sciences, Northern Illinois University, DeKalb, IL, 60115.

E-mail address: manning@math.niu.edu