FUNC3 — further strengthenings and variants

Gowers's Weblog 2018-03-10

In the last post I concentrated on examples, so in this one I’ll concentrate on conjectures related to FUNC, though I may say a little about examples at the end, since a discussion has recently started about how we might go about trying to find a counterexample to FUNC.

A proposal for a rather complicated averaging argument

After the failure of the average-overlap-density conjecture, I came up with a more refined conjecture along similar lines that has one or two nice properties and has not yet been shown to be false.

The basic aim is the same: to take a union-closed family $\mathcal A$ and use it to construct a probability measure on the ground set in such a way that the average abundance with respect to that measure is at least 1/2. With the failed conjecture the method was very basic: pick a random non-empty set $A\in\mathcal A$ and then a random element $x\in A$ .

The trouble with picking random elements is that it gives rise to a distribution that does not behave well when you duplicate elements. (What you would want is that the probability is shared out amongst the duplicates, but in actual fact if you duplicate an element lots of times it gives an advantage to the set of duplicates that the original element did not have.) This is not just an aesthetic concern: it was at the heart of the downfall of the conjecture. What one really wants, and this is a point that Tobias Fritz has been emphasizing, is to avoid talking about the ground set altogether, something one can do by formulating the conjecture in terms of lattices, though I’m not sure what I’m about to describe does make sense for lattices.

Let $\mathcal A$ be a union-closed set system with ground set $X$ . Define a chain to be a collection $B_1\supset\dots\supset B_k$ of subsets of $X$ with the following properties.

The inclusions are strict.
Each $B_i$ is an intersection of sets in $A$ .
$B_k$ is non-empty, but for every $A\in\mathcal A$ , either $A\cap B_k=\emptyset$ or $B_k\subset A$ .

The idea is to choose a random chain and then a random element of $B_k$ . That last step is harmless because the elements of $B_k$ are indistinguishable from the point of view of $\mathcal A$ (they are all contained in the same sets). So this construction behaves itself when you duplicate elements.

What exactly is a random chain? What I suggested before was to run an algorithm like this. You start with $B_1=X$ . Having got to $B_i$ , let $\mathcal A_i$ consist of all sets $A\in\mathcal A$ such that $A\cap B$ is neither empty nor $B$ , pick a random set $A\in\mathcal A_i$ , and let $B_{i+1}=B_i\cap A$ . But that is not the only possibility. Another would be to define a chain to be maximal if for every $i$ there is no set $A\in\mathcal A$ such that $A\cap B_{i-1}$ lies strictly between $B_i$ and $B_{i-1}$ , and then to pick a maximal chain uniformly at random.

At the moment I think that the first idea is more natural and therefore more likely to work. (But “more likely” does not imply “likely”.) The fact that it seems hard to disprove is not a good reason for optimism, since the definition is sufficiently complicated that it is hard to analyse. Perhaps there is a simple example for which the conjecture fails by miles, but for which it is very hard to prove that it fails by miles (other than by checking it on a computer if the example is small enough).

Another possible idea is this. Start a random walk at $X$ . The walk takes place on the set of subsets of $X$ that are non-empty intersections of sets in $\mathcal A$ . Call this set system $I(\mathcal A)$ . Then join $B$ to $B'$ in $I(A)$ if $B$ is a proper subset of $B'$ and there is no $B''\in I(A)$ that lies properly between $B$ and $B'$ . To be clear, I’m defining an undirected graph here, so if $B$ is joined to $B'$ , then $B'$ is joined to $B$ .

Now we do a random walk on this graph by picking a random neighbour at each stage, and we take its stationary distribution. One could then condition this distribution on the set you are at being a minimal element of $I(\mathcal A)$ . This gives a distribution on the minimal elements, and then the claim would be that on average a minimal element is contained in at least half the sets in $\mathcal A$ .

I’ll finish this section with the obvious question.

Question. Does an averaging argument with a probability distribution like one of these have the slightest chance of working? If so, how would one go about proving it?

Describing union-closed families using Horn clauses

Tobias Fritz has shared with us a very nice observation that gives another way of looking at union-closed families. It is sufficiently natural that I feel there is a good chance that it will be genuinely helpful, and not just a slightly different perspective on all the same statements.

Let $X$ be a finite set, let $x\in X$ and let $B\subset X$ be a non-empty subset of $X$ . Write $(x,B)$ as shorthand for the condition

$x\in A\implies A\cap B\ne\emptyset$ .

If $B=\{b_1,\dots,b_k\}$ , then we can write this as a Horn clause

$x\in A\implies b_1\in A\vee\dots\vee b_k\in A$ .

If $(x_1,B_1),\dots,(x_r,B_r)$ is a collection of conditions of this kind, then we can define a set system $\mathcal A$ to consist of all sets $A$ that satisfy all of them. That is, for each $i$ , if $x_i\in A$ , then $A\cap B_i\ne\emptyset$ .

It is very easy to check that any set system $\mathcal A$ defined this way is union closed and contains the empty set. Conversely, given a union-closed family $\mathcal A$ that includes the empty set, let $C$ be a subset of $X$ that does not belong to $\mathcal A$ . If for every $x\in C$ we can find $A_x\in\mathcal A$ such that $x\in A_x\subset C$ , then we have a contradiction, since the union of these $A_x$ belongs to $\mathcal A$ and is equal to $C$ . So there must be some $x$ such that for every $A\in\mathcal A$ , if $x\in A$ , then $A\cap(X\setminus C)\ne\emptyset$ . That is, there is a condition $(x,X\setminus C)$ that is satisfied by every $A\in\mathcal A$ and is not satisfied by $C$ . Taking all such conditions, we have a collection of conditions that gives rise to precisely the set system $\mathcal A$ .

As Thomas says, this is strongly reminiscent of describing a convex body not as a set of points but as an intersection of half spaces. Since that dual approach is often extremely useful, it seems very much worth bearing in mind when thinking about FUNC. At the very least, it gives us a concise way of describing some union-closed families that would be complicated to define in a more element-listing way: Tobias used it to describe one of Thomas Bloom’s examples quite concisely, for instance.

Generalizing the idea

Suppose we have a Horn-clause description of a union-closed family $\mathcal A$ . For each $x\in X$ , it gives us a collection of conditions that $A$ must satisfy, each of the form $x_1\in A\vee\dots\vee x_k\in A$ . Putting all these together gives us a single condition in conjunctive normal form. This single condition is a monotone property of $\mathcal A$ , and any monotone property can arise in this way. So if we want, we can forget about Horn clauses and instead think of an arbitrary union-closed family as being defined as follows. For each $x\in X$ , there is some monotone property $P_x$ , and then $\mathcal A$ consists of all sets $A$ such that for every $x\in A$ , the property $P_x(A)$ holds.

To illustrate this with an example (not one that has any chance of being a counterexample to FUNC — just an example of the kind of thing one can do), we could take $X=\mathbb{Z}_p$ (the integers mod a prime $p$ ) and take $P_x$ to be the property “contains a subset of the form $\{a,a+x,\dots,a+(r-1)x\}$ “. Note that this is a very concise definition, but the resulting criterion for a set $A$ to belong to $\mathcal A$ is not simple at all. (If you think it is, then can you exhibit for me a non-empty set $A$ of density less than 1/2 that satisfies the condition when $r=10$ , or prove that no such set exists? Update: I’ve now realized that this question has a fairly easy answer — given in a comment below. But describing the sets that satisfy the condition would not be simple.)

Natural questions that arise

This way of looking at union-closed families also generates many special cases of FUNC that could be interesting to tackle. For example, we can take the ground set $X$ to be some structure (above, I took a cyclic group, but one could also take, for instance, the complete graph on a set $V$ of vertices) and restrict attention to properties $P_x$ that are natural within that structure (where “natural” could mean something like invariant under symmetries of the structure that fix $x$ ).

Another special case that is very natural to think about is where each property $P_x$ is a single disjunction — that is, the Horn-clause formulation in the special case where each $x$ is on the left of exactly one Horn clause. Is FUNC true in this case? Or might this case be a good place to search for a counterexample? At the time of writing, I have no intuition at all about this question, so even heuristic arguments would be interesting.

A question of Gil Kalai

As discussed in the last post, we already know that an optimistic conjecture of Tobias Fritz, that there is always some $x$ and a union-preserving injection from $\mathcal A_{\overline x}$ to $\mathcal A_x$ , is false. Gil Kalai proposed a conjecture in a similar spirit: that there is always an injection from $\mathcal A_{\overline x}$ to $\mathcal A_x$ such that each set in $\mathcal A_{\overline x}$ is a subset of its image. So far, nobody (or at least nobody here) has disproved this. I tried to check whether the counterexamples to Tobias’s conjecture worked here too, and I’m fairly sure the complement-of-Steiner-system approach doesn’t work.

While the general belief seems to be (at least if we believe Jeff Kahn) that such strengthenings are false, it would be very good to confirm this. Of course it would be even better to prove the strengthening …

Update: Alec Edgington has now found a counterexample.

A question of Tom Eccles

In this comment Tom Eccles asked a question motivated by thinking about what an inductive proof of FUNC could possibly look like. The question ought to be simpler than FUNC, and asks the following. Does there exist a union-closed family $\mathcal A$ and an element $x\in X$ with the following three properties?

$x$ has abundance less than 1/2.
No element has abundance greater than or equal to 1/2 in both $\mathcal A_x$ and $\mathcal A_{\overline x}$ .
Both $\mathcal A_x$ and $\mathcal A_{\overline x}$ contain at least one non-empty set.

It would be very nice to have such an example, because it would make an excellent test case for proposed inductive approaches.

There’s probably plenty more I could extract from the comment thread in the last post, but I think it’s time to post this, since the number of comments has exceeded 100.

While I’m saying that, let me add a general remark that if anyone thinks that a direction of discussion is being wrongly neglected, then please feel free to highlight it, even (or perhaps especially) if it is a direction that you yourself introduced. These posts are based on what happens to have caught my attention, but should not be interpreted as a careful judgment of what is interesting and what is not. I hope that everything I include is interesting, but the converse is completely false.