FUNC3 — further strengthenings and variants

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

A proposal for a rather complicated averaging argument

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

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

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

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

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

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

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

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

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

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

I’ll finish this section with the obvious question.

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

Describing union-closed families using Horn clauses

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

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

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

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

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

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

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

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

Generalizing the idea

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

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

Natural questions that arise

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

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

A question of Gil Kalai

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

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

Update: Alec Edgington has now found a counterexample.

A question of Tom Eccles

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

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

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


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

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

152 Responses to “FUNC3 — further strengthenings and variants”

  1. gowers Says:

    There’s a question that’s been bugging me for some time, which I haven’t asked because I haven’t managed to make it even slightly precise. But I think maybe now I can (make it slightly precise, that is, not fully so).

    Given a union-closed set system \mathcal A, I would very much like to construct a probability distribution on its ground set X in a way that respects duplication. One way of expressing this requirement is as follows. Suppose \mathcal A is a finite collection of subsets of a not necessarily finite set \mathcal X. Is there a way of constructing a probability measure on the algebra generated by \mathcal A? The advantage of phrasing the question this way is that if all we know about X is that it is some set, then there isn’t some pre-existing measure on X to distract us.

    Of course, we can build an isomorphic set system by taking the atoms of \mathcal A as its ground set and replacing each A\in\mathcal A by the set of atoms it contains. But it is far from clear that it is natural to put the uniform distribution on the atoms.

    Here’s an example of a set system that separates the points of the ground set, where the uniform measure on the ground set is clearly a silly one to take.

    Let X=Y\cup Z, where |Y|=m and m is much smaller than |Z|, which in turn is much smaller than 2^m. Let \mathcal A consist of all subsets of Y together with all sets of the form Y\cup Z\setminus\{z\} with z\in Z, and of course the set X itself.

    Each y\in Y belongs to 2^{m-1}+|Z|+1 of these sets, so has abundance slightly greater than 1/2. Each z\in Z belongs to |Z|+1 of the sets, so has abundance close to zero. Therefore, the average abundance is almost zero, but the set system separates points.

    It feels to me as though what has gone wrong here is that in some sense the set system separates the points in Y far more than it separates the points in Z. So we need to replace the qualitative notion of being separated by a much more quantitative one. For example, for each pair (x,y) we could ask not just whether there exists a set in \mathcal A that contains x and not y, but what proportion of the sets in \mathcal A have that property. With the set system above, we find that if both x and y belong to Y, then this proportion is approximately 1/4, whereas if x belongs to Z and y belongs to Y then it is approximately 1/2, and if y belongs to Z then it is close to zero. This makes it very tempting to try to associate these probabilities with transitions in a random walk that would in this case have a stationary distribution strongly concentrated in Y. But I don’t immediately see a good definition that does this. (Recall that a good definition would need to work even if we duplicated all the points in Y and Z infinitely many times.)

  2. gowers Says:

    A different vague thought I wanted to note down concerns the search for a good weighted version of FUNC. As Ben Barber has pointed out, it is hard to come up with a satisfactory weighted version, and the attempts mentioned in FUNC1 are unsatisfactory.

    One way of summarizing the difficulty is as follows. To turn a set system into a function, the obvious method is to take its characteristic function, which is a function from the power set of X to \{0,1\}. A weighted version is then most naturally thought of as a function from the power set of X to a more general set such as [0,1] or \mathbb R_+. But then even saying what a union is is difficult. It looks as though we want a pointwise binary operation \beta such that \beta(0,0)=0, \beta(0,1)=\beta(1,0)=\beta(1,1)=1, which we then apply pointwise.

    A natural candidate for this is the pointwise maximum, but then an immediate problem arises. We would expect all the things we are counting to depend continuously on the function. So how do we count abundances? To see the problem, consider the set system \{1\}, \{1,2\}, or in function terms (1,0) and (1,1). The number of distinct pointwise maxima is 2, so 1 has abundance 1 and 2 has abundance 1/2. Now replace this by the functions (1.0000001,0) and (1,1). Now there are three distinct pointwise maxima, and the abundances suddenly change. But what we clearly should be doing is somehow reflecting the fact that (1.0000001,1) is very close to (1,1).

    The answer, it seems, should be to replace counting of sets by something more to do with metric entropy — that is, the sizes of various nets of the set of all pointwise maxima. I haven’t thought about what one might do in any detail, so I’ll end this comment here.

    • gowers Says:

      Much of the above comment is incoherent because I was muddling up generalizing 01 functions on the power set with generalizing 01 functions on the ground set. I’ll try to post an improved version of the comment later.

  3. Alec Edgington Says:

    I found a symmetric 17-set family \mathcal{A} over a 5-element ground set that answers Gil’s proposed conjecture in the negative: that is, it admits no injections \phi : \mathcal{A}_{\bar{x}} \to \mathcal{A}_x such that A \subseteq \phi(A) for all A.

    Let the ground set be \mathbb{Z}_5. The family \mathcal{A} consists of all sets of the form \{x, x+1, \ldots, x+a-1\} where a \neq 1. (I interpret a=0 as defining the empty set).

    It’s easy to see that this is union-closed. To verify that it’s a counterexample, by symmetry we need only consider one value, say x = 0. Suppose we have an injection of the required form. Then the following facts are forced: (1) \{1,2,3,4\} \mapsto \{0,1,2,3,4\}; (2) \{2,3,4\} \mapsto \{2,3,4,0\}; (3) \{1,2,3\} \mapsto \{0,1,2,3\}. Finally, there is nowhere for \{2,3\} to go.

    • gowers Says:

      This nice example prompts a simple question that might be interesting. For each r<n let \mathcal A_{n,r} be the collection of all unions of intervals of length r in \mathbb{Z}_n. Equivalently, it is the collection of all sets of the form A=B+\{0,1,\dots,r-1\}. Must every element of \mathbb{Z}_n have abundance at least 1/2 in such a system?

      This example has one thing going for it that not all examples have, which is that a random set of large density will typically not belong to the system.

    • gowers Says:

      We can describe a set in \mathcal A_{n,r} up to cyclic permutations as follows. Take a sequence 0<a_1<a_2<\dots<a_{2m-1}<a_{2m}=n such that a_{2i}\geq a_{2i-1}+r for each i, and let A be the set of x such that a_{2i-1}\leq x<a_{2i} for some i.

      The question we want to answer is: is the average size of set built like this greater than n/2 or less than n/2? One might think it should be greater than n/2 because when you take one of the intervals in A it is forced to have length at least r (and in particular to be long) while when you take one of the intervals not in A it is not restricted (and so is allowed to be shorter). Unfortunately, I think this is likely to be correct. But if it is correct, proving it to be correct might be well worth trying to do rigorously. Perhaps there is even a rather neat argument that does it.

    • Alec Edgington Says:

      That’s an interesting question. I had a go at working out the answer exactly but just got a complicated sum that I couldn’t make headway with.

      A different generalization (almost) of the above construction would be: start with some graph; take its vertex set as your ground set; and form the family consisting of all connected sets of vertices with cardinality at least half that of the original graph. By choosing suitable graphs we might obtain some interesting examples.

    • Tom Eccles Says:

      The way I convinced myself these family satisfy FUNC, without rigorous proof: if we take a set in our family, we get a partition of n into an even number of parts corresponding to the lengths of the intervals, and the gaps between them. For any such partition, look at the sets of our family corresponding to it. The constraint on these sets is that all the pieces of the partition of length less than r are the lengths of non-intervals; it’s pretty clear [insert proof here] that this makes the non-intervals smaller than the intervals on average.

      It’s worth noting that this is union closed family of the more general form “all the subgraphs of a graph G such that every edge is in a subgraph isomorphic to H”, which we thought about briefly in FUNC2 – here, G is a cycle of length k, and H is a path of length r.

    • Gil Kalai Says:

      This is very nice.

      I suppose that the Z_n-invariant version of the conjecture is already interesting. We want to show that given a family of subsets of Z_n closed under rotations and unions then the average size is at least n/2. (right?)

      A different very drastic special case of FUNC is as follows: Given a family of graphs on a set of n vertices, closed under 1) isomorphism, 2) union, then the average number of edges is at least \frac 12\binom n2. Maybe this is not hard?

      Actually, maybe for union-closed families invariant under a transitive group of permutations on the ground set in general, and for the two special classes above an even stronger statement than FUNC is correct?

    • Gil Kalai Says:

      Since we now that we cannot always have A \subset \phi(A) can we at least always have a bijection with |A| < |\phi(A)|? Even weaker, do we always have an x which belong to at least half the set and that

      \sum \{|S\backslash\{x\}|:x\in S\ge\sum\{|S|:x\notin S\}.

    • gowers Says:

      Suppose that there is no size-increasing injection from \mathcal A_{\overline x} to \mathcal A_x. Define a bipartite graph by joining each A\in\mathcal A_{\overline x} to all B\in\mathcal A_x that have larger cardinality. By Hall’s condition, there must exist a subset \mathcal K of \mathcal A_{\overline x} with fewer than |\mathcal K| neighbours in this graph. Since adding a set to \mathcal K that is not smaller than all the other sets in \mathcal K does not affect the set of neighbours, we may assume that \mathcal K consists of all sets in \mathcal A_{\overline x} of at least a given size r.

      So an equivalent formulation of your new question is this. Does there exist some x such that for every r the number of sets of size at least r+1 in \mathcal A_x is at least the number of sets of size at least r in \mathcal A_{\overline x}?

      Another weakening of the question is to reverse the order of quantification. That is, can one show that for every r there exists x such that the number of sets of size at least r+1 that contain x is at least the number of sets of size at least r that do not contain x?

      Of course, if we set r=0 we just get FUNC, but the idea would be either to find a counterexample or to find a proof that uses FUNC.

    • Uwe Stroinski Says:

      Alec’s example can be described as

      x_i \Rightarrow x_{i-1} \vee x_{i_+1}

      for 0\leq i\leq 4. Which implies

      A_i \subseteq A_{i-1} \cup A_{i+1}

      and by taking complements

      A_{\overline{i-1}} \cap A_{\overline{i+1}} \subseteq A_{\overline{i}}. The intersection on the left has \{i+2,i+3\} as non–trivial element. Since A_{\overline{i}} is union–closed we can hope that many of its members contain \{i+2,i+3\} as subset and indeed there are 4 such sets, namely

      \{i+2,i+3\}, \{i+1,i+2,i+3\},

      \{i+2,i+3,i+4\},\{i+1,i+2,i+3,i+4\}.

      The set system A_i only contains 3 such sets

      \{i,i+1,i+2,i+3\}, \{i+2,i+3,i+4,i\},

      \{i,i+1,i+2,i+3,i+4\}.

      Therefore, there is no injective map \varphi: A_{\overline{i}} \rightarrow A_i with \varphi(x)\subseteq x.

    • Alec Edgington Says:

      Tim and Tom’s argument for FUNC when the family is ‘all cyclic unions of an interval in \mathbb{Z}_n’ is pretty convincing. I wonder if we can tackle the case of ‘all cyclic unions of S’ for an arbitrary S \subseteq \mathbb{Z}_n (i.e. the smallest rotationally-invariant union-closed family that contains S). Even the case where S is a union of two intervals would be a start; this might be amenable to a similar (slightly more complex) argument.

    • Gil Kalai Says:

      The weaker bijection version of FUNC is equivalent to a stronger numerical version of FUNC (I am not sure if we considered it before).

      Given a two sequences a_1,a_2,\dots,a_m and b_1,b_2, \dots b_m we say that the first sequence majorizes the second if a_1+a_2+\cdots +a_k\geq b_1+b_2+\cdots+b_k for every k.

      Now, for an element x we can write a_i(x) the number of (n-i+1) sets in the family containing x, and b_i(x) the number of (n-i)-sets in the family not containing x. Stronger FUNC asserts that for some x the a-sequence majorizes the b sequence.

      Maybe such a stronger statement is more amenable for some inductive argument and more likely maybe it is more amenable to a counterexample.

    • Gil Kalai Says:

      Maybe we can increase k one by one and show that among the set of x‘s that satisfies the inequalities for 1,2,\dots ,k nonempty subset will satisfy the next inequality. for k=1 it is always ok, and I think I convinced myself its ok for $k=2$. ( Also maybe it will be a little more convenient to move to the complements and talk about intersection closed sets.)

  4. gowers Says:

    In the post I gave as a question (not a serious helping-with-FUNC question) whether there is a subset A of \mathbb Z_p of density less than 1/2 such that for every x\in A there is an arithmetic progression mod p of length 10 with common difference x. But this is easy: a random set of positive density will contain arithmetic progressions of length 10 with every common difference.

    I think the question becomes interesting if instead one asks for an arithmetic progression of length C\log n. It has a Kakeya-ish flavour, since one way of answering it would be to find a set of small density that contains an arithmetic progression of length C\log n for every common difference. Does existing knowledge about the Kakeya problem give such an example?

    • Brendan Murphy Says:

      Thinking of the graphs of the arithmetic progressions as lines in \mathbb{F}_p^2, it is possible to show that |A|\gg p^{1/2}k^{\epsilon}, where k=C\log n is the length of the progressions and \epsilon > 0 is small, and |A|<p^{1-\delta}.

      This uses sum-product ideas: we have pk incidences in the point set P = A\times \{0,\ldots,k-1\}. We have about pk^3 collinear triples, and we can use this to show that there are about pk solutions to (1-x)y_1 +xy_2 = y_3 with x in \{0,\ldots,k-1\} and y_1,y_2,y_3 in A. This gives us about p^2k/|A| many solutions to (1-x)y_1 +xy_2 = (1-x)y_1' +xy_2', and a Theorem of Bourgain shows that the number of such solutions is O(|A|^3k^{1-\epsilon}), assuming that k is sufficiently large and |A| 0; if k is small, we can use more recent sum-product results.

      This method only uses the fact that there are p progressions of length k contained in A, so in fact p could be n, the number of progressions of length k contained in A. For this reason, the exponent of p is the best this method can offer. If the Szemeredi-Trotter incidence bound were true over \mathbb{Z}/p, then we could take \epsilon = 1/2.

      There may be a better way of doing this, but the above estimates are “off the shelf”. In particular, we do not exploit that the x-coordinates of our point set form an interval.

  5. Thomas Says:

    I’m interested in extending the finite results on Frankl’s conjecture, does anyone know where I can find the paper proving that if the size of the ground set is 12, then the set is Frankl’s?

    • Tom Eccles Says:

      Actually, I think only 11 is known. The paper is “The 11-element case of Frankl’s conjecture” by Bosnjak and Markovic.

    • gowers Says:

      Theorem 17 in the survey seems to say that 12 is known, and a result of Zivkovic and Vuckovic, or am I misunderstanding something? It just says “preprint” in the list of references, though, so perhaps it never appeared.

    • Tom Eccles Says:

      You’re quite right – Theorem 17 says 12 is known, which I’d missed. As far as I can see, the result never appeared.

    • Thomas Says:

      yes, papers about FUNC seem very hard to track down. I’ll try to recreate the proof myself

    • Thomas Says:

      I’ve been working on finding configurations of sets that imply Frankl’s conjecture, and I found some interesting results about the weight function. When the configuration implies FUNC, there is usually a range of possible weights that can work, but when it doesn’t, there is usually a unique weight function that gives the best bound for the minimal abundance. For example, for the configuration {1, 2, 3}, {1, 2, 4}, choosing w(1)=w(2)=31, w(3)=w(4)=24, the minimal abundance is 27/55, which is best possible. This was found by equating the weights of the extreme cases. I’m working on finding the best weight function for other configurations, but unfortunately, there are more variables to consider.

  6. gowers Says:

    For amusement, and perhaps more, here are some further generalizations of FUNC.

    First, here’s a “ternary” version. Let \mathcal F be a collection of functions f:X\to\{0,1,2\}, where X is a finite set. Suppose that \mathcal F is closed under taking pointwise maxima and that the pointwise maximum of all the functions is the constant function taking the value 2 everywhere. Must there be some x\in X such that f(x)=2 for at least \frac 13|\mathcal F| functions f\in\mathcal F?

    While wondering about the slightly ad hoc condition about the pointwise maximum being the constant function 2, I came up with the following generalizations, which are not too carefully considered, so might be false for an easy reason. Indeed, the second one could be complete nonsense.

    Let \mathcal F be a collection of functions from X to \{1,\dots,k\} that is closed under taking pointwise maxima. Let g be the pointwise maximum of all the f\in\mathcal F. Must there exist x\in X such that the proportion of f\in\mathcal F such that f(x)=g(x) is at least g(x)^{-1}?

    One can rephrase the question in a suggestive way as follows. Given any \mathcal Y\subset X we can consider the projected function system \mathcal F[Y], the set of all functions h:Y\to\{1,2,\dots,k\} such that h is the restriction to Y of some f\in\mathcal F. Does there exist some x\in X such that the abundance of g(x) in \mathcal F[\{x\}] is at least the abundance of g(x) in \mathcal F?

    The reason I call that suggestive is that it raises the possibility of proving something by looking at projections to sets that are smaller than X and larger than singletons.

    • gowers Says:

      One small aspect of the second generalization that I like if it turns out not to be rubbish is that it gives a reformulation of Frankl’s conjecture itself in a way that doesn’t require one to say that \mathcal A contains at least one non-empty set.

    • Tobias Fritz Says:

      Hmm, for the ternary version, what does FUNC tell us about this if we use the old trick of duplicating points x to x_1,x_2 and throwing in all implications x_1\Rightarrow x_2 in order to emulate ternay functions by binary ones? And what if one applies to the same trick to the g-version?

      About proving something by looking at projections to sets that are smaller than X and larger than singletons, that’s what happens also in the proof of Knill’s unconditional lower bound n/\log_2(n).

    • gowers Says:

      OK, to spell it out, you’re saying that if we have a ternary function system \mathcal F on a ground set X, we can replace each x\in X by two points x_1,x_2, and then for each function f\in F we take a set A such that for each x\in X, if f(x)=0, then A\cap\{x_1,x_2\}=\emptyset, if f(x)=1, then A\cap\{x_1,x_2\}=\{x_1\}, and if f(x)=2, then A\cap\{x_1,x_2\}=\{x_1,x_2\}.

      I’m not quite sure what we learn from FUNC here. A simple-minded argument will tell us that at least one x_1 has abundance at least 1/2, but we would be wanting to use the extra hypothesis that every x_2 belongs to at least one of the sets A\in\mathcal A (and that x_2\implies x_1) to get that some x_2 has abundance at least 1/3. But maybe there is a smarter argument that gives more.

    • Thomas Says:

      I don’t know if I’m missing something, but isn’t the set of functions {0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 2} (the first element is f(1), the second is f(2)) a counterexample to your conjecture?

    • gowers Says:

      Indeed it is. Thanks for that. I’ll see whether I can come up with a better candidate for a ternary generalization.

      In fact, here’s one right now. It suffers from being less obviously natural, but maybe it’s OK.

      Define an operation \boxplus on \{0,1,\dots,k\} by

      a\boxplus b=\min\{a+b,k\}.

      Extend that to an operation on functions/sequences by applying it pointwise.

      Now let \mathcal F be a set of functions f:X\to\{0,1,\dots,k\} that contains at least one non-zero function and is closed under \boxplus. Must there be some x such that f(x)=k for at least (k+1)^{-1}|\mathcal F| of the functions in \mathcal F?

      If true, this would be best possible, as can be seen by taking all functions from X to \{0,1,\dots,k\}.

    • Thomas Says:

      Let k = 4, and choose the functions {2, 2, 2}, {2, 2, 3}, {2, 3, 2}, {2, 3, 3}, {3, 2, 2}, {3, 2, 3}, {3, 3, 2}, {3, 3, 3}, {4, 4, 4}. I think the generalizations need to be a bit more complicated for them to work.

    • Thomas Says:

      What if you take the operation to be a&b, which is the maximum of a and b if they are different, and a+1 if they are the same. This might possibly work.

    • gowers Says:

      Ah yes, good point. I was trying but failing to ensure that it wasn’t possible suddenly to “jump” to the maximum value.

      I think it might be fruitful to search for a good conjecture here (maybe the one you have proposed is already a candidate) because it might give some insight into why Frankl’s conjecture is true — if it is.

    • gowers Says:

      Amusingly, I formulated my revised conjecture after considering only the case k=2 — that is, the ternary case — where it coincides with the version you propose. So it would be interesting to see whether just this case looks true.

    • gowers Says:

      Here’s a different proposal for getting rid of the counterexamples that Thomas points out above. Given two functions f,g:X\to\{0,1,\dots,k\}, let us define H(f,g) to be the set of all functions h:X\to\{0,1,\dots,k\} with the following properties.

      1. If f(x)=f(y) and g(x)=g(y), then h(x)=h(y).

      2. g(x)\leq h(x)\leq f(x)\vee g(x) for every x.

      Now let the closure condition be that for every f,g\in\mathcal F all functions in H(f,g) must belong to \mathcal F as well.

    • Alec Edgington Says:

      I think I may be misunderstanding this. Is \vee pointwise maximum? If so, the second condition is equivalent to g \leq h \leq f. Isn’t this making a different statement from FUNC for the case k = 1?

    • Thomas Says:

      Wouldn’t that be the equivalent of an upset (which I believe someone showed satisfies FUNC)? Given that the constant function f(x)=k is in F, we have for every g that all functions h such that g(x)<=h(x)<=k for all x are in F.

      Pick a value in the domain of F, say 0. For every function f(x) with f(0) not equal to k, there is a unique function g such that g(x)=f(x) for all x except 0, where g(0)=f(0)+1. This shows that f(0)=k in at least 1/k+1 of the function in F.

      I think its very hard to come up with a good generalisation for all k that isn't trivially true or has an easy counterexample.

    • Thomas Says:

      Yes, Alec Edgington is right. I think that must be a condition on the generalisations that we use, that one of their cases has to actually be the original Frankl’s conjecture.

    • Alec Edgington Says:

      Sorry, ignore that comment — I’m not sure what I was thinking!

    • gowers Says:

      Just to clarify the condition I wrote down, suppose that k=1. In that case, let f and g be the characteristic functions of A and B. Then for h to belong to H(f,g) we require that h is constant on A\setminus B, B\setminus A, A\cap B, and (A\cup B)^c. From the second condition, we must have that h is 1 everywhere on B, and also that it cannot exceed 1 on A\cup B or 0 on (A\cup B)^c. So the only thing left to choose is the value on A\setminus B. If we take this to be 0 then we get g and if we take it to be 1 then we get f\vee g. So we recover Frankl’s conjecture, and in particular do not get an up-set.

    • gowers Says:

      In the general case, if the constant function taking value k everywhere belongs to the set, then for every function f that belongs to the set, we get that all larger functions also belong to the set as long as they are constant on sets where f is constant. For example, if k=2, n=5 and the function (1,1,1,0,0) belongs to the set, then under this condition we would get the functions (1,1,1,1,1), (1,1,1,2,2), (2,2,2,0,0) and (2,2,2,1,1) from the closure operation.

      The idea behind it is to get rid of examples where there is a sudden “jump” from most sets to a much larger set.

  7. Miroslav Chlebik Says:

    Let me elaborate on the (bipartite) graph interpretation of the union-closed sets conjecture. Let \mathcal A be a (finite) union-closed family containing also \emptyset, and X be their nonempty union, the ground set.\

    Define a bipartite graph G with vertex set \mathcal A \cup X, where we make A \in \mathcal A adjacent with all x \in A; that is, G is the incidence graph of \mathcal A. (Warning: I suspect that the corresponding part of the proof of Theorem 6 of the Bruhn and Schaudt’s survey is confused, using this with an intersection-closed family!)

    Now one can consider all subsets of vertex set \mathcal A \cup X that are (inclusionwise) maximal stable sets in G; they are exactly the complements of the vertex sets that are (inclusionwise) minimal vertex covers in G. The family of traces of these (inclusionwise) minimal vertex covers in G coincides with the family \mathcal A; this is the point where the union-closedness is crucial.

    Given any A \in \mathcal A, there is an (inclusionwise) minimal vertex cover C_A in G such that C_A \cap X = A. One can see that
    C_A \cap \mathcal A then consists of those sets B \in \mathcal A with $B \setminus A \neq \emptyset$. Now double count all (\sum_{x \in X} |\mathcal A_x|) edges of G; \sum_{x \in A} |\mathcal A_x| of them are covered by the vertices of A, and the edges not covered by A are exactly (B, x) for
    B \in \mathcal A with B \setminus A \neq \emptyset and x \in B \setminus A. We get for every A \in \mathcal A,

    \displaystyle \sum_{B \in \mathcal A} |B \setminus A|+\sum_{x \in A} |\mathcal A_x|=\sum_{x \in X} |\mathcal A_x|,

    or equivalently, for every A \in \mathcal A
    \displaystyle \sum_{B \in \mathcal A} |B \setminus A|=\sum_{x \in X \setminus A} |\mathcal A_x|,

    that is what I am happy with…

  8. gowers Says:

    An idle thought about weighted versions that I want to post but don’t have time to check for possible complete stupidity.

    One is looking for a condition on w(A\cup B) in terms of the weights w(A) and w(B). The idle thought was that a definition that generalizes the condition

    w(A\cup B)\geq 1 if w(A)=w(B)=1,

    which applies when all weights are 0 or 1 and the system is union closed, is the condition

    w(A\cup B)\geq w(A)^{1/2}w(B)^{1/2}.

    That is, the weight of a union is at least the geometric mean of the weights of the two sets making up the union.

    Aside from generalizing the normal union-closed condition (I think) to more general systems of weights on sets, this has the desirable property that if you multiply all weights by a positive constant, then it doesn’t change whether the condition is satisfied.

    I haven’t looked at any examples, so it may be that there is nothing nice one can conjecture about abundances in weighted set systems that satisfy this condition.

    • gowers Says:

      A small remark is that if B\subset A, then we get that w(A)\geq w(A)^{1/2}w(B)^{1/2}, which gives that w(A)=0 or w(A)\geq w(B). It’s mildly encouraging that we don’t get that w(A) has to be at least as big as w(B), which was a problem with another weighted version.

    • Tobias Fritz Says:

      That looks interesting, with a bit of a (probably spurious) ‘Hilbert space’ feel to it. A slightly unpleasant feature is that one obtains three different bounds on the weight of a triple union, namely w(A\cup B\cup C)\geq w(A)^{1/2} w(B)^{1/4} w(C)^{1/4}, and the other two with the powers permuted. Maybe one would want to postulate w(A\cup B\cup C)\geq w(A)^{1/3} w(B)^{1/3} w(C)^{1/3} in addition, and similarly for all unions of all arities?

      Here’s a simple observation that may be relevant when thinking about counterexamples to weighted versions. For given w_0, consider the set system
      \mathcal{A}(w_0) = \{A\subseteq X\:|\: w(A)\geq w_0\}
      For either the new weighted version or the earlier one with w(A\cup B)\geq\min\{w(A),w(B)\}, this set system is union-closed. Assuming FUNC, we find an element of abundance at least 1/2 in every \mathcal{A}(w_0), which means that its total weight is at least
      |\mathcal{A}(w_0)| w_0 /2. In order to keep this below some fixed value for all w_0, it may help to keep the product |\mathcal{A}(w_0)|w_0 roughly constant as a function of w_0. One can therefore argue for trying to have a constant multiple of -d(1/w) = dw/w^2 many sets with weight between w and w+dw.

    • gowers Says:

      I agree that that feature is unpleasant and was going to comment on it myself but you have beaten me to it. However, your proposed fix makes no difference, since the AM-GM inequality implies that

      (abc)^{1/3}\leq\max\{a^{1/2}(bc)^{1/4},b^{1/2}(ac)^{1/4},c^{1/2}(ab)^{1/4}\}.

      So I think the unpleasantness may be impossible to get rid of.

    • gowers Says:

      Actually the AM-GM inequality was overkill there. It’s clear that a weighted average where you’re allowed to choose a permutation of the weights will be better than the usual average.

    • Tobias Fritz Says:

      Right, thanks!

      Here’s a half-baked idea on how to derive the w(A\cup B)\geq\min\{w(A),w(B)\}-weighted version of FUNC from plain FUNC. Maybe somebody who’s not currently a jet-lagged zombie will be able to tell whether anything like this has a chance of working.

      Let me assume that all weights are integers in \{0,\ldots,N\}. By first taking rational approximations and then rescaling by a common denominator, this should be a wlog assumption.

      For two such integer weights w'_0 \leq w_0, we have the inclusion \mathcal{A}(w_0)\subseteq \mathcal{A}(w'_0), which trivially is a homomorphism. Hence we can apply the fibre bundle construction in order to obtain a new union-closed family \mathcal{A}. It can be realized explicitly on the ground set X\cup\{1,\ldots,N\} (disjoint union). Here, it consists of all sets of the form A\cup\{w_0,\ldots,N\} with A\subseteq X and w(A)\geq w_0. The assumed inequality for w guarantees that this is union-closed.

      What’s nice about this is that it encodes w(A) as the number of times that the X-part of some set in this system is A. So we have a partial inverse to obtaining a weighted system by restricting the ground set. Moreover, the abundance of some element in the x-part is equal to the total weight in the original weighted system, and this is my main point.

      Then the idea is to apply FUNC to \mathcal{A}. The problem with this is that now we not only have the elements of X around as potentially abundant elements, but also those of \{1,\ldots,N\}. The abundance of these elements is monotonically increasing, with N having an abundance of 1. So of course one can remove N, but then N-1 may still have very large abundance. Hence applying FUNC to \mathcal{A} doesn’t tell us anything new. Is this because I’m not being clever enough, or because the whole construction is too trivial?

    • gowers Says:

      Ever since this comment of Ben Barber I have been a bit suspicious of this weighted version. In particular, what do you suggest doing about the fact that a trivial counterexample is one where w(\emptyset)=1 and all other sets have weight 0 (or tiny positive weight if you don’t want them to have zero weight)?

      Note that with the geometric-mean suggestion, if w(\emptyset)=1, then for every A we have that w(A)\geq w(A)^{1/2}, so all other sets have weight 0 or weight at least 1. So for that version we can take the usual condition that \mathcal A should contain at least one non-empty set.

    • Tobias Fritz Says:

      Yes, I agree. As I now realize, the assumption w(A\cup B)\geq\min\{w(A),w(B)\} is merely a minimal requirement for the proposal in my previous comment to make sense; for example, it is implied by w(A\cup B)\geq w(A)^{1/2} w(B)^{1/2}. But as you’ve reminded me of, one certainly needs to use something more than just that min-inequality.

    • gowers Says:

      I was wondering about how one might come up with a “genuine” counterexample to the min version of the weighted conjecture: maybe one could simply require that w(\emptyset)=0 as the condition of genuineness.

      An idea I had, but I have no idea whether it works and I think others may find it easier to check than I would, is to take the Renaud-Sarvate example (not including the empty set) and give all sets weight 1 except the triple of non-abundant elements, which has a higher weight — as high as possible while retaining the non-abundancy property.

      Or maybe if this doesn’t work, one can do a kind of “layered” weighting where you give a large weight to the triple, a smaller one to the basis elements that intersect the triple, and a yet smaller one to the basis elements that do not intersect the triple, and then make all other weights minimal given those choices.

      But perhaps there’s a simpler approach that does the job.

    • gowers Says:

      A further remark about the GM condition is that it makes it possible to think about variational arguments.

      For example, let w be a weighting that satisfies the condition. Define the abundance of x\in X in an obvious way: it’s the sum of the weights of sets containing x divided by the sum of all weights. Suppose now that there is a set A that has positive weight and contains no element with maximal abundance. Then we can try to reduce the maximal abundance by increasing the weight of A.

      If we increase the weight of A from w(A) to w(A)(1+\epsilon), then we’ll be forced to increase the weights of some other sets. Specifically, if ever we have some set B such that w(A\cup B)=w(A)^{1/2}w(B)^{1/2}, then we’ll have to increase the weight of A\cup B to w(A\cup B)(1+\epsilon)^{1/2}. For very small \epsilon this is approximately w(A\cup B)(1+\epsilon/2).

      If one of the sets A\cup B contains an element x of maximal abundance, then this threatens to cause problems. In fact, I think it will cause serious problems if there are at least two sets B that have this property and contain x. That leaves me not having anything particularly nice to say in this situation.

      What about replacing each weight w(A) by a small adjustment w(A)(1+\epsilon(A))? The condition that the errors \epsilon(A) must satisfy is not quite as simple as one would like, but I think it’s this. (I’m ignoring second-order terms.) Let’s call a pair A,B critical if w(A\cup B)=w(A)^{1/2}w(B)^{1/2}. Then for every critical pair A,B we need

      \epsilon(A\cup B)\geq\frac 12(\epsilon(A)+\epsilon(B)).

      What we would then like to find is a function \epsilon with that property (which it could achieve, for instance, by satisfying that inequality for every pair and not just critical pairs) such that \sum_{A\in\mathcal A_x}\epsilon(A)w(A)<0 for every x of maximal abundance. I think that would show that the maximal abundance can be decreased. (Actually, I think I also need a condition that \sum_{A\in\mathcal A}\epsilon(A)w(A)=0 so that the total weight remains the same.)

      It’s potentially encouraging that the conditions here are convex. It makes it tempting to use the Hahn-Banach theorem to say that if we can’t reduce the maximum abundance by making an infinitesimal change to the weights, then there exists some functional with an interesting property.

    • Tobias Fritz Says:

      I’ve been trying to find a counterexample to min-weighted FUNC together with w(\emptyset)=0, but so far to no avail. Tim’s suggestion to adapt the weight of the triple in the Renaud-Sarvate example sounds good, but doesn’t work because the triple already has an abundance close to 1/2, while the other elements have an abundance way beyond 1/2. Hence one cannot increase the weight of the triple enough to push the abundance of the other elements to below 1/2. The layered approach fails for the same reason. Something similar happens when fiddling with the weight of \{1,\ldots,6\} in Thomas Bloom’s example, as well as in an infinite family of higher-cardinality analogs that I’ve considered.

      I’ve also been searching by hand for suitable weight functions on the power set of a 4-set, but again no luck. In case that anyone has further ideas on what to try to find a counterexample, I’d be willing to work them out.

      On the positive side, thinking about this has led to another generalization of FUNC that may be worth sharing. [I had already tried to post this separately, but it may have ended up in the spam filter.]

      Suppose that we start with the indicator weight of \mathcal{A} and increase the weight of some A\in\mathcal{A} which doesn’t contain any abundant element, as in Tim’s suggestion above. A short calculation shows that this is guaranteed to satisfy min-weighted FUNC if and only if
      \max_{x\in A} |\mathcal{A}_x| + \max_{y\not\in A} |\mathcal{A}_y| \leq |\mathcal{A}|.
      The same holds true if A consists of only abundant elements and we decrease its weight. So here’s a generalization of FUNC: suppose that A\in\mathcal{A} consists of only abundant or only non-abundant elements. Does this imply the inequality above? (To get a genuine counterexample to min-weighted FUNC, we’d also like to have \emptyset\not\in\mathcal{A}, but the question may be interesting regardless.)

      If we were to consider the inequality above for all A\in\mathcal{A}, then we’d be asking whether the added abundance of the two most abundant and \mathcal{A}-separated elements is at least 1.

    • Tobias Fritz Says:

      Correction: the inequality should have been the other way around, \max_{x\in A} |\mathcal{A}_x| + \max_{y\not\in A} |\mathcal{A}_y| \geq |\mathcal{A}|.

  9. Josh Williams Says:

    I have a few thoughts about the Horn clause way of thinking about the problem suggested by Tobias Fritz. Observe if we have any set of conditions \mathbb{C} and choose any condition in our list C = (x,A) then it does not change the resulting set system \mathbb{A} if we add conditions (x,B) where A \subseteq B. Therefore it is safe to add all conditions (x,B) where A \subset B \subseteq [m] - \{x\}. From now on, assume that we have added all such possible conditions.

    Define \mathbb{A}_l := \mathbb{A} \cap [m]^{(l)} and \mathbb{C}_i := \{ (x,A) \in \mathbb{C} : |A| = i \}. It suffices when calculating \mathbb{A}_l to only check the conditions in \mathbb{C}_{m-l}. To see this, first note that if (x,A) = C \in \mathbb{C}_{j} with j \geq m-l+1 then any X not satisfying C must be a subset of [m] \setminus C, which is of size at most l-1, so all conditions with large size can be ignored. Next, let j \leq m-l and assume that all conditions in \mathbb{C}_j are satisfied but not all in \mathbb{C}_{j-1} (induction backwards). Choose some unsatisfied (x,A) = C \in \mathbb{C}_{j-1} and consider the corresponding (x, A \cup \{z\}) for z \in [m] \setminus (A \cup \{x\} in \mathbb{C}_{j}. By our assumption, these are all satisfied, so [m] - A = X which implies |X| = m - j + 1 and since |X| = l then j = (m - l + 1) (contradiction). This proves it is only necessary to check conditions \mathbb{C}_{m-l} for any set size l.

    A set X \in \mathbb{A}_l is forbidden if and only if it is X = [m] - A for some A which is part of a condition (i.e. if there exists C \in \mathbb{B}_{m-l} with C = (x, A)). Define the projection of a condition C = (x,A) as \pi(C) = A. Then this observation shows that the number of forbidden sets must be exactly the number of unique sets in \pi(\mathbb{B}_{m-l}), therefore |\mathbb{A}_l| = \binom{m}{l} - |\pi(\mathbb{B}_{m-l})|.

    Define \mathbb{A}_l(x) := \{ A \in \mathbb{A} : x \in A \} and \mathbb{A}_l'(x) = \mathbb{A}_l \setminus \mathbb{A}_l(x). We now find a set of conditions to use with the set [m] \setminus \{x\} to work out \mathbb{A}_l'(x). Clearly should ignore conditions of the form (x, A) (not applicable). Recall any condition C = (y,A) size m-l only forbids [m] - A in [m]^{(l)}, so if x \notin A then x will be in the forbidden complement, so these conditions can also be ignored. Therefore I claim that the conditions \{B - \{x\} : B \in \mathbb{B}_{m-l}, x \in B\} is our set of conditions for \mathbb{A}_l'(x) working with set [m] \setminus \{x\}. Define \pi_x(\mathbb{B}_{m-l}) := \{ X \in \pi(\mathbb{B}_{m-l}) : x \in X\}. This means the size is |\mathbb{A}_l'(x)| = \binom{m-1}{l} - |\pi_x(\mathbb{B}_{m-l})|.

    • Josh Williams Says:

      Summing each of these bounds gives us |\mathbb{A}'(x)| = 2^{m-1} - |\pi_x(\mathbb{B})| and |\mathbb{A}| = 2^{m} - |\pi(\mathbb{B})|. If FUNC fails then for all x it holds that |\mathbb{A}| < 2|\mathbb{A}'(x)|. Rewriting this, if FUNC fails then all x it holds that 2|\pi_x(\mathbb{B})| < |\pi(\mathbb{B})|. Summing this it would imply that the average size of sets in \pi(\mathbb{B}) is strictly less than m/2, which seems almost definitely false given the properties of \pi(\mathbb{B}). (It is almost true that for any X \in \pi(\mathbb{B}) that all Y \supseteq X is also in \pi(\mathbb{B}) but in fact if C = (x, X) then we only know all supersets Y not including x are inside). But still, may be promising?

    • Josh Williams Says:

      (Sorry, at some point I accidentally switched between using \mathbb{B} and \mathbb{C} – they mean the same)

  10. Tobias Fritz Says:

    Sorry, could this be moved to the proper place? It was intended to be a reply to Tim’s 7:00pm comment…

  11. Marcelo Campos Says:

    A generalization of the conjecture that I think is interesting, but I don’t know if there are any counterexamples, is the following:

    If \mathcal{B} is a basis of a union closed family \mathcal{F} we define:

    M_x(\mathcal{F})=\{A\in \mathcal{B}; x\in A\}

    M(\mathcal{F})=\max\{|M_x(\mathcal{F})|;x\in U(\mathcal{F})\}

    T(\mathcal{F})=\{x\in U(\mathcal{F});M_x(\mathcal{F})=|M(\mathcal{F})|\}

    Then the conjecture is that

    \forall x\in T(\mathcal{F}); |\mathcal{A}_x| \geq \frac{|\mathcal{F}|}{2}

    • Marcelo Campos Says:

      We can prove the conjecture for |T(\mathcal{F})|=1 by induction on M(\mathcal{F}). If we take M(\mathcal{F})=1 the sets are disjoint, so we assume that if M(\mathcal{F})=n-1 then \forall x\in T(\mathcal{F}); |\mathcal{A}_x| \geq \frac{|\mathcal{F}|}{2}. Let \mathcal{B} be the basis for \mathcal{F}, we take x\in T(\mathcal{F}) and \mathcal{F} such that M(\mathcal{F})=n, then we split \mathcal{F} in \mathcal{F}=\mathcal{F'}\cup \{A\cup B; B\in \mathcal{F'}\} such that \mathcal{F'} is the set generated by \mathcal{B}/\{A\} and A is a set such that x\in A\in \mathcal{B}. It’s clear that M(\mathcal{F'})=n-1, then our induction hypothesis is valid and since x\in J  \forall J\in \{A\cup B; B\in \mathcal{F'}\} then claim follows.

    • Tobias Fritz Says:

      Are you trying to show that if there is unique element that occurs in the maximal number of ground sets, then this element is automatically abundant?

      Unfortunately, this is not the case: let X = \{0,1,2,3,4\} and let \mathcal{A} consist of all subsets of \{1,2,3,4\} together with all sets \{0\}\cup A where A\subseteq\{1,2,3,4\} contains at least two elements. This union-closed family has as generators the singletons 1,2,3 and 4 as well as the sets of the form \{0,x,y\} for distinct x,y\in\{1,2,3,4\}. Hence 0 is contained is 6 generators, which is more than any other element, but has an abundance of only 11/27. Or did I mess something up?

    • Marcelo Campos Says:

      Yes, Tobias Fritz, you’re right, thank you! I believe this proof is valid if there’s only 1 element that appear 2 or more times in the ground set.

  12. Tobias Fritz Says:

    Here’s another strengthening that has come up in the search for counterexamples to the naive min-version of weighted FUNC (with w(\emptyset)=0).

    Let A\in\mathcal{A} be an arbitrary set containing only non-abundant elements. Is it then necessarily the case that \max_{x\in A}|\mathcal{A}_x| + \max_{y\not\in A}|\mathcal{A}_y| \geq |\mathcal{A}|?

    In order for this to hold, the second term on the left must be \geq |\mathcal{A}|/2, establishing the existence of an abundant element. Hence a positive answer implies FUNC.

    The Renaud-Sarvate example satisfies this, as well as our earlier example due to Thomas Bloom (in his notation, every (2,l)-family works). So far I haven’t been able to find any other counterexamples either.

  13. Gil Kalai Says:

    Let me outline another strengthening of FUNC that I mentioned above. It may be more convenient to represent the conjecture for complements of the sets in the original family and thus talk about an intersection-closed family G. Let G_i be those sets in G of size i. So we can think about G_i as a sequence of i-uniform hypergraphs.

    Now for an element x of the ground set let a_i(x) the number of i-sets containing x, and b(i) be the number of (i-1)-sets not containing x.

    We want to prove that there exists x such that

    (1) a_1(x)\le b_1(x)

    (2) a_1(x)+a_2(x) \le b_1(x)+b_2(x)

    (k) a_1(x)+\cdots + a_k(x) \le b_1(x)+\cdots +b_k(x).

    for every k=1,2,\dots ,n.

    (In FUNC we have to exclude a family containing only the empty set and here we have to exclude the family containing all the elements of the ground set.)

    (1) is always true but every new imposed inequality exclude some of the elements. “All” that we need to prove is that some elements survive when we move from k to latex $k+1$. Maybe, for such a step some averaging argument (like those failing for FUNC) will come back to life?

    • Gil Kalai Says:

      This is a comment to related to the above comment but also to the other strengthening. As Igor Balla remarked https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/#comment-153911
      For all we know, maybe we can replace the condition
      (*) ” F is union closed”

      by the condition that

      (**) there is a disjoint family of Boolean intervals [A_i,B_i] such that F are the A_i’s and the B_is form a filter (up-set).

      We dont know that (**) does not imply FUNC as well as various sttengthening like mine above. (Since I moved to complements in the formulation above we need to complement (**)) as well.)

    • Uwe Stroinski Says:

      Assume \mathcal{A} to be the union closed system generated by all intervals of length 1\leq r \frac{p}{4}. Then, the first non–interval sets appear at cardinality larger than \frac{p}{2} and here we have more sets in \mathcal{A}_i than in \mathcal{A}_{\overline{i}}. Thus the above sequences represent the worst case and your conjecture follows.

      That means:

      Let \mathcal{A} be the union closed set system generated by all intervals of length r>\frac{p}{4} in \mathbb{Z}_p for p prime. Then \mathcal{A} satisfies your conjecture (and thus there is an injective map \varphi: \mathcal{A}_{\overline{i}}\rightarrow\mathcal{A}_i with |A|\leq |\varphi(A)| and thus FUNC).

    • Uwe Stroinski Says:

      (The comment before this got scrambled and can be deleted.)

      Assume \mathcal{A} to be the union closed system generated by all intervals of length 1\leq r \frac{p}{4}. Then, the first non–interval sets appear at cardinality larger than \frac{p}{2} and here we have more sets in \mathcal{A}_i than in \mathcal{A}_{\overline{i}}. Thus the above sequences represent the worst case and your conjecture follows.

      That means:

      Let \mathcal{A} be the union closed set system generated by all intervals of length r>\frac{p}{4} in \mathbb{Z}_p for p prime. Then \mathcal{A} satisfies your conjecture (and thus there is an injective map \varphi: \mathcal{A}_{\overline{i}}\rightarrow\mathcal{A}_i with |A|\leq |\varphi(A)| and thus FUNC).

    • Uwe Stroinski Says:

      I see. My comments are too long. Sorry for this.

    • Uwe Stroinski Says:

      The proof idea for the following is too long to fit in a comment:

      Let \mathcal{A} be the union closed set system generated by all intervals of length r>\frac{p}{4} in \mathbb{Z}_p for p prime. Then \mathcal{A} satisfies your conjecture (and thus there is an injective map \varphi: \mathcal{A}_{\overline{i}}\rightarrow\mathcal{A}_i with |A|\leq |\varphi(A)| and thus FUNC).

      I have to think about how I can get it here. Maybe I put it on the Wiki. My other comments in the thread can be deleted.

    • gowers Says:

      It would be great to have the comment here. I wonder whether perhaps you accidentally used a “less than” symbol, which can cause big chunks of text to disappear, especially if later on there is a “greater than” symbol.

      One possibility might be for you to email me the comment. I can then post it for you (and can do so in such a way that it will be under your name).

    • Uwe Stroinski Says:

      I did some computer experiments with union closed set systems generated by intervals in \mathbb{Z}_n, n\leq 13 and so far all of them did (easily) satisfy this conjecture.

      Any idea on where to search for a counterexample are welcome.

    • Uwe Stroinski Says:

      This is a non-garbled version of the comment posted earlier in this thread.

      Assume \mathcal{A} to be the union closed system generated by all intervals of length 1\leq r < m in \mathbb{Z}_m. I try to show that at least some of these systems satisfy your conjecture.

      Since each set A\in \mathcal{A}_{\overline{i}} is also in \mathcal{A}, by translation invariance all its translates are in \mathcal{A}. I want this translates to be different, therefore I fix m = p prime. Then m-|A| of these sets of size |A| are in \mathcal{A}_{\overline{i}} and |A| of these sets of size |A| are in \mathcal{A}_i.

      If we repeat this for all cardinalities from r to m we can see that (in this situation) \mathcal{A}_i contains 1 set of cardinality m, m-1 sets of cardinality m-1 and so on, whereas \mathcal{A}_{\overline{i}} contains 0 sets of cardinality m, 1 set of cardinality m-1 and so on

      \mathcal{A}_i: 1, m-1, m-2,\ldots r,

      \mathcal{A}_{\overline{i}}: 0,1, 2,\ldots, m-r.

      However, there is an obstacle. The set of sets of a fixed cardinality in \mathcal{A}_{\overline{i}} does not need to be generated by just one element. If that happens for small cardinalities less or equal \frac{m}{2} there will be much more sets (of this cardinality) in \mathcal{A}_{\overline{i}} than in \mathcal{A}_i. I fix that brute force be requiring r>\frac{p}{4}. Then, the first non–interval sets appear at cardinality larger than \frac{p}{2} and here we have more sets in \mathcal{A}_i than in \mathcal{A}_{\overline{i}}. Thus the above sequences represent the worst case and your conjecture follows.

      That means:

      Let \mathcal{A} be the union closed set system generated by all intervals of length r>\frac{p}{4} in \mathbb{Z}_p for p prime. Then \mathcal{A} satisfies your conjecture (and thus there is an injective map \varphi: \mathcal{A}_{\overline{i}}\rightarrow\mathcal{A}_i with |A|\leq |\varphi(A)| and thus FUNC).

  14. gowers Says:

    It seems to me that we are beginning to put together quite a nice collection of strengthenings of FUNC. Of course, they have not yet been very stringently tested, so it is likely that some of them will fall. But if any of them survive and turn out to be new, then this project will have achieved something worthwhile.

    In this comment I want to amplify on a remark I made earlier about how a weighted version of FUNC might lend itself to a variational approach. Here, once again, is the weighted version. Let w be a non-negative function on the power set of a finite set X and suppose that w(A)\ne 0 for at least one non-empty set A. Suppose also that w(A\cup B)\geq w(A)^{1/2}w(B)^{1/2} for every pair of sets A,B\subset X. If all the weights are 0 or 1, then this is precisely saying that we have the characteristic functions from a union-closed family that contains a non-empty set.

    The conjecture would now be that there exists x such that

    \sum_{A\ni x}w(A)\geq\frac 12\sum_Aw(A).

    It is quite possible that there is a completely trivial counterexample to this conjecture — I have not looked carefully. So there’s a danger that this comment is a waste of time. But let me make it anyway.

    What I would like to find is a nice condition that w must satisfy if it is impossible to reduce the maximum abundance of any element of X. And then in my dreams I’d like to show that the only set systems that satisfy this nice condition are something good such as power sets with duplicated elements. In other words, I’d like to find a smooth path from an arbitrary system of weights to a system of weights where all abundances are 1/2, while all the time not increasing the maximum abundance.

    So let’s take a system of weights w and let’s assume that it cannot be improved by an infinitesimal change.

    I’m going to assume for convenience that all weights are non-zero, since the maximum abundance depends continuously on the weights, so if it is always at least 1/2 for non-zero weights, then by a limiting argument it is always at least 1/2 when the weights are allowed to be zero.

    So now we can represent an arbitrary perturbation of the weights as replacing the weight w(A) by the weight w(A)(1+\epsilon(A)). We will get an improvement to the maximum abundance if we can choose the \epsilon(A) to have the following properties.

    (1) For every A,B\subset X such that w(A\cup B)=w(A)^{1/2}w(B)^{1/2}, \epsilon(A\cup B)\geq\frac 12(\epsilon(A)+\epsilon B).

    (2) \sum_A\epsilon(A)w(A)=0.

    (3) \sum_{A\in\mathcal A_x}\epsilon(A)w(A)<0 for every x of maximal abundance.

    Let me briefly explain why this is. The total change to the weights is \sum_A\epsilon(A)w(A), so condition (2) is saying that the sum of the weights does not change. The change to the geometric mean w(A)^{1/2}w(B)^{1/2} is, to first order, w(A)^{1/2}w(B)^{1/2}(\epsilon(A)+\epsilon(B))/2, so in order to preserve the GM condition we need condition (1) (and it is sufficient, up to first order). The change to the total weight of sets containing x is \sum_{A\in\mathcal A_x}\epsilon(A)w(A), so if that is negative, then because the total weight over all sets has stayed the same, the abundance of x has decreased. (Furthermore, it has decreased by a first-order amount, which is why second-order errors in (1) do not matter.)

    Since this comment is getting long, I’ll finish it and continue with a new one, in case I lose what I’ve written.

    • gowers Says:

      The plan now is to dualize. That is, if we cannot find \epsilon satisfying the above system of inequalities, there should be a separating functional of some kind. Such functionals are often useful, so it seems like a good idea to work out what this one is, and what properties it has.

      The set of \epsilon satisfying condition (2) is a hyperplane, so actually exhibiting the functional is not a challenge: it is the hyperplane itself. More formally, it is the linear map \epsilon\mapsto\langle\epsilon,w\rangle.

      Let \phi_{A,B} be the linear functional \epsilon\mapsto\frac 12(\epsilon(A)+\epsilon(B))-\epsilon(A\cup B), and let \psi_x be the linear functional \epsilon\mapsto\sum_{A\in\mathcal A_x}\epsilon(A)w(A). Then the assumption we are making is that if \phi_{A,B}(\epsilon)\leq 0 for every critical pair A,B (that is, a pair such that w(A\cup B)=w(A)^{1/2}w(B)^{1/2}) and \psi_x(\epsilon)<0 for every x of maximal abundance, then \langle\epsilon,w\rangle\ne 0. It is clear that if this is the case then it must in fact imply that \langle\epsilon,w\rangle<0.

      But this is equivalent to saying that w is a non-negative linear combination of the \phi_{A,B} such that (A,B) is a critical pair and the \psi_x such that x has maximal abundance. Since the sum of the values of \phi_{A,B} are zero and the sum of the values of w are positive, we also get that at least one \psi_x occurs with a strictly positive coefficient.

      Disentangling that slightly, we have non-negative coefficients \lambda_{A,B} and \mu_x such that for every set Y\subset X we have the identity

      w(Y)=\sum_{A,B}\lambda_{A,B}\phi_{A,B}(Y) + \sum_{x\in M\cap Y}\mu_x.

      Here M is the set of elements of maximal abundance, and \phi_{A,B}(Y)=-1 if Y=A\cup B, 1/2 if Y=A, 1/2 if Y=B (and if more than one of these happens one just adds up the relevant values), and 0 otherwise. Also, the sum over A,B is over the critical pairs.

      It’s not clear to me where we can go with a condition like this, but I think it might be worth thinking about.

      Also, there’s a significant chance that I’ve made mistakes in the above.

    • Alec Edgington Says:

      One thing that puzzles me about the statement ‘the maximum abundance depends continuously on the weights, so if it is always at least 1/2 for non-zero weights, then by a limiting argument it is always at least 1/2 when the weights are allowed to be zero’, which sounds perfectly true, is that if we do assume the weights are non-zero, it follows that w(A) \leq w(B) whenever A \subseteq B, which is a much stronger condition.

      I think the problem must be that it is not always possible to perturb a weighted family with zeros that satisfies the condition to a nearby weighted family without zeros that satisfies the condition.

    • gowers Says:

      Yes that’s quite right. I had previously understood the importance of letting some sets have zero weight, but wishful thinking led me to believe my wrong argument (which is wrong for exactly the reason you suggest).

      So I think that the best that the approach outlined above can give is a condition on the weights once you have decided which ones are non-zero. A potential disappointing outcome is that the argument would show that the best system of weights was one that was 1 or 0 everywhere. I’d be glad of a simple counterexample to that.

      Here’s an attempt at one: \emptyset, 1, 2, 12, 13, 23, 123. Here 1 and 2 have abundance 4/7 and 3 has abundance 3/7.

      Suppose we now slightly increase the weights of 13, 23, and 123 to 1+c. Then 1 has weight (4+2c)/(7+3c), as, by symmetry, does 2. Also, the GM condition is satisfied, since the weights are monotone. But tragically I now see that the abundance of 1 has gone up rather than down.

      Instead, let me reduce the weights of 13 and 23 to 1-2c. Then the weight of 123 must be at least 1-c (ignoring lower order terms). I think otherwise we’re OK. Then the abundance of 1 becomes (4-3c)/(7-5c), I think. This looks better: 5c is a smaller proportion of 7 than 3c is of 4.

    • Tobias Fritz Says:

      For further reference it may be worth pointing out that the variational duality approach above looks like an instance of the Karush-Kuhn-Tucker conditions.

      A nice way to write this kind of weighted FUNC as an optimization problem may be as follows:

      maximize \sum_A w(A)

      subject to:
      w(A)\geq 0
      w(A\cup B) \geq w(A)^{1/2} w(B)^{1/2}
      \sum_{A\ni x} w(A) \leq 1/2

      The idea here is that one tries to maximize the total weight, subject to the usual constraints on w plus the additional assumption that all elements have a weighted absolute abundance of at most 1/2. Weighted FUNC then claims that the solution of this optimization problem is no larger than 1.

    • Brendan Murphy Says:

      Duality for KKT recovers something like Tim’s approach. Following the notation here: https://en.wikipedia.org/wiki/Duality_(optimization)#The_non-linear_case, Tobias’ optimization problem is

      minimize f_0(w), where

      f_0(w) = -\sum_A w(A)

      over the domain $\mathcal D$ of $w$ with all components non-negative, subject to

      h_{A,B}(w), f_x(w) \leq 0

      where

      h_{A,B}(w) = w(A)^{1/2}w(B)^{1/2}-w(A\cup B)

      and

      f_x(w) = -\frac 12 + \sum_{x\in A} w(A).

      If p* is the minimal feasible value of f_0(w), then we wish to show that -1\leq p^*.

      The dual problem begins by defining the Lagrangian

      \Lambda(w,\lambda,\mu) = f_0(w)+\sum_{A,B}\lambda_{A,B}h_{A,B}(w)+\sum_x \mu_x f_x(w),

      where \lambda_{A,B},\mu_x\geq 0.

      Then we define the dual objective function g(\lambda,\mu) by

      g(\lambda,\mu) = \inf_{w\in\mathcal C} \Lambda(w,\lambda,\mu).

      Since g(\lambda,\mu)\leq p* for all \lambda,\mu, it suffices to show that g\geq -1.

    • Tobias Fritz Says:

      Nice! I think that we’ll get some prettier expression by using the constraint h_{A,B}(w) = w(A)w(B) - w(A\cup B)^2 instead.

      Also, maybe it would be interesting to perform the optimization numerically, say for sizes of the ground set between 3 and 5?

    • Brendan Murphy Says:

      Ah yes, that is a nicer constraint.

      My advisor is teaching a “data science” course that is something like combinatorics and linear programming plus python. Maybe some of his students would be interested in running numerics.

    • gowers Says:

      If a counterexample to this weighted version doesn’t emerge soon, then it would certainly be very nice to have some data to look at about the optimal weights for various set systems that we have been considering. (I’d be interested to know what the right weights were for the Renaud-Sarvate example, for instance.)

    • Alec Edgington Says:

      If there is a counterexample w to Tim’s GM-weighting conjecture, then its support \mathcal{A} = \{A : w(A) \neq 0\} must be a counterexample to Gil’s previous conjecture about injections \phi : \mathcal{A}_{\bar{x}} \to \mathcal{A}_x such that A \subseteq \phi(A) for all A. Indeed, if \phi is such an injection, then for any w supported on \mathcal{A} that satisfies the GM condition, \sum_{A : x \in A} w(A) \geq \sum_{A : x \notin A} w(\phi(A)) \geq \sum_{A : x \notin A} w(A).

      So the first place to look for a counterexample to the GM-weighting conjecture is the \mathbb{Z}_5 example considered previously.

    • Alec Edgington Says:

      I think we can eliminate any counterexample supported on the intervals of \mathbb{Z}_5 of length at least 2, by an averaging argument. Observe that

      \sum_x (\sum_{A : x \in A} w(A) - \sum_{A : x \notin A} w(A)) = \sum_A (\lvert A \rvert - (n - \lvert A \rvert)) w(A) (where n is the size of the ground set). Writing s_r = \sum_{A : \lvert A \rvert = r} w(A), this is \sum_r (2r-n) s_r. If we can show this to be non-negative then we’re done. In the case in question this is -s_2 + s_3 + 3 s_4 + 5 s_5. Since we can map the 2-intervals bijectively to the 3-intervals in such a way that each maps to a superset of itself (just extend it by one to the right), we have that s_3 \geq s_2, and the other terms are non-negative, which I think completes the proof. However, I have a niggling doubt that it was too easy and I’ve made a mistake.

  15. Alec Edgington Says:

    Here is yet another strengthening of FUNC, which is ‘weaker’ than Gil’s injection-to-supersets conjecture but ‘stronger’ than Tim’s GM-weighting conjecture.

    Let \mathcal{A} be a union-closed family over a finite set X, and let f : \mathcal{A} \to \mathbb{Z} be such that f(A) \leq f(B) whenever A, B \in \mathcal{A} and A \subseteq B. Is there always an x \in X such that \sum_{A : x \in A} f(A) \geq \sum_{A : x \notin A} f(A)?

    (Of course, \mathbb{Z} could be replaced by \mathbb{R}, or [0,1], without changing the substance of the question.)

    • Alec Edgington Says:

      Ah, sorry, that is exactly equivalent to Tim’s GM-weighting conjecture, isn’t it?

    • Alec Edgington Says:

      Also, the statement is false if we allow negative values for f, so we have to add that f(A) \geq 0.

    • Tobias Fritz Says:

      Interesting observation!

      For fixed \mathcal{A} and real-valued f, this conjecture is a linear programming problem, which makes it very amenable to a numerical approach. I’d suggest using a reformulation similar to the above, where we impose all elements to have weighted absolute abundance of at most 1/2 and try to maximize the total weight:

      maximize \sum_{A\in\mathcal{A}} f(A)

      subject to f(A)\geq 0 for all Ain\mathcal{A}
      f(A)\leq f(B) for A\subseteq B
      \sum_{A\ni x} f(A) \leq 1 for all x

      The conjecture is that the optimal solution is no larger than 1.

      I could run this on some examples, such as Renaud-Sarvate, over the weekend. But if somebody else wants to do it, please go ahead!

    • Tobias Fritz Says:

      Sorry, the right-hand side of the last inequality should have been 1/2…

    • Gil Kalai Says:

      Isn’t it also equivalent to my “injection-to-larger” conjecture (which I think is itself equivalent to my sequence of inequalities)?

    • gowers Says:

      Ah, I hadn’t spotted that equivalence. I think it makes my conjecture less interesting — I had thought previously that it was possible for w(A\cup B) to lie strictly between w(A) and w(B). At the very least, it means that stating it in terms of geometric means is silly. The condition is simply that w is supported on a union-closed family and that it is monotone on that family. But it is still mildly interesting that choosing w to be 1 everywhere is not always optimal.

      Maybe something GM-ish could be recovered if the condition were modified to one that merely says that w(A\cup B)^2\geq w(A)w(B) when A\cup B is not equal to either A or B.

    • Alec Edgington Says:

      Gil, could you explain the equivalence to your injection-to-larger conjecture?

      It would definitely be interesting to run this through a linear optimization program for various union-closed families.

      If true (and it does seem hard to find a counterexample), it’s conceivable it could be more amenable to an inductive proof.

    • gowers Says:

      For what it’s worth, given the equivalence noted by Alec, the condition for not being able to improve the weights can be modified as follows. (By the way I should confess to a mental block here. I’ve never been able to learn about duality of linear programming, Lagrange multipliers, etc., so whenever such a problem comes along I have to think about it in my own equivalent way. Apologies for this.)

      There are non-negative coefficients \lambda_{A,B} and \mu_x, where the \lambda_{A,B} are defined for all A,B\in\mathcal A with A\supset B and the \mu_x are defined for all x of maximal abundance, and they have the property that for each Y\in A,

      w(Y)=\sum_{A\supset Y}\lambda_{A,Y}-\sum_{A\subset Y}\lambda_{Y,A}+\sum_{x\in Y\cap M}\mu_x.

    • gowers Says:

      As a quick example, if we have the system \emptyset, \{1\},\{1,2\},\dots,\{1,2,\dots,m\}\}, then 1 is the unique element of maximum abundance. Set \mu_1=1. That contributes a weight of 1 to every set except the empty set. Now let \lambda_{A,\emptyset}=1/(m+1) and all other \lambda_{A,B} be zero. Adding these contributions gives us w(\emptyset)=m/(m+1), and also w(A)=m/(m+1) for all the other sets, so we have shown that the constant weight cannot be locally improved.

      Slightly disturbingly, that also seems to show that any allowable system of weights that is constant on the non-empty sets cannot be locally improved, but that is surely false, since one would like to give as much weight to the empty set as possible. I’ll have to think about where I’ve gone wrong.

    • Domink Says:

      Maximizing \sum_{A} f(A) subject to 0\leq f(A)\leq f(B) for all A\subset B and \sum_{A\ni x} f(A)\leq 1/2 for all x on the union closed set system (of cardinality 119) generated by {{7, 8}, {7, 9}, {7, 10}, {8, 9}, {8, 10}, {9, 10}, {1, 7, 8}, {2, 7,
      9}, {3, 7, 10}, {4, 8, 9}, {5, 8, 10}, {6, 9, 10}, {1, 2, 3, 4, 5,
      6}} yields a weight of \frac{53}{1672} for all sets containing {1,2,3,4,5,6} and a weight of \frac{5}{1672} for all other sets. The total weight would then be \frac{1171}{1672}\approx 0.7004.

    • Gil Kalai Says:

      I did not say they are equivalent. I only asked about it.

      Actually I want the same x for every f (do you expect it in your version?) but I think I am only looking at f of the form that it is 1 if the set hast at least t elements.

    • Brendan Murphy Says:

      Since the conditions on f make sense for any set system, it would be nice to have examples where the maximum is larger than 1.

      If there were a nice family of examples, a reasonably strategy would be to prove that a set system whose optimal weight is above 1 is similar to an extremal example, while presumably the extremal examples are not union-closed.

      It would also be nice to know if the optimum value of w is Lipschitz as a function of the set systems (with the Hamming metric on collection of set systems). E.g. in Domink’s example, throwing away a few elements of the set system doesn’t change the maximum weight weight by more than \approx 1/30 per set. If we knew this in general, then the condition of having maximum weight more than 1 would be “robust”.

    • Domink Says:

      For non union closed families the maximum can be arbitrarily large, just take a set system of singletons.
      I also ran my script on the 27 sets from the Renaud-Servate example. There the optimal weights are \frac{3}{53} for all sets containing 123 and \frac{1}{106} for all other sets. The maximum corresponding to these then is \frac{67}{106}\approx 0.632.

    • Eckhard Says:

      I can confirm Dominik’s results for both the 119-set and the 27-set families.

    • Tobias Fritz Says:

      Postulating the same x to work for all f is too strong: take \mathcal{A} to consist of all subsets of X that are missing at most a singleton, and let f be the indicator function of \mathcal{A} minus X\setminus\{x\}. Gil, could you elaborate a bit on your additional condition on f to be 1 on sets of at least t elements? What is t?

      Let me try to understand the results of Domink’s and Eckhard’s computations in the case of Thomas Bloom’s example. The weighted abundance of each of 1,\ldots,6 ends up being (2^4-4)\cdot \tfrac{53}{1672} + 40\cdot \tfrac{5}{1672}=1/2, while the weighted abundance of each of 7,\ldots,10 is 7\cdot\tfrac{53}{1672} + 93\cdot\tfrac{5}{1672} = 1/2, so that all the inequalities \sum_{A\ni x}f(A)\leq 1/2 are tight. This must be where these funny weights are coming from. Since the total weight is <1, there is no counterexample here.

      (It should be possible to obtain a small improvement by throwing in the empty set, but it will be too small to result in a counterexample.)

    • Tobias Fritz Says:

      I wrote, “Postulating the same x to work for all f is too strong [..]”. Please ignore that claim and the example. I must have been out of my mind.

    • Alec Edgington Says:

      Gil: ah, interesting, indeed maybe one can have the same x for every f. Maybe any abundant element would work?

    • Tobias Fritz Says:

      If one requires x to be independent of f in our current version of weighted FUNC, then this implies Gil’s injection-to-larger conjecture: simply take f to be the indicator function of all sets of size at least r in \mathcal{A}_{\bar{x}} and of size at least r+1 in \mathcal{A}_x. It then follows that the cardinality of the former set is at most the cardinality of the latter set, which is equivalent to Gil’s conjecture.

      Summarizing, we have the following implications:

      wFUNC with x depending on f
      \qquad \nwarrow
      \qquad\qquad \textrm{wFUNC with} x \textrm{ constant} \leftarrow \textrm{Gil's }A\subsetq\phi(A)
      \qquad \swarrow
      injection-to-larger

      Observed by Alec, the arrow on the right is relevant in that it shows that every counterexample to the other conjectures must also be a counterexample to the (already disproven) question about injections \phi:\mathcal{A}_{\bar{x}}\to\mathcal{A}_x with A\subseteq\phi(A).

    • Tobias Fritz Says:

      Now that diagram got messed up… let me try again as ASCII art:

      Gil’s injection-to-larger
      Λ
      II
      wFUNC with x constant <= Gil's A\subseteq\phi(A)
      II
      V
      wFUNC with x depending on f

      One more thing: I think that wFUNC with x constant holds if and only if x is abundant in every upper set in \mathcal{A}. In one direction, the indicator function of every upper set is monotone, and hence x must be abundant in the upper set. In the other direction, note that every monotone f is a positive linear combination of indicator functions of upper sets.

    • Alec Edgington Says:

      Nice. I’ve added a section to the wiki listing various strengthenings that have been proposed and relationships between them.

    • Alec Edgington Says:

      I’ve just realized that the above-claimed implication from constant-x weighted FUNC to x-depends-on-f weighted FUNC is incorrect. In fact, constant-x weighted FUNC is false. Let \mathcal{A} again be the subsets of \mathbb{Z}_5 generated by the 2-intervals. Without loss of generality assume x = 0. Then we can assign weight 1 to each of the 7 sets containing \{2, 3\}, and weight 0 to all the other sets. This is a monotone weighting function but the sum of the weights of the sets containing 0 is only 3.

    • Alec Edgington Says:

      Sorry, not thinking straight: the implication is indeed correct, but the conjecture is false.

  16. Gil Kalai Says:

    Let me return to the strengthening I mentioned above (which may be related to the other ones) described in a dual form.

    We have a ground set of n elements. Let’s call them vertices.

    Now we have a sequence of k-uniform hypergraphs, k=0,1,2…,r G_0, G_1,\dots. G_0 contains the empty set. G_1 is a set of vertices. G_2 is a graph. G_3 is a collection of triples and so on. We let G=G_0 \cup G_1 \cup \cdots.

    The crucial property is that the intersection of two edges in G is also in G.

    We want to identify vertices x with the following property:

    P(j): In G_0\cup G_1 \cup \cdots \cup G_j there are at least as many edges not containing x then edges containing x.
    We denote the difference between these numbers by e(x,j).

    This is stronger then FUNC but maybe not by much.

    For j=1 this is true where e(x) is 0 or 1 according to x being in G_1 or not.

    For j=1 the x’s with negative e are those vertices of G_1 which has at least 3 neighbors and moreover have at least 3 neighbors not in G_0. There could be such vertices but a simple inspection shows that there must be x’s not of this kind. So perhaps we should try to examine the next couple of values for r=3,4,5,6,.... (Maybe this coincides with things that are known.)

  17. Domink Says:

    It’s for sure not very efficient but here is a web version of the maximization to play around with: https://www.wolframcloud.com/objects/56d97a3d-f2e7-4669-b28b-e618bc31398d
    It accepts set systems in a Mathematica style curly braces syntax, e.g. {{1,3},{2,4},{5}}, then generates the smallest union closed set system \mathcal{A} containing the given system and performs the maximization \sum_{A\in\mathcal A} w(A) subject to 0\leq w(A)\leq w(B) for all A\subset B\in \mathcal A and \sum_{x\ni A\in\mathcal A}w(A)\leq\frac{1}{2} for all x.
    The Mathematica Code for generating the union closed set system is
    UnionClosedSetSystem[A_] := (Atemp = A;
    While[Length[
    DeleteDuplicates[
    Union[#[[1]], #[[2]]] & /@ Tuples[{Atemp, Atemp}]]] >
    Length[Atemp],
    Atemp = DeleteDuplicates[
    Union[#[[1]], #[[2]]] & /@ Tuples[{Atemp, Atemp}]]]; Atemp)
    The code for the maximization is:
    MaximizeWeights[B_] :=
    NMaximize[{Total[w[#] & /@ B],
    Apply[And, (w[#] >= 0) & /@ B] &&
    Apply[And,
    Complement[
    If[SubsetQ[#[[2]], #[[1]]], w[#[[2]]] >= w[#[[1]]], 0] & /@
    Tuples[{B, B}], {0}]] &&
    Apply[And,
    Table[1/2 – Total[w[#] & /@ Select[B, MemberQ[#, k] &]] >= 0, {k,
    Min[B], Max[B]}]]}, w[#] & /@ B]

    • Tobias Fritz Says:

      Very nice! Running this on Renaud-Sarvate plus the empty set results in an optimal value of \approx 0.642, with the same optimal weights on the nonempty sets, and f(\emptyset) = 1/106 being their minimum. Reasonable.

    • Alec Edgington Says:

      Thanks!

      I tried a few cyclically symmetric families (all unions of rotations of some set) on this program and they all came out with all weights equal. I wonder if this is a property of symmetric families in general (and also whether there are any non-symmetric families that have this property).

    • gowers Says:

      Without checking whether everything I say is true, I think it should be the case that symmetric families will come out with all weights equal, because it should be that a convex combination of weights is at least as good as the worst weight, so one can take a convex combination of an optimal weight with all its symmetries.

    • Gil Kalai Says:

      Regarding Alec’s comment, I am not sure if this is still relevant for the specific property that symmetric properties might have, but let me mention two properties that are weaker than being symmetric. (By symmetric we mean invariant under a transitive group of permutations on the ground set).

      1) weakly regular: every element is contained in the same number of sets from the family.

      2) more regular: every element is contained in the same number of k-sets from the family for every k.

      I would expect that properties for symmetric families relevant to FUNC and its extensions will largely extend to the “more regular” version.

  18. Brendan Murphy Says:

    It’s interesting that there are exactly two weights in the Renaud-Sarvate type examples. Perhaps gaps in weights can be used to cluster the sets.

    It also seems that the weights only depend on the minimal elements, although I’d be surprised if that was true in general.

    Has anyone found an example with three distinct weights?

    • Eckhard Says:

      There appear to be plenty of examples with three distinct weights, even for ground sets as small as {1,2,3,4}. For example, the 13-set family \{\{\},\{1\},\{2\},\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{3,4\},\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\{1,2,3,4\}\}=2^{\{1,2,3,4\}} \backslash \{\{3\},\{4\},\{2,4\}\} has an optimal weight tally of 1/22 (4 times), 3/44 (5 times), and 7/88 (4 times), given a total of 37/44\approx 0.8409.

      All cyclically symmetric families on ground sets with at most 8 elements have all optimal weights equal and total less than one.

    • Tobias Fritz Says:

      Are your cyclically symmetric families all generated by the translates of a single set, as in Alec’s case? Or did you also try taking with the cyclic shifts of two or more sets to take the union closure of?

      In the case of a single generator up to symmetry, I don’t find it so surprising that all the weights are the same: by symmetry and convexity, we can assume wlog that all generators have the same weight (see Tim’s 8:33pm comment). Given this weight for each generator, we obtain optimal abundances if we choose the weight of the other sets as small as possible, i.e. equal to the weight of the generators.

      It would be a bit more puzzling if we still always had equal weights in the case of two or more generators up to symmetry. Does this happen as well?

    • Eckhard Says:

      Thanks, I should have qualified my statement. I had only tested families that were generated as the union-closure of cyclical translates of a single set. I ran a quick test and it seems that the observation remains the same for families generated by rotations of up to five sets on ground sets with up to five elements.

    • Alec Edgington Says:

      It seems on evidence so far that the more symmetric components there are in X, the more distinct weights there are.

      To make that precise, for x, y \in X, say x \sim y if there’s some permutation \pi of X such that \pi(x) = y and \pi permutes the sets in \mathcal{A}. Is the optimal number of distinct weights always less than or equal to the number of equivalence classes under this relation?

    • Eckhard Says:

      I found an example of a cyclically symmetric 30-set family in which the optimal weights are not all equal. It has ground set {1,2,3,4,5,6} and is generated as the union-closure of rotations of {1,2,3} and {1,2,4,5}. In my script, the optimal weights come out to be zero for the three translates of {1,2,4,5}, and 1/36 for the remaining 27 sets in the family, for a total of 3/4.

      I find the example a bit unsatisfactory, however, because it seems too “reducible” in the sense that removing the three zero-weight sets preserves union-closedness of the family.

      The search continues.

    • Brendan Murphy Says:

      For Eckhard’s 30-set family, I could only find 28 sets. We have one 6-set, six 5-sets, at most fifteen 4-sets, and six 3-sets, plus perhaps the empty set, which gives at most 1+6+15+6+1 = 29.

      In addition, I could only find 14 sets containing 3, one of which has zero weight, which would mean that the total weight of 3 (and hence any element, by symmetry) is 13/36. But this means that we could multiply all of the non-zero weights by 18/13 while still satisfying the constraints, which gives a total weight of (18/13)*(3/4) = 27/26 > 1.

      There’s a very significant chance I made a mistake, since I was working by hand. Can anyone else verify either one of our calculations?

      (One possible resolution is this: I think the correct total number of non-empty sets is 1+6+9+6 = 22: one 6-set, six 5-sets, nine 4-sets, and six 3-sets. If we increase the weights to (1/36)*(18/13)=1/26, then the total weight is 22/26 < 1)

    • Eckhard Says:

      You’re right. I described my example incorrectly: its generators should be the _three_ sets {1,2,3}, {1,2,4,5} and {1,3,5}. Sorry for the confusion! Then the 30 sets break down as eight 3-sets, fifteen 4-sets, six 5-sets, and one 6-set. I agree that the example, as originally described, results in a 22-set family. However, I obtain constant optimal weights of 1/30 and a total of 11/15, which is less than your 22/26.

    • Brendan Murphy Says:

      Ah okay, thanks for the clarification. I trust your total of 11/15 for the 22-set family.

      So for the 22-set family, the translates of {1,2,4,5} have weight 1/30, even though they can be removed?

    • Alec Edgington Says:

      Note that in Eckhard’s 30-set example, the optimal solution is not unique: one can assign weights \alpha to the three translates of \{1,2,4,5\} and \beta to all other sets, provided that \alpha \leq \beta and 3 \alpha + 27 \beta = \frac34 (and 2 \alpha + 18 \beta \leq \frac12, but this is implied by the previous condition). In particular, one can choose equal weights \alpha = \beta = \frac{1}{40}.

      So, to refine the question slightly: for symmetric families, is there always an optimal solution with all weights equal?

  19. Brendan Murphy Says:

    This is an attempt to “explain” the patterns we’ve seen in the weights. (I believe it fits the examples with one and two weights, but I haven’t tested it against the new examples.)

    The simplest way to satisfy the constraints w(A)\leq w(B) if A\subseteq B is the following:

    For all B\supseteq A, we have w(B)=w(A), unless there is some A'\subseteq B such that w(A')\geq w(A). (This only matters if we have strict inequality, but I don’t want to confuse wordpress.)

    Thus, the simplest way to choose weights is to weight the minimal elements in a way that avoids conflicts.

    How do the weights go if we choose this simplified scheme?

    Let minimal elements be A_1,\ldots, A_m. Choose the A_i with the *smallest upset*

    \mathcal U_i =\{B\in\mathcal A\colon A_i\subseteq B\}

    and let every element of \mathcal U_i have same weight. For convenience, let’s assume that i =1.

    Now we repeat this process for \mathcal A_1 = \mathcal A\setminus\mathcal U_1, greedily choosing the minimal A_i with smallest upset in \mathcal A_1.

    Some questions are:
    – does this pattern hold for more complicated examples?
    – are there examples where some set above the largest minimal element has weight larger than the largest minimal element?

    • Brendan Murphy Says:

      Sorry, “largest” minimal element is incorrect, it should be minimal element with smallest upset.

      An idea for an inductive proof would be to show that it is optimal to weight every set above A_1 by w(A_1), then show that the set system \mathcal A_1 satisfies suitable hypotheses to continue the proof.

      (P.S. Tim, this idea is taken from Giorgis’ work, where he removes “channels” from Ruzsa’s layered graphs.)

    • Brendan Murphy Says:

      Actually if I understand Eckhard’s example from Feb 20, 12:23pm, then, the answer to the second question is “yes”, since the translates of {1,2,4,5} have weight zero, but the elements of their upset have weight 1/36.

      So this simple scheme is not always the optimal scheme. Although as Eckhard mentions, the translates of {1,2,4,5} can be removed.

    • Tobias Fritz Says:

      Since both Brendan and Miroslav seem to be thinking along these lines, let me try to clarify a bit more the decomposition of a weight function into a positive linear combination of indicator functions of upper sets.

      Let f:\mathcal{A}\to\mathbb{Z} be nonnegative and monotone. As we’ve already observed, U(w) := \{ A\in\mathcal{A}\:|\: f(A)\geq w\} is an upper set in \mathcal{A}. Now let w be the largest value attained by f, and consider f' := f - 1_{U(w)}, where 1_{U(w)} is the indicator function. Then f' is still nonnegative and monotone, but the largest value that it attains is smaller by one. By induction, we therefore obtain a decomposition of f of the form f = \sum_U c_U 1_U, where U ranges over all upper sets in \mathcal{A} and c_U\geq 0. Of course, it follows that the same kind of decomposition also works if f is real-valued.

      However, it may be worth noting that such a decomposition is not unique. For an example, let f:2^{\{0,1\}}\to\mathbb{Z} be the function that assigns to every subset its cardinality. This decomposes into the indicator function of all sets that contain 0 plus the indicator function of all sets that contain 1, while the prescription decomposes it differently into the indicator function of \{0,1\} plus the indicator function of all nonempty sets.

      By the way, does anyone see a relation between our current version of weighted FUNC and Möbius inversion? (I don’t know enough about the latter to say, but have the feeling that it might be relevant.)

      @Miroslav: to get the LaTeX to display here, you have to add “latex” after the dollar sign, like this: $latex

    • Brendan Murphy Says:

      Nice! This is a good way of putting it.

      From the examples, it seems that the weights depend on the generators of the set system, so perhaps we improve our decomposition by summing only over the “principal upsets” given by the generators.

      I wonder if Mobius inversion can be used to do “partial summation” to convert between f = \sum_U c_U 1_U and f = \sum_{A\in\mathcal A} w(A)\delta_A. According to wikipedia, the zeta function and Mobius function of an incidence lattice are analogous to integration and differentiation, so perhaps we can express our \delta_A‘s as “derivatives of indefinite integrals” and “integrate by parts”.

    • Brendan Murphy Says:

      Here’s a link to the relevant wikipedia page: https://en.wikipedia.org/wiki/Incidence_algebra

      Ah and I see it also says that for the natural numbers with the standard order, Mobius inversion is related to differencing, so perhaps the “Mobius inversion as integration by parts” heuristic is standard.

    • Tobias Fritz Says:

      Ah, yes, looking at the principal upsets is a good idea. In fact, if we have any function g:\mathcal{A}\to\mathbb{R}, the Möbius transform is f(A) = \sum_{B\subseteq A} g(B) = \sum_B g(B) 1_{\uparrow\{B\}}(A), where \uparrow\{B\} denotes the principal upset of B. This is indeed of the form \sum_U c_U 1_U, but with the sum only ranging over the principal upsets.

      Conversely, Möbius inversion will therefore decompose any function into a sum over indicator functions of principal upsets. For dimensional reasons, this decomposition is now unique.

      What seems less clear is how to recognize the Möbius inverse of a monotone function as opposed to the Möbius inverse of just any function. Certainly the Möbius transform of a nonnegative function g will be monotone, but the converse often fails: the indicator function of a non-principal upset is not a nonnegative linear combination of indicator functions of principal upsets, and therefore its Möbius transform must take on at least one negative value.

      Anyway, does any of this help us to explain the patterns that we’ve seen in the data?

  20. Miroslav Chlebik Says:

    One can derive certain structural properties of any optimal solution w to our linear maximization problem. Keep an optimal solution w fixed, and denote
    T(w)=\{x: \sum_{A \in \mathcal A_x} w(A)=1/2 \}
    the set of “tight” points for this constraint. Also, assume that
    0 \leq v_1 \leq v_2 \leq \dots \leq v_s
    be the sequence of all achieved values.
    One crucial observation is that, for any i=1,2, \dots , s,
    \{A \in \mathcal A: w(A) \geq v_i \} is also union closed family.
    There are obvious relations between the restriction of our solution w to this family, and the optimal solution (possibly scaled) computed for this new family.
    Every set A \in \mathcal A in the complement of this new family (for i \geq 2 hits “tight point set” T(w), otherwise some inclusionwise maximal elements can increase their weight, that contradicts optimality of w.
    Further discusion need to split according to how the tight points for new problem relate to the original ones, for example.
    In some scenario we may scale w up on one piece, and scale down on the other one, to satisfy the constraints. The fact that our optimality of w assumption will not increase the total weight, will then tell us a useful information about the solution w.

  21. dsp Says:

    There might be a mistake in here somewhere, but it seems to me that one can prove FUNC by combining Tobias Fritz’ description of union-closed families with Fourier analysis in the following way:

    We use [n] to denote the set \{ 1,\dots,n\}, 2^X for the power set of X, e_i for the vector whose ith coordinate is 1 and all other coordinates 0, and, as usual, \hat{f}(x) := \frac{1}{2^n} \sum_{y \in \{ 0,1\}^n} f(y) \chi_x(y) for the Fourier transform of f of x, where \chi_x(y) := (-1)^{x \cdot y}.

    Regard subsets of [n] as elements of \{ 0,1\}^n in the usual way (A being identified with the vector (a_1,\dots,a_n), where a_i = 1 iff i \in A), let \mathcal{A} \subseteq 2^{[n]} be any union-closed family of sets, and let f : \{ 0,1\}^n \longrightarrow \{ 0,1 \} be the indicator function of \mathcal{A}. Then the element i belongs to at least half the sets in A iff $\hat{f}(e_i)$ is not positive.

    Let (b_1,B_1),\dots,(b_r,B_r) be the list of conditions defining A in Tobias Fritz’ description, (b_i,B_i) being shorthand for b_i \in A \Rightarrow A \cap B_i \neq 0. Since b_i would be tautological in B_i, we can require that b_i \not \in B_i for all i (this will be relevant below). Now consider the polynomial x_{b_i} \prod_{j \in B_i} (1-x_j). It evaluates to 1 iff x_{b_i} = 1 and x_j = 0 for every $j \in B_i$, and otherwise to 0. Hence P_i(x_1,\dots,x_n) := 1-x_{b_i} \prod_{j \in B_i} (1-x_j) is the indicator function of the family of all sets satisfying (b_i,B_i), and hence f(x_1,\dots,x_n) = \prod_{i=1}^{r} P_i(x_1,\dots,x_n).

    Consider the function g:\{ 1,-1 \} \longrightarrow \{ 0,1 \} defined by g(1) := 0 and g(-1) := 1. Note that g(x) = \frac{x-1}{-2}. The Fourier coefficient \hat{f}(e_i) equals the coefficient of x_i in the polynomial Q(x_1,\dots,x_n) := f(g(x_1),\dots,g(x_n)) = \prod_{i=1}^{r}(1-\frac{x_{b_i}-1}{-2} \prod_{j \in B_i} (1-\frac{x_j-1}{-2})) = \prod_{i=1}^{r}(1+\frac{x_{b_i}-1}{2} \prod_{j \in B_i} \frac{x_j+1}{2}).

    Note that the constant term of 1+\frac{x_{b_k}-1}{2} \prod_{j \in B_k} \frac{x_j+1}{2} is 1-\frac{1}{2^{|B_k|+1}}. For the coefficient of x_i in 1+\frac{x_{b_k}-1}{2} \prod_{j \in B_k} \frac{x_j+1}{2}, we have the following:

    If b_k = i, then the coefficient of x_i in 1+\frac{x_{b_k}-1}{2} \prod_{j \in B_k} \frac{x_j+1}{2} is \frac{1}{2^{|B_k|+1}}.

    If b_k \neq i and i \in B_k, then the coefficient of x_i in 1+\frac{x_{b_k}-1}{2} \prod_{j \in B_k} \frac{x_j+1}{2} is -\frac{1}{2^{|B_k|+1}}. Note that “b_k \neq i and i \in B_k
    is simply equivalent to “i \in B_k,” since b_k \not \in B_k for all k.

    If b_k \neq i and i \not \in B_k, then the coefficient of x_i in $1+\frac{x_{b_k}-1}{2} \prod_{j \in B_k} \frac{x_j+1}{2}$ is 0.

    Therefore, the coefficient of x_i in Q is \sum_{b_k=i} \frac{1}{2^{|B_k|+1}} \prod_{m \neq k} (1-\frac{1}{2^{|B_m|+1}}) + \sum_{B_t \owns i} (-\frac{1}{2^{|B_t|+1}} \prod_{m \neq t} (1-\frac{1}{2^{|B_m|+1}})). Defining c_k := \prod_{m \neq k} (1-\frac{1}{2^{|B_m|+1}}), we obtain the simpler expression of \sum_{b_k=i} \frac{1}{2^{|B_k|+1}} c_k + \sum_{B_t \owns i} (-\frac{1}{2^{|B_t|+1}} c_t) for the coefficient of x_i in Q.

    Since \sum_{i=1}^{n} \sum_{B_t \owns i} (-\frac{1}{2^{|B_t|+1}} c_t) = \sum_{k=1}^{r} |B_k|(-\frac{1}{2^{|B_k|+1}}c_k) by double counting and \sum_{i=1}^{n} \sum_{b_k=i} \frac{1}{2^{|B_k|+1}} c_k = \sum_{k=1}^{r} \frac{1}{2^{|B_k|+1}}c_k, we have \sum_{i=1}^{n} \hat{f}(e_i) = \sum_{i=1}^{n} (\sum_{b_k=i} \frac{1}{2^{|B_k|+1}} c_k + \sum_{iB_t \owns i} (-\frac{1}{2^{|B_t|+1}} c_t)) = \sum_{k=1}^{r} (\frac{1}{2^{|B_k|+1}}c_k-|B_k|\frac{1}{2^{|B_k|+1}}c_k).

    Now the proof of FUNC is simple: We know that \mathcal{A} satisfies FUNC if it contains a singleton set, so suppose it doesn’t: In that case, we have |B_k| \geq 1 for all k, and hence \sum_{i=1}^{n} \hat{f}(e_i) = \sum_{k=1}^{r} (\frac{1}{2^{|B_k|+1}}c_k-|B_k|\frac{1}{2^{|B_k|+1}}c_k) = \sum_{k=1}^{r} (1-|B_k|)\frac{1}{2^{|B_k|+1}} c_k \leq \sum_{k=1}^{r} 0 = 0. Since \sum_{i=1}^{n} \hat{f}(e_i) is not positive, at least one of the \hat{f}(e_i) must not be positive either, and FUNC is proven.

  22. dsp Says:

    Correction: In my previous comment, it should read “Then the element i belongs to at least half the sets in A iff \hat{f}(e_i) is not positive” and “It evaluates to 1 iff x_{b_i} = 1 and x_j = 0 for every j \in B_i, and otherwise to 0.”

    • Tobias Fritz Says:

      What a brave attempt! To scrutinize this a bit, here are two questions:

      1) Are you sure that the Fourier coefficient \hat{f}(e_i) is equal to the coefficient of x_i in Q? I’d think that every odd power of x_i would contribute as well, and more generally every monomial in which x_i occurs with an odd power and all other variables with an even power.

      2) What you show in the end is \hat{f}(e_i)\leq 0. As far as I understand, this is equal to 2^{-n}\sum_i (|\mathcal{A}_i| - |\mathcal{A}_{\bar{i}}|). So this seems to be trying to show that the average abundance of a uniformly chosen element is at least 1/2, which we know to be false. Am I missing something?

    • dsp Says:

      1) Well, \langle f,g \rangle := 2^{-n} \sum_{x \in \{ 0,1 \}^n} f(x)g(x) defines an inner product on the space of real-valued functions on \{ 0,1 \}^n with an (orthonormal) basis given by the set of functions \chi_y(x), and f(x) = \sum_{y \in \{ 0,1 \}^n} \hat{f}(y) \chi_y(x) Note that \chi_y(x) = \prod_{i \in y} g^{-1}(x_i). Q is of the form \sum_{y \in \{ 0,1 \}^n} k_y \prod_{i \in y} x_i for some coefficients k_y, so we have f(x_1,\dots,x_n) = P(x_1,\dots,x_n) = Q(g^{-1}(x_1),\dots,g^{-1}(x_n)) = \sum_{y \in \{ 0,1 \}^n} k_y \prod_{i \in y} g^{-1}(x_i) = \sum_{y \in \{ 0,1 \}^n} k_y \chi_y(x). Since \sum_{y \in \{ 0,1 \}^n \hat{f}(y) \chi_y(x)} and \sum_{y \in \{ 0,1 \}^n} k_y \chi_y(x) are two linear combinations of the basis vectors that both equal the same vector, we have k_y = \hat{f}(y) for all y.

      2) Of course you’re correct that this proof can’t work for this reason. I think the concrete mistake that let to this false conclusion is the assertion that \sum_{k=1}^{r} (1-|B_k|)\frac{1}{2^{|B_k|+1}} c_k must not be positive because (1-|B_k|) can’t be positive, overlooking that c_k might very well be negative! It was stupid of me not to notice this. Nevertheless, I’m optimistic that the general approach — using the Horn clause description to arrive at a polynomial expression of the indicator function of \mathcal{A}, which can then be used to obtain the value of \hat{f}(e_i) = \mathcal{A}_{\bar{i}} - \mathcal{A}_i could be useful in proving FUNC.

    • Tobias Fritz Says:

      1) Yes, but your original expression for Q as a product over the polynomials associated to the Horn clauses also contains monomials of higher order. Maybe we’re getting confused because a polynomial like x_i^2 is nonconstant as a polynomial, but constant as a function on the hypercube?

      2) Your c_k was defined as \prod_{m\neq k} (1 - \tfrac{1}{2^{|B_m|+1}}). How can this possibly be negative?

      I agree that the idea of combining the Horn clause description with Fourier analysis seems very much worth pursuing. But wouldn’t one expect an analytic argument to rely on analytic bounds like Cauchy-Schwarz, hypercontractivity, etc?

  23. Tobias Fritz Says:

    I’ve been contemplating the fibre bundle construction a bit more, and there’s a small chance that this may turn into a proof strategy. But what I mostly find tantalizing about the following approach is that it’s very close to the search for counterexamples. In the special cases that I’ve looked at so far, one can write down quite concretely which properties a (minimal) counterexample must have, and then one ends up finding reasons for why these properties are difficult to satisfy jointly. However, so far I don’t have any definite results.

    The basic idea is to approach the lattice-theoretic formulation of FUNC via induction on the size of \mathcal{A}. There are two completely independent problems that need to be solved:

    1) Given a fibre bundle with projection map p:\mathcal{A}\to\mathcal{K}, show that if both \mathcal{K} and all fibres p^{-1}(K) satisfy FUNC, then so does \mathcal{A}. This is the part that’s especially close to the search for a counterexample. So far, I’ve been looking at the case where \mathcal{K} = \{0,1\} is the two-element lattice with 0\leq 1, and am currently analyzing the tradeoffs between the abundances of the join-irreducibles in p^{-1}(0) vs those in p^{-1}(1).

    2) Show that every \mathcal{A} arises as the total space of some nontrivial bundle p:\mathcal{A}\to\mathcal{K}. Again I’ve looked at the case \mathcal{K} = \{0,1\} so far, and it turns out that it’s possible to find such a p if and only if \mathcal{A} has a prime ideal (or, equivalently, a prime filter). While these exist in many large classes of lattices, M3 is the smallest lattice which doesn’t have one.

    In general, the problem is this: find a lattice \mathcal{K} with |\mathcal{K}| < |\mathcal{A}| and a surjective lattice homomorphism p:\mathcal{A}\to\mathcal{K} (i.e. preserving joins, meets, top and bottom). In other words, find a quotient lattice of \mathcal{A}. In addition, this must satisfy the following lifting property: for every K\leq L\leq M in \mathcal{K} and A\in p^{-1}(K) and C\in p^{-1}(M), there is B\in p^{-1}(L) with A\leq B\leq C. This is the difficult part.

    In order to turn this into a possible proof strategy for FUNC, one clearly needs some sort of positive answer to 2), which may be unlikely. But one can still hope to obtain a nice class of lattices for which 2) holds and try to prove FUNC for these.

    In case that anyone has any ideas about this, especially part 2), it would be great to know!

    • Tobias Fritz Says:

      In terms of congruences, Problem 2) is equivalent to the existence of a nontrivial congruence on \mathcal{A} such that if A\leq B_1\sim B_2\leq C and A\leq C, then there exists B\sim B_i such that A\leq B\leq C.

      A sort of trivial counterexample to 2) is M3 itself: the only nontrivial quotient of this is the Boolean algebra on two generators (power set of a 2-element set), but the quotient map doesn’t have the lifting property. But it would be more satisfactory to have counterexamples to 2) for which FUNC doesn’t hold trivially.

    • Tobias Fritz Says:

      To wrap this up, let me explain that 2) is indeed far from true, so that this approach cannot be a general proof strategy.

      The reason is that there are arbitrarily large finite lattices that are simple, i.e. do not have any nontrivial lattice quotients. For example, there is a theorem of Ore saying that the partition lattice of a finite set is simple. (See Theorem IV.4.2 in Grätzer’s “General Lattice Theory.)

  24. Tobias Fritz Says:

    In trying to prove FUNC, is it enough to consider those \mathcal{A} that contain every set of the form X\setminus\{x\}?

    My first thought was that this should be an easy-to-see wlog assumption, but upon further reflection this doesn’t seem clear at all. The property is strictly stronger than assuming that \mathcal{A} separates points. And just throwing in the missing sets X\setminus\{x\} contributes a lot of unwanted abundance to most elements, so this doesn’t look like a wlog procedure.

    Since all the nontrivial examples that I remember being discussed here have this property, I wonder whether we should look for some interesting examples that don’t have it.

    The reason that I’m asking is that this property translates into atomistic (atomisticity?) in the lattice-theoretic formulation. This is a nice structural property of a lattice that would be convenient to assume.

  25. Alec Edgington Says:

    It doesn’t seem clear that we can make that assumption, since adding those sets to a family increases some abundances.

    Is it always the case that a separating union-closed family contains at least one complement of a singleton?

    • Alec Edgington Says:

      Ah yes, I think that last statement follows easily from the separability condition: by taking two distinct elements not in a set of maximal cardinality less than \lvert X \rvert, finding a set that separates them, and taking the union, for a contradiction.

    • Miroslav Chlebik Says:

      Yes; any inclusionwise maximal proper set A in such a family is complement of a singleton. If (at least) two elements x,y are missing, using separating property we can find a set in our family containing just one of them; the union of this set with A is larger proper set;
      a contradiction.

    • Thomas Says:

      In fact we can assume that at least two of the sets X\{x} are in \mathcal{A}. The only way that there can be only one set X\{x} in \mathcal{A} is if that particular x is in only one set, namely the full set X. This needlessly increases the abundance of all other elements.

  26. Gil Kalai Says:

    Let me mention a question that maybe I asked before or is trivial or both. Let F be a union closed family what is the minimal hamming distance from F to a monotone (up) family? There is a lower bound on this quantity in terms of “directed” influences which are closely related to the quantities we look for. Directed influences are the measure of sets in F not containing x such that adding x takes you away from F. So we can also ask: what is the smallest directed influence a union closed family must have?

  27. Panurge Says:

    Fifteen hours ago, I put the following question on mathoverflow : would it be reasonable to conjecture that there is a real constant c>1/2 (perhaps c could be taken equal to 2/3) such that, for every natural number n, for every union closed family of n distinct finite sets with at least two elements in their union U, there is at least one subset {a,b} of U, with two elements, that intersects at least cn−1 sets of the family ?
    It’s here :https://mathoverflow.net/questions/231769/a-generalization-of-frankls-conjecture
    I got no definite answer, but it was suggested that I put the question here. In fact, I am not at the level of this Polymath, but since my question was not dismissed on Mathoverflow, perhaps it is not too presumptuous to put it here.

    • Alec Edgington Says:

      This reminds me of a generalization that Thomas Bloom suggested, and that has not as far as I know been disproved, namely that for every k \leq \log_2 n there is a subset S \subseteq X of size k that is contained in at least 2^{-k} n sets in the family.

      A natural variant (somewhat generalizing yours) would be that for every k \leq \log_2 n there is a subset S \subseteq X of size k that intersects at least (1 - 2^{-k}) n sets in the family.

  28. Miroslav Chlebik Says:

    It easily follows from the union-closed sets conjecture, and existence of a subset of size k
    that intersects at least (1-2^{-k})n sets can be shown by induction on k.
    For k=1 the conjecture allows to find an element x such that at most n/2 sets are “bad”
    and not containing x. But the family of these “bad” sets is another union-closed family
    and we can find an element y such that at most half of “bad” sets are “bad-bad”, and not contain y. So at most n/4 sets contain neither x, nor y; we can certainly continue
    by induction for every integers k (restriction from above suggested by Alec is not needed.

    • Alec Edgington Says:

      Good point!

    • Miroslav Chlebik Says:

      But after at most \log_2(n) steps, the set of picked points will dominate all sets of our family and the set of “bad-bad-…-bad” points
      will be already empty; using induction further would be rather vacuous.

  29. yowan maskay Says:

    Gil has ask a question that there is always
    an injection from to such that each set
    in is a subset of its image. I have proof this conjecture so I’ll publis this paper soon.

  30. Jean-Camille d'Ornano Says:

    let \mathcal A be a set of subset of finite set X, and let |\mathcal A| be an odd integer.
    we call Ab(\mathcal A) a subset of X constituted by the abundant elements of X in \mathcal A. By “abundant elements” I mean the element of X that are in at least half the elements of \mathcal A.

    Let \mathcal A be closed for the union,

    conjecture stronger than FUNC:

    X\setminus Ab(\mathcal A)\in\mathcal A\Rightarrow Ab(\mathcal A)\in\mathcal A

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: