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 is a union-closed family on a ground set , and , then we can take the family . The map is a homomorphism (in the sense that , so it makes sense to regard as a quotient of .

#### Subfamilies

If instead we take an equivalence relation on , we can define a set-system to be the set of all unions of equivalence classes that belong to .

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

#### Products

Possibly the most obvious product construction of two families and is to make their ground sets disjoint and then to take . (This is the special case with disjoint ground sets of the construction that Tom Eccles discussed earlier.)

Note that we could define this product slightly differently by saying that it consists of all pairs with the “union” operation . This gives an algebraic system called a join semilattice, and it is isomorphic in an obvious sense to with ordinary unions. Looked at this way, it is not so obvious how one should define abundances, because does not have a ground set. Of course, we can define them via the isomorphism to 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 be a union-closed family of sets (the “base” of the system). For each let be a union-closed family (one of the “fibres”), and let the elements of consist of pairs with . We would like to define a join operation on by

for a suitable . For that we need a bit more structure, in the form of homomorphisms whenever . These should satisfy the obvious composition rule .

With that structure in place, we can take to be , 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 and then a random , then the average abundance of 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 be a large integer and let be disjoint sets of size and . (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

.

To see that this is a counterexample, let us pick our random element 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 , then its abundance is 2/3. If it is in , then its abundance is 1/2. If it is in , then the probability that it is in is , 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 , and ). In this kind of way we get that for large enough we can make the average abundance as close as we like to

.

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 , let be the minimum abundance of any element of . Then the average of over is at least 1/2.

How can we convert the average over into the minimum over ? The answer is simple: take the original set system 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 times, the third times, and so on. For very large , the effect of this is that if we choose a random element of (after the duplications have taken place) then it will have minimal abundance in .

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 by first picking a random non-empty , then a random such that , and finally a random element ? And could we go further — e.g., picking a random chain of the form , 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 to be and to be , we would prove FUNC for if we could find an injection from to .

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 for which there does not exist any with a union-preserving injection from to . After several failed attempts, I found the following example. Take a not too small pair of positive integers — it looks as though works. Then take a Steiner -system — that is, a collection of sets of size 5 such that each set of size 3 is contained in exactly one set from . (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 , though it is more convenient just to take and prove that there is no intersection-preserving injection from to . To establish this, one first proves that any such injection would have to take sets of size to sets of size , which is basically because you need room for all the subsets of size of a set to map to distinct subsets of the image of . 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 , all -subsets of , and the 6 sets , , , , , . 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.

February 8, 2016 at 12:25 pm |

I’m going to pursue for a little bit the idea I floated in the post above about iterating the method that led to the average-overlap-density conjecture that we now know is false.

So this is a new proposal for an averaging argument. In a way it’s a sort of cheating method for producing a conjecture that’s hard to disprove, since it looks as though it will lead to difficult calculations. (Unfortunately, I think this may also make it hard to prove if by a miracle it’s true.) In a separate comment, I’ll see whether I can check it for an example that isn’t too tiny.

To specify the averaging argument, I just need to specify the probability distribution I put on the ground set , or equivalently a procedure for choosing an element randomly from . My procedure can be defined inductively as follows. I’ll always assume that my set systems contain the empty set, though I’m not sure that will be terribly important.

If consists of just two sets and , then we simply pick uniformly.

Now let be the union-closed family. Pick a random non-empty set and pass to the family , where I count sets with multiplicity: that is, if , then I count those as distinct sets. (More formally, I am taking a multifamily, which is a multiset of sets.)

This means that I must go back and redo the base case: if all the sets in the multifamily are either or , then we choose uniformly. The reason I want to consider multiplicities is that it seems more natural to do so when we are concerned with abundances: we want to favour elements contained in lots of sets, so if some of those sets get identified when we intersect them with , then we don’t want to penalize them.

At this point I can just say that I inductively apply my procedure to the multifamily .

However, we can describe the process more explicitly as follows. If consists just of and , then I choose uniformly from . Otherwise, I choose a random set that is not equal to or . If is either disjoint from, or contained in, every element of , then I choose a random element of . Otherwise, I pick a random set such that lies strictly between and and call it . I continue this process until I reach a set that cannot be divided further, and then I choose a random element from it.

Note that this process yields a distribution that will give the same average abundance if elements of the original ground set are duplicated, which is a good sign.

February 8, 2016 at 4:58 pm

While difficult to calculate exactly, this is easy to code up and just sampling it a few thousand times, to give a pretty good estimate of what the expectation is.

In particular, I tried plugging in every concrete counterexample we have so far, and the average abundancy was always at least 0.5, so this conjecture is looking good so far.

One small observation is that in a couple of cases I tried by hand (and in fact also in your example below) some elements never get chosen.

Is it possible to give a description of generating, for some union-closed family, a ‘derived’ union-closed family consisting of just the elements which occurred with positive probability in the original family, which has the same probability distribution (or at least, same in expectation) on the abundancies?

Maybe a suitably robust procedure would be a way to try proving this – from a starting family, generate a new family on which the distribution from this procedure was ‘flatter’, and repeat, until the distribution was behaving uniformly.

Actually, that’s another question: if give you a union-closed family and tell you that this procedure just produces the uniform distribution on all elements, can you deduce FUNC for this family?

February 8, 2016 at 6:03 pm

As far as your first question is concerned, a start would be to characterize the elements that don’t get chosen. I’m not sure how easy this is, but let me attempt it. Let me call a set system

non-trivialif it contains a set other than and the ground set.Then an obvious situation where an element is not chosen is if is non trivial and the only set in that contains is the ground set . Such elements will be ruled out in the “first round”.

Suppose now that we pick as our first random choice. Then if is non-trivial, there may be elements of that are at this point guaranteed not to be chosen because they do not belong to any (with ) other than itself.

However, such an element may be chosen if we don’t begin by choosing .

Actually, I’m not sure if that’s true. The assumption I’m making about is that and for every , either or . But that means that for as long as is in play, so are all the other elements of . So at some point we’ll get rid of .

That’s useful, as it means there is now a fairly simple definition of points that are guaranteed for “second-level” reasons not to be included. These are points for which there exists such that every that contains contains the whole of .

And of course we can take things a stage further. Suppose , , there exists such that is non-empty and properly contained in . Suppose also that every that contains contains . Then cannot be chosen.

It’s beginning to look as though the right definition is something like this. Suppose that every set in that contains also contains , but some set that contains does not contain . Then cannot be chosen. That looks as though it is going to be the condition.

February 8, 2016 at 6:08 pm

Let me try to do the check. Say that if every set that contains contains . Then is reflexive and transitive. If but , then during the choosing procedure we can never eliminate without eliminating , but we can always eliminate without eliminating , so eventually we will.

Conversely, we may suppose WLOG that is the only such that and . But then at each stage of the process it is possible to choose a set that includes and not some other point in the set we’ve got down to so far.

February 8, 2016 at 8:17 pm

I’m now wondering whether it is possible to work out the probability distribution as follows. Given and , I’d like to work out the conditional probability of choosing given that we choose either or . Obviously if I can do that for an arbitrary pair then I’ve got the whole distribution.

I

thinkthis conditional probability may be quite easy to work out, as follows. Suppose that at a certain point we have got down to a set (which will be an intersection of some of the sets in ) that contains both and . We will then pass to a set by choosing a random set amongst those that have a proper intersection with . But we could equally achieve this by pickinganyrandom set, ignoring it if it is disjoint from or contains , and repeating until we first get a proper intersection . If this set contains one of and but not the other, then we are finished. If it contains both, we continue. If it contains neither, then we are part of the probability space where we don’t end up with either or .In this last situation, discard any set if it contains neither nor .

The result is a kind of race: we choose a random sequence of sets and we stop when we first reach a set that contains exactly one of and . I think the probability we are looking for is the probability that it contains .

But then the ratio of the probabilities is simply the ratio of the number of sets that contain but not to the number of sets that contain but not .

Something that bothers me about this is that I don’t see why the necessary consistency conditions should hold — that is, if we write for the probability of ending up at divided by the probability of ending up at , then we must have . But then the above argument seems to imply that, writing for ,

.

But that doesn’t seem to have any reason to be true, so it leaves me worried about the correctness of the argument.

February 8, 2016 at 11:55 pm

I’ve understood my mistake. If we’re given that we choose either or , then that is going to skew the distribution on the sequence of sets. Suppose, for example, that the first set we choose contains but not . Then it’s true that if we go on to choose one of and , then it must be that we choose, but our probability of doing that depends on .

So I’m back to thinking that the probability distribution is probably quite hard to work out.

February 9, 2016 at 12:35 am

And now I’ve understood the mistake more clearly. Suppose that is contained in five very large sets that don’t contain , and is contained in just one small set that doesn’t contain . Then if we are told that one of and has been chosen, we can be pretty sure it’s , since if ever we choose a set that contains and not , it is very unlikely that we’ll actually end up choosing .

February 8, 2016 at 12:34 pm |

Now I want to try to calculate the average abundance for the set system that Alex came up with. I’ll do it case by case.

Suppose the first set I pick is . Then my final is 1. Similarly if the first set I pick is then my final is 2. If the first set I pick is , then the multiset I get, when the empty set and are excluded, is

so I will pick with probability 2/3 and with probability 1/3.

If the first set I pick is , then the multiset I get is

so I pick with probability 1.

And that’s it, since is the entire ground set.

OK, that wasn’t as bad as I feared. I end up choosing with probability

and therefore with probability 1/3.

Since 1 has abundance 2/3 and 2 has abundance 1/2, that certainly gives an average abundance of more than 1/2 — in fact, we get 11/18. It’s also somewhat encouraging that the weights this process has given to the elements of are greater, the greater the abundance of the elements themselves. (Of course, that will be lost if we duplicate, but only for inessential reasons.)

February 8, 2016 at 5:01 pm |

This follows naturally from my comment above, but is unrelated to that conjecture, so I thought I’d ask it separately. It’s also probably trivial and I’m missing something.

If you have a union-closed family such that every element has the same abundancy, can you deduce FUNC in this case?

February 8, 2016 at 5:30 pm

I don’t see a trivial argument for this, and I’m not sure it’s known even if you assume that the automorphisms of the family act transitively on the ground set.

February 9, 2016 at 7:38 am |

Inspired by Tim’s 6:08pm comment involving implications, let me try to propose another way of equipping with a probability distribution as a candidate for an averaging argument.

As discussed at FUNC1 [1], every union-closed family can be characterized in terms of a bunch of Horn clauses, by which I mean the following: there are families of elements such that contains precisely those that satisfy the implications

for all .

Now the idea is to use these implications to define a random walk (Markov chain) on . Suppose that you’re walking around on and you try to follow the ‘arrows’ formed by these implications. So whenever you’re at a left-hand side at some point in time, you should follow the arrow and randomly choose one of the on the right-hand side to move to. In case that your current position in is the left-hand side of several implications, then you choose randomly between the different possibilities. (We can assume wlog that every occurs as some left-hand side, because otherwise such a is abundant for trivial reasons.) In this way, your random walk defines the transition map of a Markov chain on .

The best-case scenario would be that any stationary distribution of this Markov chain has an average abundance of . The intuition that makes this sound somewhat plausible is as follows. There are two relevant factors that make an element likely to be abundant:

1) It occurs on many right-hand sides.

2) The right-hand sides in which it occurs are small.

