Testing a conjecture of Veronica Phan for small union closed families of sets

MO501474.py

#!/usr/bin/pypy3

def gen_union_closed_families(n, forced_inclusions = []):
	all_bits = (1 << n) - 1

	def search(i, incl):
		if i > all_bits:
			yield incl
			return

		if i not in incl:
			ext = set([i]) | set(i | s for s in incl)
			yield from search(i+1, incl | ext)

		yield from search(i+1, incl)

	yield from search(0, set(forced_inclusions))


def check_MO501474(n, F):
	u = [sum(1 for f in F if f & (1 << i)) for i in range(n)]
	l = [len(F) - ui for ui in u]
	P = [1] * (1 << n)
	for S in range(1 << n):
		for i in range(n):
			P[S] *= u[i] if (S & (1 << i)) else l[i]

	lhs = sum(P[S & ~max(MS for MS in F if (MS & S) == MS)] for S in range(1 << n))
	return lhs <= len(F)**n


for n in range(6):
	checked = 0
	for F in gen_union_closed_families(n, [0]):
		if check_MO501474(n, F):
			checked += 1
		else:
			print(f"Counterexample: {F} with n={n}")
			exit(0)
	print(f"{n}: checked {checked}")