FUNC2 — more examples

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

Standard “algebraic” constructions

Quotients

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

Subfamilies

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

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

Products

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

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

More “twisted” products

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

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

More specific constructions

Giving more weight to less abundant elements

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

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

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

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

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

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

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

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

Complements of designs

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

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

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

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

An example of Thomas Bloom

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

Conclusion

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

104 Responses to “FUNC2 — more examples”

  1. gowers Says:

    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 X, or equivalently a procedure for choosing an element randomly from X. 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 \mathcal A consists of just two sets \emptyset and X, then we simply pick x\in X uniformly.

    Now let \mathcal A be the union-closed family. Pick a random non-empty set A\in\mathcal A and pass to the family \mathcal A_A=\{A\cap B:B\in\mathcal A\}, where I count sets with multiplicity: that is, if A\cap B=A\cap B', 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 X or \emptyset, then we choose x\in X 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 A, then we don’t want to penalize them.

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

    However, we can describe the process more explicitly as follows. If \mathcal A consists just of \emptyset and X, then I choose x uniformly from X. Otherwise, I choose a random set A_1\in\mathcal A that is not equal to \emptyset or X. If A_1 is either disjoint from, or contained in, every element of \mathcal A, then I choose a random element of A_1. Otherwise, I pick a random set A\in\mathcal A such that A\cap A_1 lies strictly between \emptyset and A_1 and call it A_2. I continue this process until I reach a set A_k 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.

    • Thomas Bloom Says:

      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?

    • gowers Says:

      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-trivial if it contains a set other than \emptyset and the ground set.

      Then an obvious situation where an element x is not chosen is if \mathcal A is non trivial and the only set in \mathcal A that contains x is the ground set X. Such elements will be ruled out in the “first round”.

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

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

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

      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 x for which there exists A\in\mathcal A such that every B\in\mathcal A that contains x contains the whole of A.

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

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

    • gowers Says:

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

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

    • gowers Says:

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

      I think this conditional probability may be quite easy to work out, as follows. Suppose that at a certain point we have got down to a set Y (which will be an intersection of some of the sets in \mathcal A) that contains both x and y. We will then pass to a set Z by choosing a random set amongst those that have a proper intersection with Y. But we could equally achieve this by picking any random set, ignoring it if it is disjoint from Y or contains Y, and repeating until we first get a proper intersection Z. If this set contains one of x and y 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 x or y.

      In this last situation, discard any set if it contains neither x nor y.

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

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

      Something that bothers me about this is that I don’t see why the necessary consistency conditions should hold — that is, if we write r_{xy} for the probability of ending up at x divided by the probability of ending up at y, then we must have r_{xy}r_{yz}=r_{xz}. But then the above argument seems to imply that, writing A_{x,y} for |\mathcal A_x\setminus\mathcal A_y|,

      (A_{x,y}/A_{y,x})(A_{y,z}/A_{z,y})=A_{x,z}/A_{z,x}.

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

    • gowers Says:

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

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

    • gowers Says:

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

  2. gowers Says:

    Now I want to try to calculate the average abundance for the set system \{\emptyset, \{1\},\{2\},\{1,2\},\{1,3\},\{1,2,3\}\} that Alex came up with. I’ll do it case by case.

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

    \{\{1\},\{2\},\{1\}\}

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

    If the first set I pick is \{1,3\}, then the multiset I get is

    \{\{1\},\{1\}\}

    so I pick x=1 with probability 1.

    And that’s it, since \{1,2,3\} is the entire ground set.

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

    \frac 14(1+0+\frac 23 + 1)=2/3

    and therefore x=2 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 X are greater, the greater the abundance of the elements themselves. (Of course, that will be lost if we duplicate, but only for inessential reasons.)

  3. Thomas Bloom Says:

    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?

    • gowers Says:

      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.

  4. Tobias Fritz Says:

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

    As discussed at FUNC1 [1], every union-closed family \mathcal{A}\subseteq 2^X can be characterized in terms of a bunch of Horn clauses, by which I mean the following: there are families of elements x_i,y_{ij}\in X such that \mathcal{A} contains precisely those A\subseteq X that satisfy the implications
    x_i\in A\:\Rightarrow\: y_{i1}\in A\vee\ldots\vee y_{ik_i}\in A
    for all i=1,\ldots,m.

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

    The best-case scenario would be that any stationary distribution of this Markov chain has an average abundance of \leq 1/2. 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

    • Tobias Fritz Says:

      Oh no: I forgot the \lor‘s on the right-hand side of the implication, it should have been
      x_i\in A\:\Rightarrow\: y_{i1}\in A\lor\ldots\lor y_{ik_i}\in A.

      An appealing property of the Markov chain is that it behaves well under duplication: duplicating some u\in X to v_1 and v_2 results in transition probabilities P' that are equal to the original transition probabilities P, except in that P'(v_1|x) = P'(v_2|x) = P(u|x)/2 for all x. To see this, start with the original system of implications, and replace every occurrence of u on a right-hand side by v_1\lor v_2. For every u on a left-hand side, duplicate the implication once with v_1 and once with v_2. Finally, throw in an additional v_1\Rightarrow v_2 and v_2\Rightarrow v_1. This new system of implications characterizes the new union-closed families with a duplicated point. It’s easy to see that the transition probabilities P' 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.

    • gowers Says:

      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.)

    • gowers Says:

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

    • Tobias Fritz Says:

      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:

      7 \:\Rightarrow\: 8\lor 9\lor 10 plus cyclic;
      1 \:\Rightarrow\: 7 and 1\:\Rightarrow\: 8 plus symmetric.

      The first set of clauses excludes the singleton subsets of \{7,8,9,10\}, while the second set implements the indexing of the 2-subsets of \{7,8,9,10\} by \{1,\ldots,6\}. Unfortunately, this is not quite right yet, since this collection of clauses also excludes the set \{1,\ldots,6\}, which is part of Thomas’s example.

      So here’s an improved attempt:

      7 \:\Rightarrow\: 8\lor 9\lor 10 plus cyclic;
      1 \:\Rightarrow\: x\lor y, where x\in\{2,\ldots,6\} and y\in\{7,8\}, plus symmetric.

      So there are 5*2 = 10 clauses with a 1 on the left-hand side. These ensure that if 1\in A, then also 7,8\in A or 2,\ldots,5\in A.

      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 \{7,8,9,10\} 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 \{7,8,9,10\} 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 always eventually result in a sequence of abundant elements?

      As some of the earlier conjectures, this sounds too good to be true…

    • Tobias Fritz Says:

      Formulated slightly differently, that ridiculous conjecture claims in particular: if the Markov chain is irreducible, then all elements are abundant.

      An appealing feature of the universal quantifier ‘all elements’ is that it makes the statement much more amenable to an inductive proof: if the Markov chain of a given \mathcal{A} is irreducible, then it’s enough to show that both Markov chains of \mathcal{A}_x and \mathcal{A}_{\bar{x}} are, for arbitrary x, in order to complete the induction step.

    • Tobias Fritz Says:

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

      Suppose that \mathcal{A} 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 \mathcal{A} is abundant in \mathcal{A}?

      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.

    • Uwe Stroinski Says:

      “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 4 \Rightarrow 3 and 3 \Rightarrow 1 and 3 \Rightarrow 2 on \{1,2,3,4\} my program generates \{ \emptyset,\{1\},\{2\},\{1,2\},\{1,2,3\},\{1,2,3,4\}\}.

      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?

    • Tobias Fritz Says:

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

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

      7 \:\Rightarrow\: 8\lor 9\lor 10
      8 \:\Rightarrow\: 7\lor 9\lor 10
      9 \:\Rightarrow\: 7\lor 8\lor 10
      10 \:\Rightarrow\: 7\lor 8\lor 9

      plus all the ones of the following form:

      x \:\Rightarrow\: y\lor z,

      where x ranges over \{1,\ldots,6\}, y ranges over \{1,\ldots,6\}\setminus\{x\}, and z ranges over the 2-element subset of \{7,8,9,10\} that corresponds to x, so for example z\in\{7,8\} for x=1. (Recall that each x\in\{1,\ldots,6\} indexes exactly one 2-subset of \{7,8,9,10\}.) Does this clarify things?

    • Uwe Stroinski Says:

      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.

    • Tobias Fritz Says:

      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.

    • Uwe Stroinski Says:

      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 a\Rightarrow b is applied as \neg a \vee b.

      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.

  5. Uwe Stroinski Says:

    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?

  6. Gil Kalai Says:

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

    • gowers Says:

      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 (r,s)-Steiner systems example. Taking complements, your question becomes, for this example, the following. Let \mathcal K be a Steiner (r,s)-system with ground set X together with all subsets of X of size at most s. Does there necessarily exist an injection from some \mathcal K_x to \mathcal K_{\overline x} such that each set contains its image?

      Let A\in\mathcal K be a set of size r that contains x. Then under such a map it will have to go to a subset of itself of size at most s that does not contain x. Also, the sets of size t containing x will have to go to subsets of themselves when t\leq s.

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

      How many sets in \mathcal A of size r contain x? Well, every set of size s that contains x is contained in exactly one such set, and every set of size r containing x contains \binom{r-1}{s-1} s-sets that contain x. So it looks as though we have \binom{n-1}{s-1}/\binom{r-1}{s-1} sets of size r in \mathcal K that contain x. We need an injection from that to the sets of size s that do not contain x.

      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.

    • Alec Edgington Says:

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

    • Alec Edgington Says:

      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: \{\emptyset, \{1,3\}, \{1,3,4\}, \{2,4\}, \{1,2,4\}, \{1,2,3\}, \{1,4\}, \{1,2,3,4\}\}, where the element 3 gives a counterexample.

  7. gowers Says:

    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 A\in\mathcal A and A\subset B then B\in\mathcal A) can be expressed in disjunctive normal form as something like

    \bigvee_{i=1}^m(x_{i1}\wedge\dots\wedge x_{ik_i}).

    Each clause x_{i1}\wedge\dots\wedge x_{ik_i} is saying that x_{ij}\in A for j=1,2,\dots,k_i, and then the big “or” is saying that at least one of those statements must hold. So to express \mathcal A in this form, we just create a clause for each minimal set in \mathcal A 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

    x\implies y_1\vee\dots\vee y_k.

    This time we take a big conjunction. That is, our set system \mathcal A consists of all sets A that satisfy a bunch of conditions of the form

    x\in A\implies y_1\in A\vee\dots\vee y_k\in A.

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

    How can we represent a union-closed family \mathcal A in this way? An obvious way, which is guaranteed to work if anything does, is to take all Horn clauses that are satisfied by every set in \mathcal A. We end up needing to prove a separation theorem: that for every B\notin\mathcal A there exists a Horn clause not satisfied by B that is satisfied by every A\in\mathcal A.

    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.

    • gowers Says:

      OK, I have a union-closed family \mathcal A and a set B\notin\mathcal A. I want to find some x\in B and a set C disjoint from B such that for every A\in\mathcal A that contains x, A\cap C\ne\emptyset. Clearly I make things better for myself if I make C larger, so I may as well take C to be B^c.

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

    • Tobias Fritz Says:

      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 \emptyset\in\mathcal{A}😉

    • gowers Says:

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

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

      x\implies y_1\vee\dots\vee y_k

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

    • gowers Says:

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

    • Tobias Fritz Says:

      Ah, yes, for B=\emptyset the final part of your proof will write B as the empty union! So this is a contradiction only if \emptyset\in\mathcal{A}.

      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 \mathbb{B} = \{0,1\}, where addition is \lor and multiplication is \land. 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.

  8. gowers Says:

    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 X of size m, an element z not in X, and you take \emptyset together with all subsets of X\cup\{z\} that contain z. For this example, all elements of X have abundance less than 1/2, while z has abundance close to 1.

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

    • gowers Says:

      In general, one has to think what precisely Tobias’s “ridiculous conjecture” should be. Do we want to say that any Horn-clause specification of \mathcal A 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 (x,C) such that x\notin C and every set in \mathcal A that contains x has a non-empty intersection with C.

      Actually, it would also be natural to insist that C is minimal with this property. By the way, to convert (x,C) into a Horn clause I go for

      x\implies y_1\vee\dots\vee y_k,

      where y_1,\dots,y_k are the elements of C.

      So now the random walk is defined as follows. Take all such pairs (the ones with minimal C). If you’re at x, pick a random C from all the pairs (x,C) in your collection and then move to a random element of C. 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 5/n if it’s at most n/2 and 1/n if it’s at least (n+1)/2. 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.

    • gowers Says:

      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.

    • Tobias Fritz Says:

      “all pairs (x,C) such that x\notin C and every set in \mathcal A that contains x has a non-empty intersection with C [..and..] insist that C is minimal with this property.”

      That reminds me of the proof of Theorem 13 in the survey (Knill’s unconditional lower bound \frac{n-1}{\log_2 n}), which uses a set S that intersects every member of \mathcal{A} and is minimal with this property. Coincidence?

  9. gowers Says:

    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 X=Y\cup Z, where Y and Z are of equal size and disjoint. Then for each y\in Y I want to take a Horn clause of the form y\implies z_1\vee\dots\vee z_r (for some parameter r that I will choose later) and for each z\in Z I want to take a Horn clause of the form z\implies y_1\vee\dots\vee y_s. I’ll choose these Horn clauses randomly. (Of course, the z_i belong to Z and the y_i to Y.)

    My hope is that if r<s, then the resulting set system will be biased in one of Y and Z, 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 \mathcal A come from cycles in the directed bipartite graph I’ve just defined. Let’s define N_y, the neighbourhood of y, to be the set of points in Z that are implied by y, and similarly the other way round. Then if y\in A, so must some neighbour of y 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 \mathcal A is I think a path x_1,x_2,\dots,x_m such that x_m has a neighbour amongst x_1,\dots,x_{m-1}. 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 Y I choose r neighbours randomly from Z, but for each vertex in Z I choose r neighbours randomly from Y\cup Z=X. So now there is a tendency for cycles to spend more time in Z than in Y. So the generating sets ought to look fairly random but with elements chosen with higher probability in Z than in Y.

    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 r to be pretty large — proportional to n, 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 Y having abundance less than 1/2.

    Perhaps we can be a bit more brutal about this. What happens if we have a bijection \phi:Z\to Y and we join each y\in Y to everything in Z, and each z\in Z to everything in (Z\cup\{\phi(z)\})\setminus\{z\}? Then the minimal sets are, I think, pairs of elements of Z and also sets of the form \{z,\phi(z)\}. So it looks as though \mathcal A consists of sets A\cup B such that A\subset Y, B\subset Z, |B|\geq 2, and A\subset\phi(B).

    I have to stop now, but it feels as though this might be an example where the elements of Y 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 y\implies\phi^{-1}y for each y\in Y and z implies everything other than z for each z\in Z.

    • Tobias Fritz Says:

      I think that looks good, especially the last example involving \phi, although we’d need to have a proof that the abundance of the elements of Y 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 Y=\{1',2',3'\} and Z=\{1,2,3\}, with \phi being the bijection that just adds the prime. Then the Horn clauses are:

      1'\:\Rightarrow 1\lor 2\lor 3 plus cyclic,
      1\:\Rightarrow 1'\lor 2\lor 3 plus cyclic.

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

      \mathcal{A} = \{\emptyset^1,\{1,2\}^3,\{1,1'\}^3,\{1,2,3\}^1,\{1,2,1'\}^6,\{1,2,3'\}^3,
      \{1,1',2'\}^6,\{1,2,3,1'\}^3,\{1,2,1',2'\}^3,\{1,2,1',3'\}^6,\{1,1',2',3'\}^3,
      \{1,2,3,1',2'\}^3,\{1,2,1',2',3'\}^3,\{1,2,3,1',2',3'\}^1\},

      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 1, and 24/45 for 1'… 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…

    • gowers Says:

      Let me try to attack it the other way round. So let \psi:Y\to Z be a bijection and let \mathcal A consist of all sets A\cup B such that \psi(A)\subset B.

      Then if |Y|=|Z|=m, the number of sets in this system is 3^m (since for any sequence in \{0,1,2\}^m we can let the 1s represent elements of A and the 2s represent elements of B\setminus A in an obvious way).

      If y\in Y, then how many of these sets contain y? 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 Z 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 y belongs to a set, then so does \phi(y). 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

      z\implies x_1\vee\dots\vee x_n,

      where x_1,\dots,x_n are the elements of Y\cup Z. This is in other words a “trivial” Horn clause that says that if z 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

      z\implies z?

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

      To try to bypass these problems, let’s change the original set system so that now I take pairs (A,B) such that \phi(A)\subset B and |B|\geq 2. The only sets I’ve removed from the previous system are sets of the form \{z\} and sets of the form \{y,\psi(y)\} (oh, and I keep the empty set). So the abundances are hardly changed when m is large, as these sets form an exponentially small fraction of the total.

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

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

      Or to make things simpler I could take all pairs (A,B) such that \psi(A)\subset B and A\ne\emptyset. Now the clauses would be y\implies\psi(y) and z\implies Y. The second set of clauses tells us that if a set is non-empty, then it must contain an element of Y.

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

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

    • Tobias Fritz Says:

      “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 A\neq\emptyset (when B\neq\emptyset), that system would be isomorphic to the m-fold product of \{\emptyset,\{1\},\{1,2\}\} 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 x\Rightarrow C where C ranges over all minimal transversals of \mathcal{A}_x.

      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 \mathcal{A}. 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.

    • gowers Says:

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

    • Tobias Fritz Says:

      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 3^m - (2^m-1) many elements. An element of Z occurs in 3^{m-1} + 3^{m-1} - 2^{m-1} many sets, while an element of Y occurs in simply 3^{m-1} many sets.

      Therefore the expected absolute abundance is \tfrac{1}{2}\cdot 3^m - 2^{m-2}. Multiplying by two gives 3^m - 2^{m-1}, which is still (barely!) larger than |\mathcal{A}|. Hence this doesn’t yet exclude an averaging argument based on the stationary distribution of the random walk.

    • gowers Says:

      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

      x\implies y_1\vee\dots\vee y_k.

      The second is k clauses

      x\implies y_i, i=1,2,\dots k.

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

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

      The random walk will visit Y and Z equally often, since it always alternates between Y and Z. What I hope now is that we can contradict the conjecture by making Z a bit bigger than Y, since it looks to me as though elements of Z 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 \mathcal A. 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.

    • gowers Says:

      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 u to become v_1 and v_2 we split up all the implications in the natural way and also add the implications v_1\implies v_2 and v_2\implies v_1. Then this changes the stationary distribution, because effectively it is adding in a non-zero probability of staying put at u in the random walk.

      The reason I thought of this is the following example. Let Y\cup Y'\cup Z be the ground set, where Y' is a copy of Y. Then let \mathcal A consist of all sets A\cup A'\cup B where A\ne\emptyset, A' is the copy of A in Y' and \phi(A)\subset B for some (fixed in advance) bijection \phi:A\to B. This is the previous example but with elements of Y duplicated. Also add in the empty set.

      But now the Horn clauses will be y\implies\phi(y), y'\implies\phi(y), y\implies y', y'\implies y, and z\implies Y\cup Y'. So for the random walk, points in Y are equally likely to go to Y' or Z, points in Y' are equally likely to go to Y or Z, and points in Z are equally likely to go to Y or Y'.

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

      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.

    • Tobias Fritz Says:

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

    • Tobias Fritz Says:

      A small curiosity of this random walk is that it’s closely related to Google’s PageRank algorithm: the elements x correspond to the web pages, and a Horn clause x\:\Rightarrow\: y_1\lor\ldots\lor y_k is the list of all the web pages that x 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

  10. gowers Says:

    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 (A_1,B_1),(A_2,B_2),\dots such that the intersections

    (A_1\cup B_1)\cap\dots\cap(A_r\cup B_r)

    strictly decrease, until it is no longer possible for them to decrease without becoming empty. Since \psi(A_i)\subset B_i for each i, we always have a set A\cup B with \psi(A)\subset B when we run this process. Therefore, we cannot get stuck at a set A\cup B with A non-empty, since for such a set there would always be the possibility of intersecting it with A^c\cup Z. So it looks to me as though the distribution we get is uniform on Z. So this conjecture is still alive.

  11. Ben Barber Says:

    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.

    • gowers Says:

      Ah, I hadn’t spotted that. I thought that the fact that A=A\cup\emptyset would make it OK, but of course it just shows that w(A)\geq w(A), which is not that interesting.

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

    • Ben Barber Says:

      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 1 \times 1 \times \cdots \times 1 = 1.

    • Ben Barber Says:

      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 1 to N. Duplicate each point of the ground set $N$ times and replace the set A = \{a_1, \ldots, a_k\} of weight w by the w sets \{a_1^1, \ldots, a_1^j, a_2^1, \ldots, a_{k-1}^j, a_k^1, \ldots, a_k^j\} for all 1 \leq j \leq w. 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.

    • gowers Says:

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

      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 X=\{x,y\}\cup Z\cup W and let \mathcal A consist of all sets A such that x\in A\implies Z\subset A and y\in A\implies W\subset A. Then if |Z|=|W|=m, the weights of \{x\} and \{y\} are 2^m, while the weight of \emptyset is 2^{2m} and the weight of \{x,y\} is 1.

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

      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.

    • Tobias Fritz Says:

      Actually looking at that construction of weights further can lead us to significant improvements of Knill’s unconditional lower bound \frac{n-1}{\log_2(n)} (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 S\subseteq X. As explained in the previous comment, there is an associated weight function w:2^S\to\mathbb{N}, and we want to find s\in S such that the total weight of the s-containing sets is a high fraction of the overall weight n. Knill’s original argument is like this: if every s\in S had a total weight of less than \frac{n-1}{|S|}, then it wouldn’t be possible to cover all of 2^S\setminus\{\emptyset\}, which has a total weight of n-1, where the negative term is w(\emptyset) = 1. Since |S|\leq \log_2(n), it follows that there is some s\in S of total weight at least \frac{n-1}{|S|}\geq \frac{n-1}{\log_2(n)}.

      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 T\subseteq S has a weight w(T)\geq 1. This is good because every T that is not a singleton will contribute its weight to more than one element of S.

      So how can we improve the argument? What I’ve tried so far is just to use that w\geq 1 everywhere. Using a worst-case analysis analogous to the above, I’ve found that this implies that some s\in S must have a total weight of at least
      \frac{n-2^{|S|}}{|S|} + 2^{|S|-1}
      where |S| is somewhere between 1 and \log_2(n). It’s encouraging that at these two extreme values, the resulting lower bound is precisely n/2. However, my numerics indicate that for fixed n, there is a unique minimum of this bound as a function of |S|, and the value of this minimum seems asymptotically at most a constant factor away from Knill’s bound \frac{n-1}{\log_2(n)}. So this is not a really big improvement yet.

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

    • Tobias Fritz Says:

      Minor correction: the two extreme values resulting in n/2 should have been |S|=2 and |S|=\log_2(n). For |S|=1, we get n-1, which is a tight bound as well.

    • Tobias Fritz Says:

      So if anyone is good at special functions and their asymptotics: minimize the expression \frac{n-2^{|S|}}{|S|} + 2^{|S|-1} as a function of |S|. How does the value of the minimum scale as n\to\infty? Does it grow faster than \frac{n}{\log_2(n)}? If it doesn’t differ by more than a constant factor, is it possible to say what this constant is?

    • Eckhard Says:

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

    • Tobias Fritz Says:

      That’s good to know, thank you!

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

    • Tobias Fritz Says:

      I was wondering yesterday what can be said about weight functions arising from quotienting along S\subseteq X for minimal transversals S, besides the fact that w\geq 1 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 \mathcal{A}\subseteq 2^X with a minimal transversal S\subseteq X such that the induced weight function on 2^X realizes my worst-case scenario, which is that w(T)=1 for all non-singleton T, and w(\{x\}) is independent of x and arbitrarily large.

      The construction goes like this: fix k\gg 1 and take X := S\cup \bigcup_{s\in S} Y_s, where the Y_s are disjoint copies of a k-set. Take \mathcal{A} to consist of all A\subseteq X that satisfy the following implication for every s: if s\in A, then also Y_t\subseteq A for all t\in S\setminus\{s\}. The crucial point here is that S is a minimal transversal of \mathcal{A}, and for every s there are 2^k sets A that satisfy A\cap S = \{s\}. However, the union of any two such sets for different s contains all the Y_s‘s. Hence the induced weight function on 2^S is w(T)=2^k if T is a singleton, and w(T) = 1 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 S.

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

  12. gowers Says:

    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 \mathcal A on a ground set X, one should define a probability distribution p=p_{\mathcal A} on X, and then one should prove that for every union-closed family \mathcal A the p-average abundance of an element x\in X is at least 1/2. Ideally I would also like the construction of the probability distribution to have the property that if an element x\in X is duplicated k times, becoming x_1,\dots,x_k, then each x_i has a probability p(x)/k 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 \mathcal A 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 p_x and p_{\overline x} for the probability distributions associated with \mathcal A_x and \mathcal A_{\overline x} we could then assume that a p_{x}-random element of X is contained in at least half the elements of \mathcal A_x and a p_{\overline x}-random element of X is contained in at least half the elements of \mathcal A_{\overline x}.

    But that seems a bit problematic: if we have tailored our distributions so that they favour abundant elements, then p_x may favour a completely different set of elements from p_{\overline x}.

    To give an extreme example, suppose that p_{\mathcal A} is uniformly distributed over all elements with maximum abundance in A. Then it might be that p_x is concentrated at u and p_{\overline x} is concentrated at v. Even if u has abundance greater than 1/2 in \mathcal A_x and v has abundance greater than 1/2 in \mathcal A_{\overline x}, we cannot then deduce that some element has abundance greater than 1/2 in \mathcal A.

    The problem here seems to be that p_{\mathcal A} is not related in a reasonable way to p_{\mathcal A_x} and p_{\mathcal A_{\overline x}}.

    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 \mathcal A into \mathcal A_x and \mathcal A_{\overline x}. They cannot be just an arbitrary pair of set systems: if A\in\mathcal A_x and B\in\mathcal A_{\overline x}, then we know that A\cup B\in\mathcal A_x.

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

    I should probably modify what I’ve just written so that \mathcal A_x is defined to be \{A\setminus\{x\}:A\in\mathcal A, x\in A\} so that it is not the case that x has abundance 1 in \mathcal A_x.

    Either way, it seems that we have to use all three conditions \mathcal B+\mathcal B\subset\mathcal B, \mathcal B+\mathcal C\subset\mathcal B and \mathcal C+\mathcal C\subset\mathcal C in order to obtain some interesting relationship between p_{\mathcal B} and p_{\mathcal C}.

    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 p_{\mathcal B} and p_{\mathcal C} that would allow the largeness of the p_{\mathcal A} average to follow from the largeness of the p_{\mathcal B} and p_{\mathcal C} averages?

    • Tom Eccles Says:

      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 \mathcal A, and an element x such that:

      1) x is not abundant in \mathcal A
      2) No element is abundant in both \mathcal A_x and \mathcal A_{\bar x}.
      3) Both \mathcal A_x and \mathcal A_{\bar x} contain a non-empty set (just to exclude some silly examples).

    • gowers Says:

      I wonder whether an example I was thinking about in a different comment would work for this. Let X=\{x\}\cup Y\cup Z with those three sets disjoint and with Y and Z of the same size m. Let \mathcal A consist of all sets that are either empty, or contain \{x\}\cup Y, or do not contain x and contain all of Z. The number of sets in this set system is 1+2^m+2^m. The element x belongs to 2^m of the sets, so is not abundant. Oh, this doesn’t work, since \mathcal A_x has size 2^m, and every element of Y belongs to every set in \mathcal A_x, and every element of Z belongs to half the sets in \mathcal A_x.

    • gowers Says:

      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 \mathcal A\leq\mathcal B if \mathcal A+\mathcal B\subset \mathcal B. That is, if A\in\mathcal A and B\in\mathcal B, then A\cup B\in\mathcal B. Then if \mathcal A\leq\mathcal B and both set systems are union closed, there exists an element x that has abundance at least 1/2 in both systems.

      The connection (just to spell it out) is that if \mathcal A is any union-closed system and x belongs to its ground set, then \mathcal A_{\overline x}\leq\mathcal A_x.

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

    • Tom Eccles Says:

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

    • gowers Says:

      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.

    • Tom Eccles Says:

      I was actually thinking of it as a simple counterexample! My first couple of attempts failed for simple reasons – \mathcal A 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 \mathcal A_x, and also add a weaker version I still can’t find a counterexample to.

      Conjecture 1: If \mathcal A and \mathcal B are union-closed, with \mathcal A \leq \mathcal B and |\mathcal A| > |\mathcal B|, then there is an element x which is abundant in both \mathcal A and \mathcal B.

      Conjecture 2: Under the same conditions, every abundant element of \mathcal A is abundant in \mathcal B.

    • gowers Says:

      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.

    • Alec Edgington Says:

      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?

    • Tom Eccles Says:

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

      In the first formulation, the family \mathcal A would be:

      \{\{x\} \cup B: B\in\mathcal B\} \cup \{C\},

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

    • Alec Edgington Says:

      Aha, thanks.

  13. gowers Says:

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

    (i) if y\in A, then Y\subset A;

    (ii) if y\notin A, then Z\subset A or A=\emptyset.

    As we choose our random sequence A_1,A_2,\dots with their properly nested intersections, we cannot end up at y, since at each stage if y is included then so is the rest of Y. So p(y)=0.

    The set system \mathcal A_y consists of sets that contain Y, so it is isomorphic to the power set of Z. Furthermore, any sequence will have to end up at the set Y (or Y\setminus\{y\} if we define \mathcal A_y the other way). So p_y is uniform on Y (or Y\setminus\{y\}). Similarly, the set system \mathcal A_{\overline y} always gives rise to a sequence that ends at Z, so p_{\overline y} is uniform on Z.

    I’m not really sure where this is going.

  14. Thomas Bloom Says:

    We now know that it is false that:

    There exists x and B\in \mathcal{A}_x such that A\mapsto A\cup B is an injection from \mathcal{A}_{\overline{x}}\to\mathcal{A}_x.

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

    There exists x and a map A\mapsto B from \mathcal{A}_{\overline{x}}\to\mathcal{A}_x such that A\mapsto A\cup B_A is an injection from \mathcal{A}_{\overline{x}}\to\mathcal{A}_x.

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

    • Tobias Fritz Says:

      Interesting! If this is true, then since A\subseteq A\cup B_A, we get in particular a positive answer to the question whether there is an injection f:\mathcal{A}_{\bar{x}}\to\mathcal{A}_x with f(A)\supseteq A: https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154298

      Conversely, suppose that such an f exists. Then we can just put B_A:=f(A), and get A\cup B_A = B_A = f(A), 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.

    • gowers Says:

      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.

    • gowers Says:

      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.

  15. Eckhard Says:

    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.

  16. Tom Eccles Says:

    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?

    • gowers Says:

      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 is a 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.

    • Tom Eccles Says:

      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 X= X_1\cup\dots X_k, all of equal size. For each i, let Y_i be a subset of X\setminus X_i, taken randomly of size |X_i| + \epsilon|X|. We generate our union-closed family with all sets that contain some X_i, and avoid the corresponding Y_i.

      These generators are constrained on (2/k + \epsilon)|X| elements of X. Any union of two or more of these generators is constrained on about (2/k + 1/k^2)|X| elements of X. So, picking \epsilon small and then X large, almost all the sets in our family are generators. Also, the generators have average size less than |X|/2 – 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 X. That’s promising. The problem is that the Y_i don’t cover X anything like twice – so some (in fact most) elements of X are only in a single Y_i. It looks very much like those elements are going to be the abundant ones.

    • Tom Eccles Says:

      The idea of that attempt was to find a family \mathcal F of sets which were fairly small, and whose unions generated many fewer sets than |\mathcal F|. The final property I needed, which didn’t come out on this attempt, was that \mathcal F 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.

    • gowers Says:

      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 r-sets with r=\alpha n for some \alpha a little less than 1/2 might do the job, because a typical union of such sets will have size close to 3n/4 and there are far fewer such sets than there are sets of size \alpha n. 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.

  17. gowers Says:

    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 \mathcal A be a set system and let X be its ground set. Define a random walk on X as follows. If you are at x, then pick a random set A\in\mathcal A that contains x and move to a random element y of A. Then the distribution associated with \mathcal A is the stationary distribution of this random walk.

    Let x be a point in x, 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 x a billion times, then you are hugely more likely to end up at a copy of x whenever you choose some set that contains x in the original system.) In the Polymath spirit I will post this non-thought anyway, in case the idea can be rescued somehow.

  18. Uwe Stroinski Says:

    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.

  19. Alec Edgington Says:

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

    Let k \geq 1. (In the example above, k = 2.) Let X be a set of size m. To construct our family \mathcal{A} we take Z = \{1, \ldots, k\} \times X as the ground set, and then we take \mathcal{A} to consist of all sets \{(i, x): \alpha(x) \geq i\} \subseteq Z where \alpha ranges over all functions X \to \{0, 1, \ldots, k\}.

    The function \phi(\alpha) =\{(i, x): \alpha(x) \geq i\} is injective. Furthermore, \phi(\alpha) \cup \phi(\beta) = \phi(\max(\alpha, \beta)) (where \max(\alpha, \beta) is defined pointwise). So \mathcal{A} is a union-closed family of size (k+1)^{\lvert X \rvert}. It is separating and contains the empty set (corresponding to the function \alpha(x) = 0).

    The relative abundance of an element (i, x) \in Z depends only on i: it is \frac{1}{k+1} \lvert \{ 0 \leq j \leq k : j \geq i \} \rvert = 1 - \frac{i}{k+1}.

    • gowers Says:

      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 Z=\{1,\dots,k\}\times X, I’ll take it to be a disjoint union X_1\cup\dots\cup X_k of copies of a set of size m. (This isn’t a significant reformulation of course — maybe redescription would be a better word.)

      Given a function \alpha:X\to\{0,1,\dots,k\}, the sets A_i=\{x:\alpha(x)\geq i\} are nested downwards. Conversely, given any nested sequence of sets I can find an \alpha that gives rise to them. So the sets in \mathcal A are, in this description, sets of the form A_1\cup\dots\cup A_k where each A_i is a subset of X (or more formally of the copy X_i of X) and A_1\supset\dots\supset A_k. I see now why you chose your description — it was to avoid the informality of saying things like that A_1\supset A_2 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 \mathcal A is union closed. Also, since elements of \mathcal A are in a natural one-to-one correspondence with sequences of length m that take values in \{0,1,\dots,k\}, we get the abundances.

    • Tobias Fritz Says:

      That example is isomorphic to the X-fold product of the total order \{\emptyset,\{1\},\ldots,\{1,\ldots,k\}\} with itself, isn’t it? The component of a set \{(i,x)\:|\: \alpha(x)\geq i\} at x is just \{i\:|\: \alpha(x)\geq i\}, which is a member of \{\emptyset,\{1\},\ldots,\{1,\ldots,k\}\}.

      Here’s a generalization of this construction, which is more conveniently formulated for intersection-closed families. Let p:Z\to X be an arbitrary function between finite sets such that every fibre p^{-1}(x) carries the structure of a meet-semilattice. It helps to have a ‘bundle’ picture in mind with X as the base space and Z the total space. Then the idea is to let \alpha vary over all ‘partial sections’ of p, i.e. functions \alpha:Y\to Z defined on a subset Y\subseteq X such that p\circ\alpha = 1_Y. The set associated to such a section is A = \{z\in Z\:|\: p(z)\in Y,\: z\leq\alpha(p(z))\}. The intersection of this A with an A' arising from \alpha':Y'\to Z is \{z\in Z\:|\: p(z)\in Y\cap Y',\: z\leq\alpha(p(z))\cap \alpha'(p(z))\}.

      [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 \mathcal{K}=2^X and \mathcal{A}_K to be the product of the fibres \prod_{x\in K} p^{-1}(x), but I need to think about this a little bit more.

    • Alec Edgington Says:

      Perhaps a more intuitive way to think of this family is \{ S_1 \sqcup \cdots \sqcup S_k : S_1 \subseteq \cdots \subseteq S_k \subseteq X \}, somwhat abusing notation, each S_i being actually a subset of the ith ‘copy’ of X.

    • Alec Edgington Says:

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

  20. gowers Says:

    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 \mathcal A the set of pairs from some set V, so that its elements can be thought of as edges in graphs. Then \mathcal A 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 monotone properties — that is, ones where if G_1 has it and G_1\subset G_2, then G_2 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 is hereditary properties, which are properties such that if G_1 is an induced subgraph of G_2 and has the property, then G_2 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 G with an induced 5-cycle by taking five vertices x_1,\dots,x_5 and putting all edges into G except the pairs x_ix_j with |i-j|\equiv 2 mod 5. Taking two such graphs with disjoint sets of five vertices, their union will be the complete graph on n 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.

    • gowers Says:

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

      Suppose we have a clause of the form

      e\implies e_1\vee\dots\vee e_k.

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

      \phi(e)\implies\phi(e_1)\vee\dots\vee\phi(e_k).

      For example, suppose e, e_1,e_2,e_3 were the edges xy, yz, zw, wy, so they made a graph that consisted of a triangle zyw with an edge xy attached to it. This clause would tell us that if xy 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 any edge 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 is monotone. If the graph has at least one edge, then there can be at most one isolated vertex, since otherwise if xy is an edge and z and w are isolated vertices, then the triple yzw fails to contain an edge. But then every triple xyz of vertices contains at least one edge, since it must include one non-isolated vertex x. If x is not already joined to y or z, then it is joined to some other w, from which it follows that yz 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.

    • gowers Says:

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

      \bigvee_z (xz\wedge yz)

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

      \bigvee_z z\phi(z).

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

    • gowers Says:

      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 G contains the edge e then it must satisfy some other e-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 e that it has to be satisfied for, which is good news. Could the good news outweigh the bad news?

    • Tom Eccles Says:

      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.

    • gowers Says:

      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 e. If P is such a property, write P(G,e) for the statement that G satisfies the property when e is the preferred edge. (An example of such a property is “e is contained in a cycle with length a multiple of 5″.)

      If P is any monotone graph-edge property, then we can form a union-closed property by taking all graphs G such that P(G,e) for every edge e. To give a non-trivial example, we could take P(G,e) to be the property “There are r disjoint paths of length s connecting the two end points of e“. Then the union-closed property would be that this is true for every edge e, 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 “e is contained in a subgraph isomorphic to H“, 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 H, 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 U and just looking at subgraphs of U. Then perhaps one could have a property like “Every edge e 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 U, 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.)

  21. Tobias Fritz Says:

    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 \mathcal{K} to be a power set 2^X, and choose the bundle data such that all join-irreducibles of the resulting lattice \mathcal{A} live over small subsets of X. Achieving the required abundance of these join-irreducibles means that for K\subseteq X of size > |X|/2, one should strive to make \mathcal{A}_K 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.

    • gowers Says:

      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 no join-irreducible elements to be abundant.

    • Tobias Fritz Says:

      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.

    • gowers Says:

      To persist with my elementary confusion, if the lattice happens to be, say, the power set of a finite set X 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.

    • Tobias Fritz Says:

      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.)

  22. Miroslav Chlebik Says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: