FUNC1 — strengthenings, variants, potential counterexamples

Gowers's Weblog 2018-03-10

After my tentative Polymath proposal, there definitely seems to be enough momentum to start a discussion “officially”, so let’s see where it goes. I’ve thought about the question of whether to call it Polymath11 (the first unclaimed number) or Polymath12 (regarding the polynomial-identities project as Polymath11). In the end I’ve gone for Polymath11, since the polynomial-identities project was listed on the Polymath blog as a proposal, and I think the right way of looking at things is that the problem got solved before the proposal became a fully-fledged project. But I still think that that project should be counted as a Polymathematical success story: it shows the potential benefits of opening up a problem for consideration by anybody who might be interested.

Something I like to think about with Polymath projects is the following question: if we end up not solving the problem, then what can we hope to achieve? The Erdős discrepancy problem project is a good example here. An obvious answer is that we can hope that enough people have been stimulated in enough ways that the probability of somebody solving the problem in the not too distant future increases (for example because we have identified more clearly the gap in our understanding). But I was thinking of something a little more concrete than that: I would like at the very least for this project to leave behind it an online resource that will be essential reading for anybody who wants to attack the problem in future. The blog comments themselves may achieve this to some extent, but it is not practical to wade through hundreds of comments in search of ideas that may or may not be useful. With past projects, we have developed Wiki pages where we have tried to organize the ideas we have had into a more browsable form. One thing we didn’t do with EDP, which in retrospect I think we should have, is have an official “closing” of the project marked by the writing of a formal article that included what we judged to be the main ideas we had had, with complete proofs when we had them. An advantage of doing that is that if somebody later solves the problem, it is more convenient to be able to refer to an article (or preprint) than to a combination of blog comments and Wiki pages.

With an eye to this, I thought I would make FUNC1 a data-gathering exercise of the following slightly unusual kind. For somebody working on the problem in the future, it would be very useful, I would have thought, to have a list of natural strengthenings of the conjecture, together with a list of “troublesome” examples. One could then produce a table with strengthenings down the side and examples along the top, with a tick in the table entry if the example disproves the strengthening, a cross if it doesn’t, and a question mark if we don’t yet know whether it does.

A first step towards drawing up such a table is of course to come up with a good supply of strengthenings and examples, and that is what I want to do in this post. I am mainly selecting them from the comments on the previous post. I shall present the strengthenings as statements rather than questions, so they are not necessarily true.

Strengthenings

1. A weighted version.

Let $w$ be a function from the power set of a finite set $X$ to the non-negative reals. Suppose that the weights satisfy the condition $w(A\cup B)\geq\max\{w(A),w(B)\}$ for every $A,B\subset X$ and that at least one non-empty set has positive weight. Then there exists $x\in X$ such that the sum of the weights of the sets containing $x$ is at least half the sum of all the weights.

Note that if all weights take values 0 or 1, then this becomes the original conjecture. It is possible that the above statement follows from the original conjecture, but we do not know this (though it may be known).

This is not a good question after all, as the deleted statement above is false. When $w$ is 01-valued, the statement reduces to saying that for every up-set there is an element in at least half the sets, which is trivial: all the elements are in at least half the sets. Thanks to Tobias Fritz for pointing this out.

2. Another weighted version.

Let $w$ be a function from the power set of a finite set $X$ to the non-negative reals. Suppose that the weights satisfy the condition $w(A\cup B)\geq\min\{w(A),w(B)\}$ for every $A,B\subset X$ and that at least one non-empty set has positive weight. Then there exists $x\in X$ such that the sum of the weights of the sets containing $x$ is at least half the sum of all the weights.

Again, if all weights take values 0 or 1, then the collection of sets of weight 1 is union closed and we obtain the original conjecture. It was suggested in this comment that one might perhaps be able to attack this strengthening using tropical geometry, since the operations it uses are addition and taking the minimum.

3. An “off-diagonal” version.

Tom Eccles suggests (in this comment) a generalization that concerns two set systems rather than one. Given set systems $\mathcal{A}$ and $\mathcal{B}$ , write $\mathcal{A}+\mathcal{B}$ for the union set $\{A\cup B:A\in\mathcal{A},B\in\mathcal{B}\}$ . A family $\mathcal{A}$ is union closed if and only if $|\mathcal{A}+\mathcal{A}|\leq|\mathcal{A}|$ . What can we say if $\mathcal{A}$ and $\mathcal{B}$ are set systems with $\mathcal{A}+\mathcal{B}$ small? There are various conjectures one can make, of which one of the cleanest is the following: if $\mathcal{A}$ and $\mathcal{B}$ are of size $k$ and $\mathcal{A}+\mathcal{B}$ is of size at most $k$ , then there exists $x$ such that $|\mathcal{A}_x|+|\mathcal{B}_x|\geq k$ , where $\mathcal{A}_x$ denotes the set of sets in $\mathcal{A}$ that contain $x$ . This obviously implies FUNC.

Simple examples show that $\mathcal{A}+\mathcal{B}$ can be much smaller than either $\mathcal{A}$ or $\mathcal{B}$ — for instance, it can consist of just one set. But in those examples there always seems to be an element contained in many more sets. So it would be interesting to find a good conjecture by choosing an appropriate function $\phi$ to insert into the following statement: if $|\mathcal{A}|=r$ , $|\mathcal{B}|=s$ , and $|\mathcal{A}+\mathcal{B}|\leq t$ , then there exists $x$ such that $|\mathcal{A}_x|+|\mathcal{B}_x|\geq\phi(r,s,t)$ .

4. A first “averaged” version.

Let $\mathcal{A}$ be a union-closed family of subsets of a finite set $X$ . Then the average size of $\mathcal{A}_x$ is at least $\frac 12|\mathcal{A}|$ .

This is false, as the example $\Bigl\{\emptyset,\{1\},\{1,2,\dots,m\}\Bigr\}$ shows for any $m\geq 3$ .

5. A second averaged version.

Let $\mathcal{A}$ be a union-closed family of subsets of a finite set $X$ and suppose that $\mathcal{A}$ separates points, meaning that if $x\ne y$ , then at least one set in $\mathcal{A}$ contains exactly one of $x$ and $y$ . (Equivalently, the sets $\mathcal{A}_x$ are all distinct.) Then the average size of $\mathcal{A}_x$ is at least $\frac 12|\mathcal{A}|$ .

This again is false: see Example 2 below.

6. A better “averaged” version.

In this comment I had a rather amusing (and typically Polymathematical) experience of formulating a conjecture that I thought was obviously false in order to think about how it might be refined, and then discovering that I couldn’t disprove it (despite temporarily thinking I had a counterexample). So here it is.

As I have just noted (and also commented in the first post), very simple examples show that if we define the “abundance” $a(x)$ of an element $x$ to be $|\mathcal{A}_x|/|\mathcal{A}|$ , then the average abundance does not have to be at least $1/2$ . However, that still leaves open the possibility that some kind of naturally defined weighted average might do the job. Since we want to define the weighting in terms of $\mathcal{A}$ and to favour elements that are contained in lots of sets, a rather crude idea is to pick a random non-empty set $A\in\mathcal{A}$ and then a random element $x\in A$ , and make that the probability distribution on $X$ that we use for calculating the average abundance.

A short calculation reveals that the average abundance with this probability distribution is equal to the average overlap density, which we define to be $\mathbb{E}_{A\ne\emptyset}\mathbb{E}_B|A\cap B|/|A|,$ where the averages are over $\mathcal{A}$ . So one is led to the following conjecture, which implies FUNC: if $\mathcal{A}$ is a union-closed family of sets, at least one of which is non-empty, then its average overlap density is at least 1/2.

A not wholly pleasant feature of this conjecture is that the average overlap density is very far from being isomorphism invariant. (That is, if you duplicate elements of $X$ , the average overlap density changes.) Initially, I thought this would make it easy to find counterexamples, but that seems not to be the case. It also means that one can give some thought to how to put a measure on $X$ that makes the average overlap density as small as possible. Perhaps if the conjecture is true, this “worst case” would be easier to analyse. (It’s not actually clear that there is a worst case — it may be that one wants to use a measure on $X$ that gives measure zero to some non-empty set $A$ , at which point the definition of average overlap density breaks down. So one might have to look at the “near worst” case.)

7. Compressing to an up-set.

This conjecture comes from a comment by Igor Balla. Let $\mathcal{A}$ be a union-closed family and let $x\in X$ . Define a new family $\mathcal{A}_x$ by replacing each $A\in\mathcal{A}$ by $A\cup\{x\}$ if $A\cup\{x\}\notin\mathcal{A}$ and leaving it alone if $A\cup\{x\}\in\mathcal{A}$ . Repeat this process for every $x\in X$ and the result is an up-set $\mathcal{B}$ , that is, a set-system $\mathcal{B}$ such that $B_1\in\mathcal{B}$ and $B_1\subset B_2$ implies that $B_2\in\mathcal{B}$ .

Note that each time we perform the “add $x$ if you can” operation, we are applying a bijection to the current set system, so we can compose all these bijections to obtain a bijection $\phi$ from $\mathcal{A}$ to $\mathcal{B}$ .

Suppose now that $A,B\in\mathcal{A}$ are distinct sets. It can be shown that there is no set $C$ such that $A\subset C\subset\phi(A)$ and $B\subset C\subset\phi(B)$ . In other words, $A\cup B$ is never a subset of $\phi(A)\cap\phi(B)$ .

Now the fact that $\mathcal{B}$ is an up-set means that each element $x$ is in at least half the sets (since if $x\notin B$ then $x\in B\cup\{x\}$ ). Moreover, it seems hard for too many sets $A$ in $\mathcal{A}$ to be “far” from their images $\phi(A)$ , since then there is a strong danger that we will be able to find a pair of sets $A$ and $B$ with $A\cup B\subset\phi(A)\cap\phi(B)$ .

This leads to the conjecture that Balla makes. He is not at all confident that it is true, but has checked that there are no small counterexamples.

Conjecture. Let $\mathcal{A}$ be a set system such that there exist an up-set $\mathcal{B}$ and a bijection $\phi:\mathcal{A}\to\mathcal{B}$ with the following properties.

For each $A\in\mathcal{A}$ , $A\subset\phi(A)$ .
For no distinct $A,B\in\mathcal{A}$ do we have $A\cup B\subset\phi(A)\cap\phi(B)$ .

Then there is an element $x$ that belongs to at least half the sets in $\mathcal{A}$ .

The following comment by Gil Kalai is worth quoting: “Years ago I remember that Jeff Kahn said that he bet he will find a counterexample to every meaningful strengthening of Frankl’s conjecture. And indeed he shot down many of those and a few I proposed, including weighted versions. I have to look in my old emails to see if this one too.” So it seems that even to find a conjecture that genuinely strenghtens FUNC without being obviously false (at least to Jeff Kahn) would be some sort of achievement. (Apparently the final conjecture above passes the Jeff-Kahn test in the following weak sense: he believes it to be false but has not managed to find a counterexample.)

Examples and counterexamples

1. Power sets.

If $X$ is a finite set and $\mathcal{A}$ is the power set of $X$ , then every element of $X$ has abundance 1/2. (Remark 1: I am using the word “abundance” for the proportion of sets in $\mathcal{A}$ that contain the element in question. Remark 2: for what it’s worth, the above statement is meaningful and true even if $X$ is empty.)

Obviously this is not a counterexample to FUNC, but it was in fact a counterexample to an over-optimistic conjecture I very briefly made and then abandoned while writing it into a comment.

2. Almost power sets

This example was mentioned by Alec Edgington. Let $X$ be a finite set and let $z$ be an element that does not belong to $X$ . Now let $\mathcal{A}$ consist of $\emptyset$ together with all sets of the form $A\cup\{z\}$ such that $A\subset X$ .

If $|X|=n$ , then $z$ has abundance $1-1/(2^n+1)$ , while each $x\in X$ has abundance $2^{n-1}/(2^n+1)$ . Therefore, only one point has abundance that is not less than 1/2.

A slightly different example, also used by Alec Edgington, is to take all subsets of $X$ together with the set $X\cup\{z\}$ . If $|X|=n$ , then the abundance of any element of $X$ is $(2^{n-1}+1)/(2^n+1)$ while the abundance of $z$ is $1/(2^n+1)$ . Therefore, the average abundance is $\displaystyle \frac n{n+1}\frac{2^{n-1}+1}{2^n+1}+\frac 1{n+1}\frac 1{2^n+1}.$ When $n$ is large, the amount by which $(2^{n-1}+1)/(2^n+1)$ exceeds 1/2 is exponentially small, from which it follows easily that this average is less than 1/2. In fact, it starts to be less than 1/2 when $n=2$ (which is the case Alec mentioned). This shows that Conjecture 5 above (that the average abundance must be at least 1/2 if the system separates points) is false.

3. Empty set, singleton, big set.

Let $m$ be a positive integer and take the set system that consists of the sets $\emptyset, \{1\}$ and $\{1,2,\dots,m\}$ . This is a simple example (or rather class of examples) of a set system for which although there is certainly an element with abundance at least 1/2 (the element $1$ has abundance 2/3), the average abundance is close to 1/3. Very simple variants of this example can give average abundances that are arbitrarily small — just take a few small sets and one absolutely huge set.

4. Using strong divisibility sequences.

I will not explain these in detail, but just point you to an interesting comment by Uwe Stroinski that suggests a number-theoretic way of constructing union-closed families.

I will continue with methods of building union-closed families out of other union-closed families.

5. Duplicating elements.

I’ll define this process formally first. Let $X$ be a set of size $n$ and let $\mathcal{A}$ be a collection of subsets of $X$ . Now let $\{E(x):x\in X\}$ be a collection of disjoint non-empty sets and define $E(\mathcal{A})$ to be the collection of all sets of the form $\bigcup_{x\in A}E(x)$ for some $A\in\mathcal{A}$ . If $\mathcal{A}$ is union closed, then so is $E(\mathcal{A})$ .

One can think of $E(x)$ as “duplicating” the element of $x$ $|E(x)|$ times. A simple example of this process is to take the set system $\emptyset, \{1\}, \{1,2\}$ and let $E(1)=\{1\}$ and $E(2)=\{2,3,\dots,m\}$ . This gives the set system 3 above.

Let us say that $\mathcal{A}\rightarrow\mathcal{B}$ if $\mathcal{B}=E(\mathcal{A})$ for some suitable set-valued function $E$ . And let us say that two set systems are isomorphic if they are in the same equivalence class of the symmetric-transitive closure of the relation $\rightarrow$ . Equivalently, they are isomorphic if we can find $E_1$ and $E_2$ such that $E_1(\mathcal{A})=E_2(\mathcal{B})$ .

The effect of duplication is basically that we can convert the uniform measure on the ground set into any other probability measure (at least to an arbitrary approximation). What I mean by that is that the uniform measure on the ground set of $E(\mathcal{A})$ , which is of course $\bigcup_x E(x)$ , gives you a probability of $|E(x)|/\sum|E(x)|$ of landing in $E(x)$ , so has the same effect as assigning that probability to $x$ and sticking with the set system $\mathcal{A}$ . (So the precise statement is that we can get any probability measure where all the probabilities are rational.)

If one is looking for an averaging argument, then it would seem that a nice property that such an argument might have is (as I have already commented above) that the average should be with respect to a probability measure on $X$ that is constructed from $\mathcal{A}$ in an isomorphism-invariant way.

It is common in the literature to outlaw duplication by insisting that $\mathcal{A}$ separates points. However, it may be genuinely useful to consider different measures on the ground set.

6. Union-sets.

Tom Eccles, in his off-diagonal conjecture, considered the set system, which he denoted by $\mathcal{A}+\mathcal{B}$ , that is defined to be $\{A\cup B:A\in\mathcal{A},B\in\mathcal{B}\}$ . This might more properly be denoted $\mathcal{A}\cup\mathcal{B}$ , by analogy with the notation $A+B$ for sumsets, but obviously one can’t write it like that because that notation already stands for something else, so I’ll stick with Tom’s notation.

It’s trivial to see that if $\mathcal{A}$ and $\mathcal{B}$ are union closed, then so is $\mathcal{A}+\mathcal{B}$ . Moreover, sometimes it does quite natural things: for instance, if $X$ and $Y$ are any two sets, then $P(X)+P(Y)=P(X\cup Y)$ , where $P$ is the power-set operation.

Another remark is that if $X$ and $Y$ are disjoint, and $\mathcal{A}\subset P(X)$ and $\mathcal{B}\subset P(Y)$ , then the abundance of $x$ in $\mathcal{A}$ is equal to the abundance of $x$ in $\mathcal{A}+\mathcal{B}$ .

7. A less obvious construction method.

I got this from a comment by Thomas Bloom. Let $X$ and $Y$ be disjoint finite sets and let $\mathcal A$ and $\mathcal B$ be two union-closed families living inside $X$ and $Y$ , respectively, and assume that $X\in\mathcal A$ and $Y\in\mathcal B$ . We then build a new family as follows. Let $\phi$ be some function from $X$ to $\mathcal{B}$ . Then take all sets of one of the following four forms:

sets $A\cup Y$ with $A\in\mathcal{A}$ ;
sets $X\cup B$ with $B\in\mathcal{B}$ ;
sets $(X\setminus\{x\})\cup\phi(x)$ with $x\in X$ ;
sets $(X\setminus\{x\})\cup Y$ with $x\in X$ .

It can be checked quite easily (there are six cases to consider, all straightforward) that the resulting family is union closed.

Thomas Bloom remarks that if $\mathcal A$ consists of all subsets of $\{1,2,3\}$ and $\mathcal B$ consists of all subsets of $\{4,5,6\}$ , then (for suitable $\phi$ ) the result is a union-closed family that contains no set of size less than 3, and also contains a set of size 3 with no element of abundance greater than or equal to 1/2. This is interesting because a simple argument shows that if $A$ is a set with two elements in a union-closed family then at least one of its elements has abundance at least 1/2.

Thus, this construction method can be used to create interesting union-closed families out of boring ones.

Thomas discusses what happens to abundances when you do this construction, and the rough answer is that elements of $Y$ become less abundant but elements of $X$ become quite a lot more abundant. So one can’t just perform this construction a few times and end up with a counterexample to FUNC. However, as Thomas also says, there is plenty of scope for modifying this basic idea, and maybe good things could flow from that.

I feel as though there is much more I could say, but this post has got quite long, and has taken me quite a long time to write, so I think it is better if I just post it. If there are things I wish I had mentioned, I’ll put them in comments and possibly repeat them in my next post.

I’ll close by remarking that I have created a wiki page. At the time of writing it has almost nothing on it but I hope that will change before too long.