FUNC2 — more examples

Gowers's Weblog 2018-03-10

The first “official” post of this Polymath project has passed 100 comments, so I think it is time to write a second post. Again I will try to extract some of the useful information from the comments (but not all, and my choice of what to include should not be taken as some kind of judgment). A good way of organizing this post seems to be list a few more methods of construction of interesting union-closed systems that have come up since the last post — where “interesting” ideally means that the system is a counterexample to a conjecture that is not obviously false.

Standard “algebraic” constructions

Quotients

If $\mathcal A$ is a union-closed family on a ground set $X$ , and $Y\subset X$ , then we can take the family $\mathcal A_Y=\{A\cap Y:A\in\mathcal{A}\}$ . The map $\phi:A\to A\cap Y$ is a homomorphism (in the sense that $\phi(A\cup B)=\phi(A)\cup\phi(B)$ , so it makes sense to regard $\mathcal A_Y$ as a quotient of $\mathcal A$ .

Subfamilies

If instead we take an equivalence relation $R$ on $X$ , we can define a set-system $\mathcal A( R)$ to be the set of all unions of equivalence classes that belong to $\mathcal{A}$ .

Thus, subsets of $X$ give quotient families and quotient sets of $X$ give subfamilies.

Products

Possibly the most obvious product construction of two families $\mathcal A$ and $\mathcal B$ is to make their ground sets disjoint and then to take $\{A\cup B:A\in\mathcal A,B\in\mathcal B\}$ . (This is the special case with disjoint ground sets of the construction $\mathcal A+\mathcal B$ that Tom Eccles discussed earlier.)

Note that we could define this product slightly differently by saying that it consists of all pairs $(A,B)\in\mathcal A\times\mathcal B$ with the “union” operation $(A,B)\sqcup(A',B')=(A\cup A',B\cup B')$ . This gives an algebraic system called a join semilattice, and it is isomorphic in an obvious sense to $\mathcal A+\mathcal B$ with ordinary unions. Looked at this way, it is not so obvious how one should define abundances, because $(\mathcal A\times\mathcal B,\sqcup)$ does not have a ground set. Of course, we can define them via the isomorphism to $\mathcal A+\mathcal B$ but it would be nice to do so more intrinsically.

More “twisted” products

Tobias Fritz, in this comment, defines a more general “fibre bundle” construction as follows. Let $\mathcal K$ be a union-closed family of sets (the “base” of the system). For each $K\in\mathcal K$ let $\mathcal A_K$ be a union-closed family (one of the “fibres”), and let the elements of $\mathcal A$ consist of pairs $(K,A)$ with $A\in\mathcal A_K$ . We would like to define a join operation $\sqcup$ on $\mathcal A$ by $(K,A)\sqcup(L,B)=(K\cup L,C)$ for a suitable $C\in\mathcal A_L$ . For that we need a bit more structure, in the form of homomorphisms $\phi_{K,L}:\mathcal A_K\to\mathcal A_L$ whenever $K\subset L$ . These should satisfy the obvious composition rule $\phi_{L,M}\phi_{K,L}=\phi_{K,M}$ .

With that structure in place, we can take $C$ to be $\phi_{K,K\cup L}(A)\cup\phi_{L,K\cup L}(B)$ , and we have something like a union-closed system. To turn it into a union-closed system one needs to find a concrete realization of this “join semilattice” as a set system with the union operation. This can be done in certain cases (see the comment thread linked to above) and quite possibly in all cases.

More specific constructions

Giving more weight to less abundant elements

First, here is a simple construction that shows that Conjecture 6 from the previous post is false. That conjecture states that if you choose a random non-empty $A\in\mathcal A$ and then a random $x\in A$ , then the average abundance of $x$ is at least 1/2. It never seemed likely to be true, but it survived for a surprisingly long time, before the following example was discovered in a comment thread that starts here.

Let $m$ be a large integer and let $A,B,C$ be disjoint sets of size $1, m$ and $m^2$ . (Many details here are unimportant — for example, all that actually matters is that the sizes of the sets should increase fairly rapidly.) Now take the set system

$\{\emptyset, A, B, A\cup B, A\cup C, A\cup B\cup C\}$ .

To see that this is a counterexample, let us pick our random element $x$ of a random set, and then condition on the five possibilities for what that set is. I’ll do a couple of the calculations and then just state the rest. If $x\in A$ , then its abundance is 2/3. If it is in $B$ , then its abundance is 1/2. If it is in $A\cup B$ , then the probability that it is in $A$ is $m^{-1}$ , which is very small, so its abundance is very close to 1/2 (since with high probability the only three sets it belongs to are $B, A\cup B$ , and $A\cup B\cup C$ ). In this kind of way we get that for large enough $m$ we can make the average abundance as close as we like to

$\frac 15(2/3 + 1/2 + 1/2 + 1/3 + 1/3)=7/15<1/2$ .

One thing I would like to do — or would like someone to do — is come up with a refinement of this conjecture that isn’t so obviously false. What this example demonstrates is that duplication shows that for the conjecture to have been true, the following apparently much stronger statement would have had to be true. For each non-empty $A\in\mathcal{A}$ , let $m(A)$ be the minimum abundance of any element of $A$ . Then the average of $m(A)$ over $\mathcal A$ is at least 1/2.

How can we convert the average over $A$ into the minimum over $A$ ? The answer is simple: take the original set system $\mathcal A$ and write the elements of the ground set in decreasing order of abundance. Now duplicate the first element (that is, the element with greatest abundance) once, the second element $m$ times, the third $m^2$ times, and so on. For very large $m$ , the effect of this is that if we choose a random element of $A$ (after the duplications have taken place) then it will have minimal abundance in $A$ .

So it seems that duplication of elements kills off this averaging argument too, but in a slightly subtler way. Could we somehow iterate this thought? For example, could we choose a random $x$ by first picking a random non-empty $A\in\mathcal A$ , then a random $B\in\mathcal A$ such that $A\cap B\ne\emptyset$ , and finally a random element $x\in A\cap B$ ? And could we go further — e.g., picking a random chain of the form $A_1, A_1\cap A_2, A_1\cap A_2\cap A_3$ , etc., and stopping when we reach a set whose points cannot be separated further?

Complements of designs

Tobias Fritz came up with a nice strengthening that again turned out (again as expected) to be false. The thought was that it might be nice to find a “bijective” proof of FUNC. Defining $\mathcal A_x$ to be $\{A\in\mathcal A:x\in A\}$ and $\mathcal{A}_{\overline x}$ to be $\mathcal A\setminus\mathcal A_x$ , we would prove FUNC for $\mathcal A$ if we could find an injection from $\mathcal A_{\overline x}$ to $\mathcal A_x$ .

For such an argument to qualify as a proper bijective proof, it is not enough merely to establish the existence of an injection — that follows from FUNC on mere grounds of cardinality. Rather, one should define it in a nice way somehow. That makes it natural to think about what properties such an injection might have, and a particularly natural requirement that one might think about is that it should preserve unions.

It turns out that there are set systems $\mathcal A$ for which there does not exist any $x$ with a union-preserving injection from $\mathcal A_{\overline x}$ to $\mathcal A_x$ . After several failed attempts, I found the following example. Take a not too small pair of positive integers $r>s$ — it looks as though $r=5, s=3$ works. Then take a Steiner $(r,s)$ -system — that is, a collection $\mathcal K$ of sets of size 5 such that each set of size 3 is contained in exactly one set from $\mathcal K$ . (Work of Peter Keevash guarantees that such a set system exists, though this case was known before his amazing result.)

The counterexample is generated by all complements of sets in $\mathcal K$ , though it is more convenient just to take $\mathcal K$ and prove that there is no intersection-preserving injection from $\mathcal K_x$ to $\mathcal K_{\overline x}$ . To establish this, one first proves that any such injection would have to take sets of size $r$ to sets of size $r$ , which is basically because you need room for all the subsets of size $s$ of a set $K$ to map to distinct subsets of the image of $K$ . Once that is established, it is fairly straightforward to show that there just isn’t room to do things. The argument can be found in the comment linked to above, and the thread below it.

An example of Thomas Bloom

Thomas Bloom came up with a simpler example, which is interesting for other reasons too. His example is generated by the sets $\{1,2,3,4,5,6\}$ , all $2$ -subsets of $\{7,8,9,10\}$ , and the 6 sets $\{1,7,8\}$ , $\{2,7,9\}$ , $\{3,7,10\}$ , $\{4,8,9\}$ , $\{5,8,10\}$ , $\{6,9,10\}$ . I asked him where this set system had come from, and the answer turned out to be very interesting. He had got it by staring at an example of Renaud and Sarvate of a union-closed set system with exactly one minimal-sized set, which has size 3, such that that minimal set contains no element of abundance at least 1/2. Thomas worked out how the Renaud-Servate example had been pieced together, and used similar ideas to produce his example. Tobias Fritz then went on to show that Thomas’s construction was a special case of his fibre-bundle construction.

Conclusion

This post is by no means a comprehensive account of all the potentially interesting ideas from the last post. For example, Gil Kalai has an interesting slant on the conjecture that I think should be pursued further, and there are a number of interesting questions that were asked in the previous comment thread that I have not repeated here, mainly because the post has taken a long time to write and I think it is time to post it.