Now the Markov chain is designed precisely in such a way that a stationary distributions should roughly assign high probability to elements with these properties.

[1] https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154161

February 9, 2016 at 7:58 am

Oh no: I forgot the ‘s on the right-hand side of the implication, it should have been

.

An appealing property of the Markov chain is that it behaves well under duplication: duplicating some to and results in transition probabilities that are equal to the original transition probabilities , except in that for all . To see this, start with the original system of implications, and replace every occurrence of on a right-hand side by . For every on a left-hand side, duplicate the implication once with and once with . Finally, throw in an additional and . This new system of implications characterizes the new union-closed families with a duplicated point. It’s easy to see that the transition probabilities must be as I described above.

On the other hand, it should also be mentioned that the system of implications that characterize a given union-closed family is far from unique, and the Markov chain that I’m proposing will probably depend on the choice. Maybe there’s a unique minimal choice, but I’m not sure.

February 9, 2016 at 8:01 am

This looks interesting — as I hinted in an earlier post (or perhaps comment), I was trying to find something along these lines, by which I mean a natural random walk such that one could use its stationary distribution as a candidate for an averaging argument. So I’m very pleased to see this suggestion. I also very much like duality arguments when it comes to convex bodies, so I will think about this Horn-clause formulation and try to understand it properly.

One small detail is that in your earlier comment you have disjunctions on the right-hand side of your Horn clauses, whereas in your comment above you appear to have conjunctions. Is that just a small slip here? (If so, I can easily edit your comment to correct it.)

February 9, 2016 at 8:02 am

Ah, you’ve answered my question before I even asked it! I’ll go ahead and edit the first comment.

February 9, 2016 at 12:43 pm

Thanks!

I should add that I’ve intentionally omitted some technical subtleties in my earlier comments in order to keep them reasonably concise. For example, what I called a ‘Horn clause’ is properly called a ‘definite dual-Horn clause’. I hope that this isn’t too confusing…

Let me try to work out a set of Horn clauses that characterize Thomas’s example:

plus cyclic;

and plus symmetric.

The first set of clauses excludes the singleton subsets of , while the second set implements the indexing of the 2-subsets of by . Unfortunately, this is not quite right yet, since this collection of clauses also excludes the set , which is part of Thomas’s example.

So here’s an improved attempt:

plus cyclic;

, where and , plus symmetric.

So there are clauses with a on the left-hand side. These ensure that if , then also or .

It might be useful to have a computer program to check whether this system indeed works. But for now, let me assume that it is correct. The associated Markov chain results in something very nice: the set of points is closed, i.e. the Markov chain will never leave this set once it enters. Together with symmetry, this implies that the stationary distribution is unique and assigns a probability of 1/4 to each of and vanishes on the other elements. So in this case, the stationary distribution is completely supported on abundant elements!

In fact, the same happens for the basic examples 1-3 in the main post of FUNC1. So, here’s a very bold strengthening of the conjecture:

Conjecture: any stationary distribution of the Markov chain is supported on abundant elements.In other words, does following the arrows of the Horn clauses in a non-deterministic manner

alwayseventually result in a sequence of abundant elements?As some of the earlier conjectures, this sounds too good to be true…

February 9, 2016 at 3:10 pm

Formulated slightly differently, that ridiculous conjecture claims in particular: if the Markov chain is irreducible, then

allelements are abundant.An appealing feature of the universal quantifier ‘

allelements’ is that it makes the statement much more amenable to an inductive proof: if the Markov chain of a given is irreducible, then it’s enough to show that both Markov chains of and are, for arbitrary , in order to complete the induction step.February 9, 2016 at 8:00 pm

I’m trying to gauge the chances of getting such an inductive proof to work.

Suppose that is such that all of its nontrivial quotients and nontrivial subfamilies (as in the main post) have the property that all elements of their respective ground sets are abundant. Does this imply that every element of the ground set of is abundant in ?

If so, this would prove the “ridiculous conjecture” in the case where the Markov chain is irreducible, since one can choose the system of Horn clauses for the quotients and subfamilies in such a way that the irreducibility is preserved.

February 10, 2016 at 9:47 am

“It might be useful to have a computer program to check whether this system indeed works.”

As a sanity check, to see whether I understand your idea let me first give an example.

When I input and and on my program generates .

If that is roughly what the program should do, there should be no problem to check your Horn clauses for Thomas’s example. I just need to understand properly what you mean be “symmetric”. Could you please elaborate?

February 10, 2016 at 10:21 am

Cool! Yes, that’s exactly what the program’s output should be.

The Horn clauses for Thomas’s example are hypothetically the following:

plus all the ones of the following form:

,

where ranges over , ranges over , and ranges over the 2-element subset of that corresponds to , so for example for . (Recall that each indexes exactly one 2-subset of .) Does this clarify things?

February 10, 2016 at 1:55 pm

That works. Impressive. I get a set with 120 elements (empty set included). The generators are in it and the frequencies are as Thomas describes 100 for 7 to 10 and 52 for 1 to 6.

February 10, 2016 at 2:17 pm

That’s reassuring to know. Thank you!

By the way, would you be willing to share your code? I might want to run some more computer experiments tomorrow.

February 10, 2016 at 3:11 pm

I use Mathematica. Its is a two line program. Let me explain it with the smaller example I posted before.

Generate the powerset with

A = Subsets[{1,2,3,4}]

Select sets from the powerset by connecting the clauses with “And[…] &”. The ampersand is important to indicate that this is a function you want to apply. Any clause is applied as .

S = Select[A,

And[

Or[Not[MemberQ[#,4]],MemberQ[#,3]],

Or[Not[MemberQ[#,3]],MemberQ[#,1]],

Or[Not[MemberQ[#,3]],MemberQ[#,2]]

]

&]

To get Thomas’s example just generate the powerset on 10 elements and do a 1 minute copy paste orgy to get the 64 clauses. I hope that helps.

February 9, 2016 at 10:53 am |

The conclusion “the averaging method can never yield the union-closed sets conjecture in its full generality” on p. 22 of the survey is based on the non–separating Hungarian family example and is therefore not completely convincing, since according to p. 4 of the survey “it suffices to prove the conjecture for separating families”.

Are there separating examples with small average?

February 9, 2016 at 11:55 am

Isn’t the construction at the bottom of the same page supposed to be exactly such an example?

February 9, 2016 at 2:58 pm

The example is supposed to be separating. The authors claim it without proof.

However,

for all we have that is contained in exactly one set. This set also contains . Hence is not separating.

E.g. for we can take and and get

February 9, 2016 at 3:04 pm

There is a member set which contains , but not , and that’s enough to separate these two elements. (Cf. the definition of separating on p.2, “for any two elements there exists a member-set containing exactly one of them”.)

February 9, 2016 at 4:41 pm

Ah ok. Thank a lot.

February 9, 2016 at 12:49 pm |

Regarding injections from the sets without to the sets with . We can hope to find such an injection that always take a set to a set containing it. I wonder what is the status of this hope (do we have counterexample? or know that this follows from FUNC?)

February 9, 2016 at 5:09 pm

I like this question, and I think we should make some efforts to find a counterexample. A natural place to start looking would be the examples that disproved the existence of union-preserving injections.

Now that I’ve said that I feel a moral obligation to think about the -Steiner systems example. Taking complements, your question becomes, for this example, the following. Let be a Steiner -system with ground set together with all subsets of of size at most . Does there necessarily exist an injection from some to such that each set contains its image?

Let be a set of size that contains . Then under such a map it will have to go to a subset of itself of size at most that does not contain . Also, the sets of size containing will have to go to subsets of themselves when .

Let’s deal with the small sets first. The set is forced to go to . Then any set is forced (by injectivity) to go to . By induction, any set of size at most that contains is forced to go to . It follows that the sets of size containing must all map to sets of size exactly .

How many sets in of size contain ? Well, every set of size that contains is contained in exactly one such set, and every set of size containing contains -sets that contain . So it looks as though we have sets of size in that contain . We need an injection from that to the sets of size that do not contain .

Unfortunately, that is not ruled out on cardinality grounds. So can we use the additional hypothesis that each set contains its image to obtain a contradiction? I’m not sure we can. In fact, maybe some Hall-type argument would show that the injection does in fact exist.

February 10, 2016 at 2:32 pm

This conjecture has withstood my attempts so far to find a counterexample by generating random families.

February 10, 2016 at 7:35 pm

I briefly wondered if it might even be true that every abundant element admits such an injection. Unsurprisingly it isn’t, though it seems one needs four elements in the ground set to construct a counterexample. One such family is: , where the element gives a counterexample.

February 9, 2016 at 5:47 pm |

In this comment I want to think aloud, so to speak, as I try to understand Tobias Fritz’s Horn-clause formulation of FUNC.

First of all, let’s make the well-known observation that any monotone family of sets (meaning that if and then ) can be expressed in disjunctive normal form as something like

.

Each clause is saying that for , and then the big “or” is saying that at least one of those statements must hold. So to express in this form, we just create a clause for each minimal set in and then we end up with all sets containing one of those minimal sets.

To get a general set system one allows negation. Then one can simply list all the sets and write down a clause for each one, saying which elements belong to it and which do not.

Now Tobias’s thought, as I understand it, is to find something a bit like the monotone disjunctive normal form above for union-closed families — that is, nicer than a fully general disjunctive normal form because of the union-closed property. We can’t let it be monotone, because there are union-closed families that are not monotone, but we can try to make it special in some way.

The way he came up with is to use Horn clauses, that is, clauses of the form

.

This time we take a big

conjunction. That is, our set system consists of all sets that satisfy a bunch of conditions of the form.

Let’s check that if and satsify the condition above, then so does . It’s trivial, since if , then either or , and in both cases we get that all the belong to .

How can we represent a union-closed family in this way? An obvious way, which is guaranteed to work if anything does, is to take

allHorn clauses that are satisfied by every set in . We end up needing to prove a separation theorem: that for every there exists a Horn clause not satisfied by that is satisfied by every .This comment is getting long and I don’t yet see how the proof goes. (I could look it up in Tobias’s file that he links to, but I’d like to have a go at it first.) So I’ll stop here and start writing a new comment.

February 9, 2016 at 5:51 pm

OK, I have a union-closed family and a set . I want to find some and a set disjoint from such that for every that contains , . Clearly I make things better for myself if I make larger, so I may as well take to be .

So now I want such that no that contains is a subset of . But if I can’t do that, then for every I can find a subset that contains . And then the union of those is , so , a contradiction.

February 9, 2016 at 5:55 pm

Yes, that’s spot-on. One of the subtleties that I’ve swept under the rug so far is that the union-closed families which one can represent in this way are precisely those that contain the empty set. I’m a bit confused at the moment about where you’ve actually used the necessary assumption 😉

February 9, 2016 at 6:06 pm

I don’t know whether I made essential use of it when I proved that I could find such that …

Suppose that consists of all sets other than the empty set. Then any non-trivial Horn clause

rules out the singleton . So the only allowable clauses are trivial, and therefore don’t rule out the empty set.

February 9, 2016 at 6:09 pm

Or perhaps I was implicitly including the empty union as a union, so that union-closed sets contain by definition.

February 9, 2016 at 6:15 pm

Ah, yes, for the final part of your proof will write as the empty union! So this is a contradiction only if .

The way that I think about all this is that union-closed families are analogues of convex polytopes, while union-closed families that also contain the empty set are analogues of convex (polyhedral) cones. A Horn clause is the analogue of a linear inequality bounding the cone, and the separation theorem is analogous to Farkas’s lemma (or Hahn-Banach). One can make this analogy more precise by working over the Boolean semiring , where addition is and multiplication is . Writing down the obvious notions of convex cone, linear inequality etc results in the concepts above. (A linear inequality may have several terms on the left-hand side, but it turns out to be equivalent to a system of linear inequalities with only one term on each left-hand side.)

BTW, I haven’t performed a careful literature search on this since I haven’t had any plans to publish it (so far). So it may well be that this correspondence between union-closed families and systems of Horn clauses has been discovered previously.

February 9, 2016 at 6:16 pm |

Let me try to check Tobias’s “ridiculous conjecture” on one of Alec’s examples. The example is the one where you have a set of size , an element not in , and you take together with all subsets of that contain . For this example, all elements of have abundance less than 1/2, while has abundance close to 1.

What would be a Horn-clause definition of the system? It looks like being given by all clauses with . But then the stationary distribution does indeed just contain . So the conjecture survives this example.

February 9, 2016 at 7:17 pm

In general, one has to think what precisely Tobias’s “ridiculous conjecture” should be. Do we want to say that

anyHorn-clause specification of should work, or do we want to pick a particular one? If the latter, then the only natural candidate I can see at the moment is the maximal one that can be thought of as all pairs such that and every set in that contains has a non-empty intersection with .Actually, it would also be natural to insist that is minimal with this property. By the way, to convert into a Horn clause I go for

,

where are the elements of .

So now the random walk is defined as follows. Take all such pairs (the ones with minimal ). If you’re at , pick a random from all the pairs in your collection and then move to a random element of . Is it the case that you will eventually end up only ever visiting elements of abundance at least 1/2?

It feels to me as though a counterexample should be something like a set system constructed as follows. Take some random generating sets, but “bias” them a bit towards small numbers. For example, choose each element with probability if it’s at most and if it’s at least . Then I would hope that the elements in the second half would have abundance less than 1/2, but that the Horn-clause walk wouldn’t be confined to the first half. But this may be complete nonsense.

February 9, 2016 at 7:18 pm

Of course, even if the ridiculous conjecture fails, that still leaves the very interesting and non-ridiculous conjecture that an averaging argument works for the stationary distribution.

February 10, 2016 at 9:48 am

“all pairs such that and every set in that contains has a non-empty intersection with [..and..] insist that is minimal with this property.”

That reminds me of the proof of Theorem 13 in the survey (Knill’s unconditional lower bound ), which uses a set that intersects every member of and is minimal with this property. Coincidence?

February 9, 2016 at 11:34 pm |

I want to try out an idea for disproving the ridiculous conjecture. (I’ll leave out the inverted commas, which doesn’t mean that I think that the conjecture is genuinely ridiculous — unlikely, yes, but very much worth thinking about.)

A good way of creating a union-closed set system with a random walk of some character one wants is probably to choose the Horn clauses first and let those define the set system. So let , where and are of equal size and disjoint. Then for each I want to take a Horn clause of the form (for some parameter that I will choose later) and for each I want to take a Horn clause of the form . I’ll choose these Horn clauses randomly. (Of course, the belong to and the to .)

My hope is that if , then the resulting set system will be biased in one of and , with the result that half the elements will have abundance less than 1/2, but also that the Markov chain will be irreducible. The second part looks OK, but the first is more worrying.

It looks as though the sets in come from cycles in the directed bipartite graph I’ve just defined. Let’s define , the neighbourhood of , to be the set of points in that are implied by , and similarly the other way round. Then if , so must some neighbour of be, and a neighbour of that, and so on, and this cannot end until we have … ah, maybe not quite a cycle. A minimal set in is I think a path such that has a neighbour amongst . So it’s like a cycle with a little tail on it that is directed towards the cycle. Ah, except that is not minimal, since if we cut off the tail, then we still have a set that satisfies the condition.

Note that I am in a very special situation here where each vertex is on the left of precisely one of the Horn clauses. In general, it may be on the left of several of them. So my description of the minimal sets is not one that applies to all union-closed systems.

Unfortunately, my hope that there would be a bias towards one half looks rather unlikely to be fulfilled, since these cycles visit each half the same amount.

So let me change the model. This time for each vertex in I choose neighbours randomly from , but for each vertex in I choose neighbours randomly from . So now there is a tendency for cycles to spend more time in than in . So the generating sets ought to look fairly random but with elements chosen with higher probability in than in .

I don’t see an easy way to guess what happens to abundances in this system, or what the best parameters should be. At a guess, we should probably take to be pretty large — proportional to , say — so that the cycles will tend to close off quickly, which will make the generating sets small, which will give the system a reasonable chance of the elements of having abundance less than 1/2.

Perhaps we can be a bit more brutal about this. What happens if we have a bijection and we join each to everything in , and each to everything in ? Then the minimal sets are, I think, pairs of elements of and also sets of the form . So it looks as though consists of sets such that , , , and .

I have to stop now, but it feels as though this might be an example where the elements of have abundance less than 1/2, and yet the Horn clauses define a random walk that is irreducible. But I’m not confident of this, as I’ve not checked things very carefully and felt rather unsure of what I was writing. A suitable set of Horn clauses seems to be for each and implies everything other than for each .

February 10, 2016 at 9:43 am

I think that looks good, especially the last example involving , although we’d need to have a proof that the abundance of the elements of is really less than 1/2. I’ve tried to work this out explicitly for sets of cardinality two, which turns out to be too small, and the for cardinality three, as follows. Let and , with being the bijection that just adds the prime. Then the Horn clauses are:

plus cyclic,

plus cyclic.

Going through each of the 2^6 candidate sets modulo symmetry by hand, this results in

,

where I’m really listing representatives of symmetry classes, and the exponent indicates the cardinality of each class. Assuming that this is correct, the abundances are: 28/45 for , and 24/45 for … I’ve done a couple of cross-checks now and this seems to be the correct count. So either cardinality 3 is still too small, or the counterexample doesn’t work…

February 10, 2016 at 10:31 am

Let me try to attack it the other way round. So let be a bijection and let consist of all sets such that .

Then if , the number of sets in this system is (since for any sequence in we can let the 1s represent elements of and the 2s represent elements of in an obvious way).

If , then how many of these sets contain ? We are fixing a certain coordinate to be 1 in the correspondence above, so the answer is a proportion 1/3. Similarly, all the elements of have abundance 2/3.

Now we have to work out what the natural Horn-clause representation is, and see whether the resulting random walk is irreducible. The one condition I can see is that if belongs to a set, then so does . That leaves a small problem, which is that I don’t know how the random walk is defined if I’m at a vertex and there is no Horn clause with that vertex on the left-hand side.

One natural convention would be to say that we also have all Horn clauses of the form

,

where are the elements of . This is in other words a “trivial” Horn clause that says that if is in a set, then that set is non-empty.

But actually, why did I go for that rather than an alternative trivial Horn clause

?

In the first case I’ll get an irreducible Markov chain and in the second I’ll get one that ends up in .

To try to bypass these problems, let’s change the original set system so that now I take pairs such that and . The only sets I’ve removed from the previous system are sets of the form and sets of the form (oh, and I keep the empty set). So the abundances are hardly changed when is large, as these sets form an exponentially small fraction of the total.

So now I know that if belongs to one of my sets, then so does … aargh, some other element of , which is still not enough.

OK, I had better insist also that is non-empty. The abundances are still hardly changed. Now I think a suitable set of Horn clauses will consist of the clauses and the clauses (with the convention I was using earlier — this means that if is in the set, then so is at least one element of ) and .

Or to make things simpler I could take all pairs such that and . Now the clauses would be and . The second set of clauses tells us that if a set is non-empty, then it must contain an element of .

I think this is an example of a set system where the Horn-clause random walk is irreducible, and the elements of have abundance approximately 1/3 and the elements of have abundance approximately 2/3.

But as always I’m waiting for silly mistakes to be pointed out to me.

February 10, 2016 at 11:23 am

“The second set of clauses tells us that if a set is non-empty, then it must contain an element of Y.”

Ah, that does the trick! Without the additional condition (when ), that system would be isomorphic to the -fold product of with itself, but imposing the additional condition makes these copies interact nicely. I suspect that the system of Horn clauses that you wrote down for this example even coincides with your earlier suggestion of taking all where ranges over all minimal transversals of .

Maybe the general lesson is that adding a single Horn clause with a large right-hand side will typically affect the abundances only marginally, but may dramatically improve the recurrence properties of the random walk.

I guess that this kills all reasonable interpretations of the ridiculous conjecture, involving either an arbitrary or a “natural” choice of the system of Horn clauses for given . D’oh.

On a different note:

“I don’t know how the random walk is defined if I’m at a vertex and there is no Horn clause with that vertex on the left-hand side.”

If that happens, then that vertex is automatically abundant. Hence we can assume wlog that it doesn’t happen.

February 10, 2016 at 11:44 am

An annoying feature of this example is that the random walk alternates between and , so the stationary distribution is uniform, whereas one would prefer it to be biased towards .

February 10, 2016 at 4:38 pm

Good point. Nevertheless, I’d like to compute the average abundance in that example to see whether it also finishes off the random walk’s stationary distribution as a candidate for an averaging argument.

The entire set system has many elements. An element of occurs in many sets, while an element of occurs in simply many sets.

Therefore the expected absolute abundance is . Multiplying by two gives , which is still (barely!) larger than . Hence this doesn’t yet exclude an averaging argument based on the stationary distribution of the random walk.

February 10, 2016 at 6:13 pm

I agree that it makes sense to check the average abundance statement as well. To find a counterexample, we would somehow like a stationary distribution that favours less abundant elements.

One way to try to achieve that is, I think, to observe that the following two sets of clauses have very different effects on the set system but the same effect on the random walk. The first is just a single clause of the form

.

The second is clauses

, .

Because it is much harder to satisfy all the clauses in the second set, it should make less abundant.

So now the idea would be to have two sets and , and for each we have two random clauses of the form , . (For the sake of analysing the random walk, let’s also assume that each belongs to precisely two of these clauses.) On the other side, for each I have a single random clause of the form .

The random walk will visit and equally often, since it always alternates between and . What I hope now is that we can contradict the conjecture by making a bit bigger than , since it looks to me as though elements of should have lower abundance, because their conditions are harder to satisfy.

To check this, I need to try to understand what the sets are in . This may be easier to do experimentally, but I’ll have a try.

Actually, I think I may have an easier example. I’ll try again.

February 10, 2016 at 11:13 pm

I’m now getting a bit worried by your claim that your random-walk suggestion behaves well when you duplicate. It’s a slightly technical problem that bothers me, but a problem nevertheless.

Suppose we do as you say and when we duplicate to become and we split up all the implications in the natural way and also add the implications and . Then this changes the stationary distribution, because effectively it is adding in a non-zero probability of staying put at in the random walk.

The reason I thought of this is the following example. Let be the ground set, where is a copy of . Then let consist of all sets where , is the copy of in and for some (fixed in advance) bijection . This is the previous example but with elements of duplicated. Also add in the empty set.

But now the Horn clauses will be , , , , and . So for the random walk, points in are equally likely to go to or , points in are equally likely to go to or , and points in are equally likely to go to or .

The number of sets is still approximately , since all we’ve done is duplicate . So the abundances in and are about 1/3 and the abundances in are about 2/3, which means that the average abundance for the stationary distribution is about .

This example feels like a slight cheat, but I think it may be possible to modify it to produce one that doesn’t rely on duplication to the same extent.

February 11, 2016 at 7:20 am

Good point, and apologies for the false claim. Back to the drawing board.

February 13, 2016 at 8:42 am

A small curiosity of this random walk is that it’s closely related to Google’s PageRank algorithm: the elements correspond to the web pages, and a Horn clause is the list of all the web pages that links to. PageRank then computes the stationary distribution of the walk, possibly mixed with random noise: there may be an additional probability to “teleport” to a webpage uniformly chosen at random at every step.

When ignoring the additional random noise, this is exactly my proposed random walk in the special case that there are no two different Horn clauses with the same left-hand side.

Source: PageRank beyond the Web, http://arxiv.org/abs/1407.5107v1

February 10, 2016 at 11:54 am |

Since the example towards the end of this comment has caused problems for one conjecture, maybe it will do so for another, the idea outlined in this comment. What distribution do we get if we apply the procedure from the second comment just mentioned to the example in the first comment?

We will pick a random sequence such that the intersections

strictly decrease, until it is no longer possible for them to decrease without becoming empty. Since for each , we always have a set with when we run this process. Therefore, we cannot get stuck at a set with non-empty, since for such a set there would always be the possibility of intersecting it with . So it looks to me as though the distribution we get is uniform on . So this conjecture is still alive.

February 10, 2016 at 1:15 pm |

I was thinking about counterexamples to the second weighted version from FUNC1. The reason it should fail is that, thinking in terms of indicator functions of sets, the “weight-respecting union” is not a lattice operation. In particular, you can add large weights to elements low in the lattice without this weight propagating to higher elements. The game is to choose the low down elements carefully to simultaneously avoid all of the extra weight being on a few elements, and the extra weight propagating too far up. I played around with a few examples last night without getting anywhere, but here’s a trivial observation: as stated the second weighted version is clearly false as you can put an arbitrarily high weight on the empty set.

February 10, 2016 at 2:01 pm

Ah, I hadn’t spotted that. I thought that the fact that would make it OK, but of course it just shows that , which is not that interesting.

So it’s beginning to look as though finding a suitable weighted version will be difficult.

February 10, 2016 at 2:09 pm

Yes, I started out trying to show that the weighted version was equivalent to the usual version, which led to me trying other possible weighted versions when that didn’t work out. To me the weighted side is screaming for arbitrary non-negative functions rather than multiples of indicators of sets, but I have no good way of describing the size of one of these objects; on the set side we have lucky coincidences like .

February 10, 2016 at 2:22 pm

In the Polymath spirit I should probably say what it was that I tried. To show that the uniform measure and arbitrary measure versions are the same you can make points “wider” by duplicating them. So perhaps we can simulate weights on the sets by making them “taller”. More precisely, suppose that all of the weights are integers from to . Duplicate each point of the ground set $N$ times and replace the set of weight by the sets for all . Unfortunately the resulting family is not union-closed: for that to be true you would need the operation on weights to be the genuine supremum of functions, not our funny definition involving minimum weights.

February 10, 2016 at 3:59 pm

Here’s a possible approach to defining families with integer weights. First observe that if is a union-closed family with ground set , and , then we naturally get a multifamily of subsets of : the weight attached to a subset is the number of such that .

If we forget the weights, then this family is union closed (indeed, it is the quotient family as described in the post above). What can we say about it if we don’t forget the weights?

It is not completely easy to say. For example, let and let consist of all sets such that and . Then if , the weights of and are , while the weight of is and the weight of is .

It may seem odd that FUNC is wildly false for this weighted set system, but that is because the elements with large abundance in are not or .

I find it discouraging that a weighted set system that occurs in nature, so to speak, should not (as far as I can tell) have nice properties.

February 11, 2016 at 12:36 pm

Actually looking at that construction of weights further can lead us to significant improvements of Knill’s unconditional lower bound (Theorem 13 in the survey). If I’m not totally off base, then the argument still leaves a lot of maneuvering room.

As in Knill’s proof, consider a minimal transversal . As explained in the previous comment, there is an associated weight function , and we want to find such that the total weight of the -containing sets is a high fraction of the overall weight . Knill’s original argument is like this: if every had a total weight of less than , then it wouldn’t be possible to cover all of , which has a total weight of , where the negative term is . Since , it follows that there is some of total weight at least .

This argument is suboptimal: the worst-case scenario that it assumes is that the weight is completely concentrated on the singletons. This doesn’t happen in the case at hand, since every nonempty has a weight . This is good because every that is not a singleton will contribute its weight to more than one element of .

So how can we improve the argument? What I’ve tried so far is just to use that everywhere. Using a worst-case analysis analogous to the above, I’ve found that this implies that some must have a total weight of at least

where is somewhere between and . It’s encouraging that at these two extreme values, the resulting lower bound is precisely . However, my numerics indicate that for fixed , there is a unique minimum of this bound as a function of , and the value of this minimum seems asymptotically at most a constant factor away from Knill’s bound . So this is not a really big improvement yet.

Is there more that we can say about weight functions arising from quotienting along for minimal transversals $S$?

February 11, 2016 at 12:43 pm

Minor correction: the two extreme values resulting in should have been and . For , we get , which is a tight bound as well.

February 11, 2016 at 12:50 pm

So if anyone is good at special functions and their asymptotics: minimize the expression as a function of . How does the value of the minimum scale as ? Does it grow faster than ? If it doesn’t differ by more than a constant factor, is it possible to say what this constant is?

February 11, 2016 at 1:54 pm

Numerically, the constant appears to be one, so no asymptotic gain.

February 11, 2016 at 2:48 pm

That’s good to know, thank you!

For another potential improvement, we could also try to choose the minimal transversal in some clever way, but I don’t have any ideas along these lines.

February 12, 2016 at 4:49 pm

I was wondering yesterday what can be said about weight functions arising from quotienting along for minimal transversals , besides the fact that everywhere. Based on a straightforward variation on Tim’s example, I now know: for the purposes of strengthening Knill’s argument, the answer is “nothing”.

More precisely, I claim that there are union-closed with a minimal transversal such that the induced weight function on realizes my worst-case scenario, which is that for all non-singleton , and is independent of and arbitrarily large.

The construction goes like this: fix and take , where the are disjoint copies of a -set. Take to consist of all that satisfy the following implication for every : if , then also for all . The crucial point here is that is a minimal transversal of , and for every there are sets that satisfy . However, the union of any two such sets for different contains all the ‘s. Hence the induced weight function on is if is a singleton, and otherwise. This is the worst-case scenario in the sense that my bound is tight, i.e. it reproduces the exact abundance of the elements of .

So the only further room that I can see for potential strengthening of Knill’s argument is to make a clever choice of . In the above example, take e.g. a minimal transversal that contains one element in each : all elements of such a transversal have abundance close to 1. (Of course, a clever enough choice of will always work if FUNC holds, since one can just choose to contain an element of maximal abundance…)

February 10, 2016 at 3:02 pm |

Other commenters have already thought along these lines (I’m thinking in particular of this comment of Tom Eccles and the ensuing discussion, and also this comment of Tobias Fritz and the one after it), but I think it would be good to try to pin down as exactly as possible what would be required for an averaging argument to work with an inductive proof.

Let me try first to say what I mean by “an averaging argument”. I mean that for each union-closed family on a ground set , one should define a probability distribution on , and then one should prove that for every union-closed family the -average abundance of an element is at least 1/2. Ideally I would also like the construction of the probability distribution to have the property that if an element is duplicated times, becoming , then each has a probability in the new distribution, so that in particular the average abundance is unchanged. (It is easy to achieve this condition by simply identifying equivalence classes of points and then using probability distributions defined for separating families, but I would prefer a definition that depends naturally on in such a way that this kind of device is not necessary.)

Suppose we have such a definition. What could a proof conceivably look like? If we are going for an inductive proof, what would the inductive hypothesis look like?

The obvious one is simply that the conjecture is true for all smaller union-closed families. Writing and for the probability distributions associated with and we could then assume that a -random element of is contained in at least half the elements of and a -random element of is contained in at least half the elements of .

But that seems a bit problematic: if we have tailored our distributions so that they favour abundant elements, then may favour a completely different set of elements from .

To give an extreme example, suppose that is uniformly distributed over all elements with maximum abundance in . Then it might be that is concentrated at and is concentrated at . Even if has abundance greater than 1/2 in and has abundance greater than 1/2 in , we cannot then deduce that some element has abundance greater than 1/2 in .

The problem here seems to be that is not related in a reasonable way to and .

Another problem, which is essentially the one that Tom Eccles was worrying about, is that we have to be careful not to throw away essential information when we split our set system into and . They cannot be just an arbitrary pair of set systems: if and , then we know that .

Conversely, if and are union-closed set systems such that belongs to every element of and no element of , and if in addition (to use Tom Eccles’s notation again), then is a union-closed set system.

I should probably modify what I’ve just written so that is defined to be so that it is not the case that has abundance 1 in .

Either way, it seems that we have to use all three conditions , and in order to obtain some interesting relationship between and .

This comment is getting long, so I’ll finish it. But the next question I was planning to think about is whether there is some nice condition one can put on and that would allow the largeness of the average to follow from the largeness of the and averages?

February 10, 2016 at 9:48 pm

It might be fruitful to look for a hard example for this kind of induction argument. In particular, it would be interesting to have an example of a union-closed family , and an element such that:

1) is not abundant in

2) No element is abundant in both and .

3) Both and contain a non-empty set (just to exclude some silly examples).

February 10, 2016 at 10:28 pm

I wonder whether an example I was thinking about in a different comment would work for this. Let with those three sets disjoint and with and of the same size . Let consist of all sets that are either empty, or contain , or do not contain and contain all of . The number of sets in this set system is . The element belongs to of the sets, so is not abundant. Oh, this doesn’t work, since has size , and every element of belongs to every set in , and every element of belongs to half the sets in .

February 10, 2016 at 10:39 pm

In connection with your question, let me make a ludicrous conjecture for someone to disprove. It may have a very easy counterexample, because my attempts to find one amount to about 30 seconds of thought without a piece of paper.

Say that if . That is, if and , then . Then if and both set systems are union closed, there exists an element that has abundance at least 1/2 in both systems.

The connection (just to spell it out) is that if is any union-closed system and belongs to its ground set, then .

The fact that you ask for condition 1 suggests that you may already know that this is false.

February 10, 2016 at 10:56 pm

Yes, we do need condition 1. We know that there is a union closed family containing a three-set such that no element of is abundant in . Take be the family with only that three-set; then .

February 10, 2016 at 11:38 pm

Thanks. But it’s interesting if we need a counterexample of that level of sophistication. It suggests that finding an example of the kind you ask for will not be straightforward, which, given its clear relevance to the conjecture, makes it a very interesting problem.

February 11, 2016 at 7:42 am

I was actually thinking of it as a simple counterexample! My first couple of attempts failed for simple reasons – can’t have a 1-set or a 2-set. Once I realised that, re-using this example seemed natural.

Anyway, I’m going to rephrase my example as a conjecture using your language to remove the rather unnecessary reference to , and also add a weaker version I still can’t find a counterexample to.

Conjecture 1: If and are union-closed, with and , then there is an element which is abundant in both and .

Conjecture 2: Under the same conditions, every abundant element of is abundant in .

February 11, 2016 at 7:50 am

I was worried that that remark of mine would seem strange. To clarify, it’s simple modulo the result you use, but that result is not that easy to prove if you start from scratch.

February 11, 2016 at 9:19 am

I still don’t understand why we need condition 1 in the original formulation (or rather, why we know it’s false without it). Are you saying that the Renaud–Sarvate family contains an abundant element that satisfies conditions 2 and 3?

February 11, 2016 at 9:25 am

Not quite; I had switched to the new notation when presenting that counterexample.

In the first formulation, the family would be:

,

where is the Renaud-Sarvate family, and is the special 3-set in that family with no abundant element.

February 11, 2016 at 9:44 am

Aha, thanks.

February 10, 2016 at 4:43 pm |

Let’s consider my inductive method of constructing probability distributions, and look at how it does on the following set system. The ground set is divided into two equal-sized subsets and . We have some element , and we take all sets with the following properties:

(i) if , then ;

(ii) if , then or .

As we choose our random sequence with their properly nested intersections, we cannot end up at , since at each stage if is included then so is the rest of . So .

The set system consists of sets that contain , so it is isomorphic to the power set of . Furthermore, any sequence will have to end up at the set (or if we define the other way). So is uniform on (or ). Similarly, the set system always gives rise to a sequence that ends at , so is uniform on .

I’m not really sure where this is going.

February 10, 2016 at 5:38 pm |

We now know that it is false that:

There exists and such that is an injection from .

How about the following (in particular, does the Steiner-based example disprove this also?)

There exists and a map from such that is an injection from .

(I don’t think this particular conjecture has been suggested before, but apologies if it has/is trivially equivalent and I’ve missed it).

February 10, 2016 at 5:48 pm

Interesting! If this is true, then since , we get in particular a positive answer to the question whether there is an injection with : https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154298

Conversely, suppose that such an exists. Then we can just put , and get , and we get a positive answer to your question.

Hence your question is equivalent to Gil’s, although of course I might have been misunderstanding something.

February 10, 2016 at 6:22 pm

If it is indeed equivalent to Gil’s (and Tobias’s argument looks convincing at a first glance), then I managed to persuade myself that the Steiner construction doesn’t disprove it.

February 10, 2016 at 8:09 pm

Oops, I misremembered. I tried to prove that the Steiner construction gave a counterexample, and couldn’t do it with a completely straightforward argument, and began to get the feeling that there was such an injection, but failed to prove that properly.

February 10, 2016 at 9:40 pm |

The paper “Recursive definition of the lattice of

Moore families” by Labernia and Raynaud might be relevant / interesting. I haven’t had the time to read it in detail yet.

February 11, 2016 at 7:58 am |

Unlike most people who’ve worked on it, I’ve never really been convinced by the truth of FUNC. Would someone who thinks it is very likely to be true like to explain why?

February 11, 2016 at 11:12 am

Implicit in your question above is a strategic one. I imagine that people participating actively in this discussion would like to maximize the chances of solving the problem in a short time. With that end in mind, are we focusing too much on proof ideas and not enough on ideas for constructing counterexamples?

I don’t know what I think about this. It also makes me think of something Gil Kalai once wrote, possibly in a blog comment — I’d be very pleased to have an exact reference — which was that there is no difference between looking for a proof and looking for a counterexample. I agree strongly with the point he is making, namely that whether or not you believe in a statement, in order to find out whether it is true you basically need (or very often need) to do the same sort of iterative process of trying to prove it, getting stuck, trying to turn that stuckness into a counterexample, getting stuck, trying to turn that stuckness into a proof, and so on until if you are lucky the process converges.

In another sense there obviously

isa difference, in that there are two distinct parts to that iterative process — the looking-for-proof parts and the looking-for-counterexample parts. So the question remains of whether we should try to come up with proposals for methods of creating counterexamples.One vague thought I have had, and I don’t think I’m alone in this, is that it might be possible to do something like creating an example where only a few elements have abundance greater than 1/2 (which we know we can do), and then somehow creating out of that example a new example where we reduce the abundances of those few elements, probably adding some new elements in the process. The difficulty with such approaches seems to be that in reducing the abundance of some elements, the constructions one can think of seem to introduce new elements with large abundances.

February 11, 2016 at 11:37 pm

As well as that strategic question, I think intuitions about why FUNC would be true would be a) interesting and b) potentially useful. If there are reasons to believe FUNC, beyond the lack of a counterexample, perhaps those reasons contain the seed of a proof.

I do also wonder whether more focus on the looking-for-a-counterexample side of things would be sensible. However, it seems very hard to even find a promising direction on that.

But let’s get the ball rolling – here is an attempted counterexample to FUNC.

Let the groundset be , all of equal size. For each , let be a subset of , taken randomly of size . We generate our union-closed family with all sets that contain some , and avoid the corresponding .

These generators are constrained on elements of . Any union of two or more of these generators is constrained on about elements of . So, picking small and then large, almost all the sets in our family are generators. Also, the generators have average size less than – because they exclude slightly more elements than they include.

So, the average size of our sets is small, and the scheme doesn’t favour any particular element of . That’s promising. The problem is that the don’t cover anything like twice – so some (in fact most) elements of are only in a single . It looks very much like those elements are going to be the abundant ones.

February 12, 2016 at 8:13 am

The idea of that attempt was to find a family of sets which were fairly small, and whose unions generated many fewer sets than . The final property I needed, which didn’t come out on this attempt, was that has each element around equally often. But I’m still interested in this direction – I don’t yet see why such a construction is doomed.

February 12, 2016 at 8:55 am

Something like that thought was behind the failed attempt of mine that I presented in the post that one might think of as FUNC0. I wondered whether a random family of -sets with for some a little less than 1/2 might do the job, because a typical union of such sets will have size close to and there are far fewer such sets than there are sets of size . While the detailed estimates didn’t work out, I had the same feeling as you that I couldn’t see any fundamental reason for a counterexample with this general flavour being impossible.

February 11, 2016 at 11:32 am |

Influenced by Tobias Fritz’s random-walk idea I have thought of another way of using a set system to create a probability distribution on the ground set. It is pretty simple, and I think it behaves well under duplication.

The idea is this. Let be a set system and let be its ground set. Define a random walk on as follows. If you are at , then pick a random set that contains and move to a random element of . Then the distribution associated with is the stationary distribution of this random walk.

Let be a point in , and let us duplicate it.

OK I’m completely wrong, and it’s obvious that duplication has a massive effect. (For example, if you duplicate a billion times, then you are hugely more likely to end up at a copy of whenever you choose some set that contains in the original system.) In the Polymath spirit I will post this non-thought anyway, in case the idea can be rescued somehow.

February 11, 2016 at 12:29 pm |

While I was implementing the software for the Horn clauses I was wondering whether we should think about how to make the search for a counterexample accessible to a math SAT solver.

February 12, 2016 at 8:14 am |

Here is a way to construct arbitrarily large families with a regular distribution of abundances. For example, it can generate for any a family of size with a ground set of size such that half the elements have abundance and half have abundance .

Let . (In the example above, .) Let be a set of size . To construct our family we take as the ground set, and then we take to consist of all sets where ranges over all functions .

The function is injective. Furthermore, (where is defined pointwise). So is a union-closed family of size . It is separating and contains the empty set (corresponding to the function ).

The relative abundance of an element depends only on : it is .

February 12, 2016 at 9:09 am

I’m trying to get my head round this, and may as well share my attempt. To do it, I’ll reformulate the example — not because the way I reformulate it is better, but just because by doing the exercise of reformulating it, I hope I’ll end up understanding it.

So instead of taking , I’ll take it to be a disjoint union of copies of a set of size . (This isn’t a significant reformulation of course — maybe redescription would be a better word.)

Given a function , the sets are nested downwards. Conversely, given any nested sequence of sets I can find an that gives rise to them. So the sets in are, in this description, sets of the form where each is a subset of (or more formally of the copy of ) and . I see now why you chose your description — it was to avoid the informality of saying things like that when in reality they are disjoint, or defining an ugly set of bijections.

Be that as it may, with this description it’s obvious that is union closed. Also, since elements of are in a natural one-to-one correspondence with sequences of length that take values in , we get the abundances.

February 12, 2016 at 10:13 am

That example is isomorphic to the -fold product of the total order with itself, isn’t it? The component of a set at is just , which is a member of .

Here’s a generalization of this construction, which is more conveniently formulated for intersection-closed families. Let be an arbitrary function between finite sets such that every fibre carries the structure of a meet-semilattice. It helps to have a ‘bundle’ picture in mind with as the base space and the total space. Then the idea is to let vary over all ‘partial sections’ of , i.e. functions defined on a subset such that . The set associated to such a section is . The intersection of this with an arising from is .

[I hope that it’s clear how this generalizes your example; if not, let me know.]

I think that all of this should be an instance of the fibre bundle construction from the main post, probably by taking and to be the product of the fibres , but I need to think about this a little bit more.

February 12, 2016 at 10:18 am

Perhaps a more intuitive way to think of this family is , somwhat abusing notation, each being actually a subset of the th ‘copy’ of .

February 12, 2016 at 10:27 am

Ah, I hadn’t seen Tim’s comment above, which says the same thing. 🙂

February 12, 2016 at 10:07 am |

Because of Tom Eccles’s recent comment I was musing about possible counterexamples, and came up with a question that I find interesting, though it probably won’t be hugely helpful for FUNC.

I wondered whether perhaps one could create a counterexample by taking as the ground set of the set of pairs from some set , so that its elements can be thought of as edges in graphs. Then would be a union-closed set of graphs. When looking for sets of graphs, it is natural to look for

graph properties— that is, sets that are invariant under permutation of the vertices. Thus, the hope would be to find a union-closed graph property that is for some reason easier for small graphs to satisfy than for large graphs.There are two classes of properties that come up most often. One is

monotoneproperties — that is, ones where if has it and , then has it. Typical examples are “is connected” or “contains a triangle”. For our purposes, these are useless, since every element that occurs at all in a monotone set system occurs with abundance at least 1/2. The other ishereditaryproperties, which are properties such that if is aninducedsubgraph of and has the property, then has the property. A simple example is “contains an induced cycle of length 5”.The question I was going to ask is whether there are any natural graph properties that are union closed but not monotone. Hereditary properties look promising at first, but at least the example above clearly doesn’t work. We can create a graph with an induced 5-cycle by taking five vertices and putting all edges into except the pairs with mod 5. Taking two such graphs with disjoint sets of five vertices, their union will be the complete graph on vertices, which does not contain an induced 5-cycle.

As I said at the beginning, I don’t expect this question to lead magically to a counterexample to FUNC, but it might give us some insight into what union-closed families can look like.

Maybe we can answer the question by thinking about Horn clauses. The fact that we are talking about a graph property will imply that the Horn-clause description will have a lot of symmetries. Looking at it the other way, perhaps considering sets of Horn clauses with the necessary symmetries will lead to interesting union-closed graph properties.

February 12, 2016 at 10:45 am

Let me spell out what the constraints on the Horn clauses would have to be.

Suppose we have a clause of the form

.

The edges form a graph , and the symmetry of the property we are defining tells us that if is any permutation of the edges that is induced by a permutation of the vertices, then we will also get the clause

.

For example, suppose were the edges , so they made a graph that consisted of a triangle with an edge attached to it. This clause would tell us that if belongs to the graph, then so does at least one of the edges in the attached triangle. But by symmetry that tells us that if

anyedge belongs to the graph, then so does at least one edge from every triangle that overlaps with that edge in precisely one vertex.That’s a slightly peculiar property, but it is probably already an example of a union-closed property that isn’t monotone.

Actually, I think it

ismonotone. If the graph has at least one edge, then there can be at most one isolated vertex, since otherwise if is an edge and and are isolated vertices, then the triple fails to contain an edge. But then every triple of vertices contains at least one edge, since it must include one non-isolated vertex . If is not already joined to or , then it is joined to some other , from which it follows that is an edge. But that shows that the property above is equivalent to the property of intersecting all triangles, which is a monotone property.However, it gives a clue about how to construct non-monotone union-closed properties. Here’s one that seems to work: every edge is contained in a triangle. A triangle has the property, the property is clearly union-closed (after all, a union of unions of triangles is a union of triangles), but a triangle together with one more edge does not have the property.

February 12, 2016 at 10:54 am

A small remark here is that the property “every edge is contained in a triangle” does not have a nice Horn-clause description. If is an edge, then we require some such that both and belong to . This is most naturally expressed as

If instead we put it into conjunctive normal form, we end up saying that for every function that takes vertices other than and to either or , we must satisfy

.

So we get an exponential number of Horn clauses for each edge.

February 12, 2016 at 10:59 am

Here’s very vaguely why one might be ready to fantasize that something like this could lead to a counterexample. We would try to identify a property of the form “If contains the edge then it must satisfy some other -related constraint.” The constraint will typically be easier to solve for bigger graphs, which is bad news, but the bigger the graph, the more edges that it has to be satisfied for, which is good news. Could the good news outweigh the bad news?

February 12, 2016 at 6:32 pm

These graphs are very nice examples of union-closed families. Expanding on “every edge must be in a triangle”, the simplest classes are “every edge is in a graph H”, where the edge may have to be a particular edge in H.

Is FUNC true for these union-closed families? For triangles, it looks very likely – nearly all graphs with many edges have every edge in a triangle, and many small graphs don’t. In fact, for any fixed H and a large vertex set, that looks true. So I think to have any chance of finding a counterexample, we would need to look at graphs H which aren’t that much smaller than the vertex set.

February 12, 2016 at 11:13 pm

One can generalize the construction as follows. Let’s define a graph-edge property to be a subset of the set of all graphs that is invariant under all symmetries that fix a given edge . If is such a property, write for the statement that satisfies the property when is the preferred edge. (An example of such a property is “ is contained in a cycle with length a multiple of 5″.)

If is any

monotonegraph-edge property, then we can form a union-closed property by taking all graphs such that for every edge . To give a non-trivial example, we could take to be the property “There are disjoint paths of length connecting the two end points of “. Then the union-closed property would be that this is true for every edge , which is clearly not a monotone property but is certainly union closed.I think it would be an interesting partial result if we could prove FUNC for such properties, or properties of the specific form “ is contained in a subgraph isomorphic to “, or even some weakening of FUNC that is better than is known for general union-closed families. It seems hard to find a counterexample, because as you say one probably needs to look at quite large graphs , but large graphs have many edges and so contribute quite a bit to abundances.

To get round that last problem, it might perhaps help to look at a variant that somehow makes it harder for large graphs. An idea I wondered about was taking a sparse random graph and just looking at subgraphs of . Then perhaps one could have a property like “Every edge is contained in a cycle.” The cycles would have to be quite long.

But actually I don’t really see what would make this work. Basically this set system would consist of unions of cycles in , and I’m not sure why there would be few large ones. (But I still think it would be worth checking, even if not rigorously, that this is not a counterexample.)

February 12, 2016 at 11:12 am |

In the polymath spirit, here’s my own take on the search for a counterexample, based on the fibre bundle construction from the main post. Since this construction most naturally lives in the world of lattices, I’ll formulate my considerations for the lattice formulation of FUNC. (Also, I frequently have the impression that working with a ground set can obscure the essential structures.) So far, it’s not very concrete at all…

The goal is to create a finite lattice in which every join-irreducible element is abundant, i.e. the upper set that it generates must contain at least half the lattice elements. In this sense, all the join-irreducibles must be sufficiently far ‘down’ in the lattice; but there should also be sufficiently many join-irreducibles to express every other element as a join of these. (For if one couldn’t, then some other element would be join-irreducible.) This is the challenging tradeoff that one has to achieve.

In order to realize this with the fibre bundle construction, one could try to take to be a power set , and choose the bundle data such that all join-irreducibles of the resulting lattice live over small subsets of . Achieving the required abundance of these join-irreducibles means that for of size , one should strive to make very large. But it also can’t be too large, since every one of its element still needs to be a join of the join-irreducibles further down, and there are only so many possibilities for combining join-irreducibles.

It should help to work out the details of this tradeoff more quantitatively, but I haven’t done so yet.

February 12, 2016 at 11:22 am

This is probably a very elementary confusion, but I don’t understand why you want every join-irreducible element to be abundant, rather than wanting

nojoin-irreducible elements to be abundant.February 12, 2016 at 11:28 am

That’s because the lattice formulation (p.5 in the survey) is an abstract restatement of the intersection-closed families version of FUNC, which asks whether every intersection-closed family has a rare element. Since the join-irreducibles correspond to the elements, I’m trying to make all the join-irreducibles strictly abundant.

February 12, 2016 at 12:15 pm

To persist with my elementary confusion, if the lattice happens to be, say, the power set of a finite set with the usual lattice operations, then aren’t the join-irreducible elements the singletons? I understood the definition to be that you can’t write your element in a non-trivial way as a join of two other elements.

Ah, I see what’s going on now. So the assumption on the lattice is that it is closed under taking meets.

February 12, 2016 at 1:08 pm

Right, it’s a meet-semilattice to start out with. Now note that every finite meet-semilattice is automatically a lattice: the least upper bound of any two lattice elements is the meet of the set of all elements that are above both. (This may be an empty meet, so I’m including the existence of a top element in the definition of meet-semilattice.)

February 12, 2016 at 11:20 am |

Of course, in any bipartite graph with bipartition (A, B), the family of traces (in A, say) of incusionwise minimal vertex covers in that bipartite graph forms a union closed (and often non-monotene) family.