A too-short sequence based on Property B

[magictour at free.fr]

 >Definition:  We work inside a finite set X of unspecified
 >size. A collection C of subsets of X, all of size n, has Property B if
 >we can partition X into two disjoint subsets X = Y union Z
 >such that every set in C meets both Y and Z.
 >
 >m(n) is the smallest number of sets of size n that
 >do not have Property B.
 >
 >m(1)=1,m(2)=3,m(3)=7, 20<m(4)<24


When A,B are sets, denote by A<B that A is a subset of B, including A=B and
A={}.
For a positive integer m, let N(m):={1,2,...,m}
For positive integers m,n with m>=n let _P(m,n) be set of all
 subsets of N(m) of size n and _let _P(m) be the powerset of N(m).
_P(m) is obviously the union of the _P(m,n) over all n with n<=m.

For X in _P(m) let _Y(m,X):={S in _P(m) , S/\X={} or S/\(N(m)-X)={} }

For m,n with n<=m let c(m,n) be the minimum size of a covering
  of _P(m) by sets of the form _Y(m,X) with X in _P(m,n).

Then Neil's m(n) is the minimum of all c(m,n) with m>=n .


What values or bounds of c(m,n) are known for small m,n ?
Is c(m,n) monotone ?
What's the minimum m for which c(m,n)=m(n) ?

What fast computer programs are available to compute the minimum
size of a covering ? How far(m,n) can they go ?
Are there better methods to compute c(m,n) ?

We get a collection of binomial(m,n) subsets _Y(m,X) of _P(m) which
 have to be examined for a minimal cover of _P(m).

For m=7,n=3 this gives 35 subsets to cover a set with 128 elements.
For m=21,n=4 it gives 5985 subsets to cover a set with 2097152 elements.
Can it be done ?


OK, using a greedy algorithm without backtracking
I get these upper bounds for c(m,n):
n=1,m=1,2,.. : 1,1,..
n=2,m=3,4,.. : 3,3,...
n=3,m=5,6,.. : 10,10,7,7,...
n=4,m=7,8,.. : 35,35,31,33,30,32,32,34,36,37,39,...
n=5,m=9,10,..: 126,126,67,90,87,90,93,93,97,...
n=6,m=11,12,.. : 462,474,320,322,275,284,...
n=7,m=13,14    : 1716,1721

with some hillclimbing I could improve upper bounds:
c(9,4)<=26,c(10,4)<=26,c(11,4)<=23,c(12,4)<=28,c(11,5)<=66,c(13,5)<=84
the c(11,4)=23 construction is quite natural/symmetric and hillclimbing
converged to it several times with no other solution found.
This supports c(11,4)=23.
Using 22 sets, I could only cover 2032 of the 2048 members in _P(11).
Typical values with greedy algo were for s=19..28 :
1956,1982,2012,2014,2018,2030,2034,2042,2044,2048.
So gaps of 2032->2048 are typically only closed by some special
cleverly planted design and not by more brute force.
So my guess is c(11,4)=23 and c(i,4)>c(11,4) for other i
but this is less certain.

-----------------------------------



As for the lower bounds of c(m,n) let's define for S in P(m), n<=m :
E(S,m,n):={C in _P(m,n) , C/\X != {} and C/\(N(m)-X) != {} }
F(S,m,n,s) := { _C subset of _P(m,n), |_C|=s , _C < E(S,m,n) }
G(m,n,s) := union of all F(S,m,n,s) over all S in P(m)
g(m,n,s) := |G(m,n,s)|

For s being a lower bound for c(m,n) we need :
f.a. _C < P(m,n) , |_C|=s t.e. X in P(m) , _C < E(X,m,n)
f.a. _C < P(m,n) , |_C|=s t.e. X in P(m) , _C in F(X,m,n,s)
f.a. _C < P(m,n) , |_C|=s  _C <  G(m,n,s)
P(P(m,n),s) < G(m,n,s)
g(m,n,s) = binomial(binomial(m,n),s)




for C in P(m) let U(C):={X in P(m) , U meets both X and N(m)-X }
obviously X in U(C) , iff
 |X/\U| is in {1,..|U|-1} and there is no restriction on X/\(N(m)-U)
 so U(C) has size (2^|U|-2)*2^(m-|U|) = 2^m-2^(m-|U|+1)
for _C subset of P(m) let V(_C):= intersection of all U(C) for C in _C

For s being a lower bound for c(m,n) we need :
f.a. _C in P(P(m,n),s) : V(_C)!={}
each C in such _C has order 2^m-2^(m-n+1)

we can compute the binomial(m,n) sets U(C) and then see whether
we can find s of them whose intersection is empty.

we can restrict to those X in U(C) with |X|=m-1
that gives n*s possibilities to calculate for each _C




for each n*s matrix with s distinct rows from P(m,n)
select one element from each row into X
select one element from each row into Y
such that X and Y are disjoint.




Ok, but we have to walk through all binomial(binomial(m,n),s)
matrices (set-systems) which is  1e26  (reduced by m!)
for m=11,n=4,s=22 , which is out of reach for direct computation.
I can't see how to reduce the search ?!?


--Guenter.  sterten(at)aol.com


--Guenter.