Outdated Archival Version

These pages are not updated anymore. They reflect the state of 20 August 2005. For the current production of this journal, please refer to http://www.math.psu.edu/era/.

\input amstex
\documentstyle{era-ams}
\topmatter
\title 
Some results on the $m(4)$ problem of Erd\"os and Hajnal.
\endtitle                    
\author Gregory M. Manning \endauthor
\date June 10, 1995\inRevisedForm October 9, 1995 \enddate
\cvol{1}
\cvolno{3}
\cvolyear{1995}
\cyear{1995}
\communicatedby{Ronald Graham}
\abstract
A recursive computer program has shown that $m(4)\ge20$.
\endabstract
\subjclass 05A05; 05B30, 05D05 \endsubjclass
\address Department of Mathematical Sciences, Northern
Illinois University, DeKalb, IL, 60115. \endaddress
\email  manning\@math.niu.edu \endemail

\advance\pageno by 111

\endtopmatter

\document

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 {\it design}.  Paul Seymour found a design with 23 quads 
on 11 points, hence $m(4) \le 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) \ge 20$.
\bigskip
\centerline{\bf Description of Algorithm for $m(4)$ Problem}
\bigskip
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\times 4$ diagram.
Let A be the letter occuring most often.  Initialize diagram $\Cal D$ with A,
leaving the blank rows at the bottom.  If a bicoloring rule applies to $\Cal D$
then we are done.  If not, make a {\it plan} to show that the remaining
letters must intersect the non-blank rows of $\Cal D$ in such a way that it
{\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\}:

\vfill\eject
$$
\alignedat4 
A&\ &B&\ &C&\ \ .&\\
A&\ &B&\ &.&\ \ .&\\
A&\ &C&\ &.&\ \ .&\\
A&\ &.&\ &.&\ \ .&\\
A&\ &.&\ &.&\ \ .&\\
A&\ &.&\ &.&\ \ .&\\
B&\ &.&\ &.&\ \ .&\\
C&\ &.&\ &.&\ \ .&\\
.&\ &.&\ &.&\ \ .&\\
.&\ &.&\ &.&\ \ .&
\endalignedat
$$


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 $\Cal D$ which is passed to it.  
For each combination the list of bicoloring rules is checked to see if 
the new diagram $\Cal D'$ can be bicolored, 
{\it 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 $\Cal 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.


\enddocument