Conference rusure::math

1769.0. "Conway's Challenge Sequence" by RUSURE::EDP (Always mount a scratch monkey.) Mon Jun 21 1993 15:11

From:	US2RMC::"[email protected]" "Stanley Rabinowitz" 19-JUN-1993 22:00:44.91
To:	<rusure::edp>
CC:	
Subj:	problem

Here's a problem for the math notes conference:

A non-empty collection of non-empty finite sets
is said to be union-closed if the collection is closed under union.

Define the boundary function phi(n) to be k if all union-closed
collections of n sets have an element in k sets; and there exists a
union-closed collection of n sets in which no element occurs in k+1 sets.

The first 17 values of phi(n) are:

1 2 2 3 4 4 4 5 6 7 7 8 8 8 8 9 10

Extend this table to disprove or give more evidence for the
conjecture that phi(n)=a(n+1) where a(n) is the Conway
sequence defined by

a(1)=1 a(2)=1 a(n)=a(a(n-1))+a(n-a(n-1)) for n>2.

This is an unsolved problem and will surely merit
publication if you either prove or disprove the conjecture.

REFERENCES:

J.-C. Renaud and L. F. Fitina, On Union-Closed Sets and
Conway's Sequence, Bulletin of the Australian Mathematical
Society, 47(1993)321-332

C. I. Mallows, Conway's Challenge Sequence, American
Mathematical Monthly, 98(1991)5-20.

J.-C. Renaud, Is the Union-Closed Sets Conjecture the Best
Possible?, Journal of the Australian Mathematical Society,
series A, 51(1991)276-283.



% ====== Internet headers and postmarks (see DECWRL::GATEWAY.DOC) ======
% Received: by us2rmc.bb.dec.com; id AA21268; Sat, 19 Jun 93 22:00:48 -0400
% Received: by inet-gw-1.pa.dec.com; id AA13834; Sat, 19 Jun 93 19:02:25 -0700
% Received: by iha.compuserve.com (5.67/5.930129sam) id AA00631; Sat, 19 Jun 93 22:00:55 -040
% Date: 19 Jun 93 21:58:28 EDT
% From: Stanley Rabinowitz <[email protected]>
% To: <rusure::edp>
% Subject: problem
% Message-Id: <[email protected]>