FUNC1 — strengthenings, variants, potential counterexamples

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

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

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

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

Strengthenings

1. A weighted version.

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

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

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

2. Another weighted version.

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

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

3. An “off-diagonal” version.

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

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

4. A first “averaged” version.

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

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

5. A second averaged version.

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

This again is false: see Example 2 below.

6. A better “averaged” version.

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

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

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

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

7. Compressing to an up-set.

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

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

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

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

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

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

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

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

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

Examples and counterexamples

1. Power sets.

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

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

2. Almost power sets

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

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

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

3. Empty set, singleton, big set.

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

4. Using strong divisibility sequences.

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

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

5. Duplicating elements.

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

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

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

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

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

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

6. Union-sets.

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

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

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

7. A less obvious construction method.

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

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

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

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

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

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

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

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

This entry was posted on January 29, 2016 at 2:41 pm and is filed under polymath11. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

132 Responses to “FUNC1 — strengthenings, variants, potential counterexamples”

gowers Says:
January 29, 2016 at 3:59 pm | Reply
Something I should have mentioned is methods of creating smaller union-closed families out of given ones. For example, one can remove an element from $X$ and identify sets that become identical. Or one can take an equivalence relation on $X$ and restrict to just those sets that are unions of equivalence classes — this would be a “quotient” family.

This sort of construction could conceivably be useful in an inductive proof. At any rate, in any proof we are free to assume that all such families contain elements with abundance at least 1/2, though that seems too weak to use as an inductive hypothesis — probably induction has more chance of working with attempted averaging arguments.
- gowers Says:
  January 29, 2016 at 4:38 pm
  That use of the word “quotient” wasn’t very intelligent. What I should have said is that a subset of $X$ gives rise to a quotient family (since you have to identify elements of $\mathcal{A}$ ) while a quotient set of $X$ gives rise to a subfamily of $\mathcal{A}$ . So some sort of duality is operating.
Qiaochu Yuan Says:
January 29, 2016 at 5:26 pm | Reply
Logistical comment: have you considered getting a programmer (perhaps a volunteer) to write some more dedicated platform for hosting these discussions? The major weakness of having them in WordPress comments as I see it is that even when voting on comments is possible you can’t sort by votes (as you can on MathOverflow, say). Also there’s an annoying limit to how much you can nest comments, at least as far as I recall.

I think a platform something like Reddit but with LaTeX support would do a better job of bubbling up the best comments to everyone’s attention, to make it easier to follow the discussions casually.
- David Roberts Says:
  January 29, 2016 at 10:03 pm
  The r/math reddit [1] lists some scripts/extensions that one can use there to get the faux-TeX to display properly. I’ve not spent any appreciable time there or tried out the suggestions.
  
  [1] https://www.reddit.com/r/math
- Brendan Murphy Says:
  January 31, 2016 at 4:20 pm
  I made a polymath subreddit: https://www.reddit.com/r/polymathpoject/. I’m not sure I’m allowed to do this, but in the spirit of rapid prototyping I went ahead. I’m happy to hand it over to whoever wants to moderate it.
  
  From what I understand, it might be best to have a subreddit for each polymath project or each “research community” (e.g. I have several email threads going with a bunch of collaborators, but we could use a private subreddit).
  
  This bookmarklet will run mathjax on reddit: http://web.mit.edu/jcalz/Public/Reddit/mathjaxbookmarklet.html
- François Dorais Says:
  February 4, 2016 at 2:48 pm
  The discourse platform would already be a major step up: https://www.discourse.org/
Tobias Fritz Says:
January 29, 2016 at 6:17 pm | Reply
Concerning the first weighted generalization “1.”, the assumption $w(A\cup B)\geq \max\{w(A),w(B)\}$ for all $A, B$ is equivalent to $w(A\cup B)\geq w(A)$ for all $A,B$ , which is simply monotonicity of $w$ . So when $w$ is the normalized counting measure of a set system, this assumption requires the set system to be upper closed! This is clearly not what we’re looking for, and therefore we might want to abandon the first weighted generalization in favour of the second, which indeed specializes to FUNC.
- gowers Says:
  January 29, 2016 at 6:31 pm
  Good point — I’ll edit the post later.
gowers Says:
January 30, 2016 at 9:46 am | Reply
Suppose we want to prove that the average overlap density of a union-closed family $\mathcal{A}$ is always at least 1/2. An obvious idea is to try to use induction. That enables us to assume that the average overlap density of $\mathcal{A}_x$ is at least 1/2 for every $x\in X$ . But it actually allows us to assume more. We can define the average overlap density with respect to any probability measure we like on $X$ , and the duplication procedure shows that we are forced to prove the result for all such measures, so we end up with a stronger inductive hypothesis that does not come at the cost of a stronger result that needs to be proved with the help of that hypothesis.

So the inductive hypothesis would be something like that for every $x$ and every probability measure $\mu$ on $X$ that gives non-zero probability to all the elements of $X$ , the average overlap density of $\mathcal{A}_x$ with respect to $\mu$ is at least 1/2.

So far so good. Where I don’t have an idea is in how to use the hypothesis that $\mathcal{A}$ is union closed. It has to come in somewhere. But perhaps the right way to work that out is to try to carry out the above proof for an arbitrary set system $\mathcal{A}$ (which of course makes the result completely false) and then see what extra hypotheses are needed to make it work. Maybe one can identify some minimal hypotheses and the conjecture that those hold for union-closed families.

Of course, this average-overlap-density conjecture may very well be false, but in that case maybe pursuing an attempt like the above could lead to a way of constructing a counterexample.
- gowers Says:
  January 30, 2016 at 11:23 am
  Here’s a brief indication of why the average overlap density of $\mathcal{A}$ might be hard to express in terms of the average overlap densities of the $\mathcal{A}_x$ . The average overlap density of $\mathcal{A}_x$ is roughly speaking the average overlap of a random set $B\in\mathcal{A}$ with a random set $A\in\mathcal{A}$ given that both $A$ and $B$ contain $x$ . When we average that over $x$ (possibly with some weighted average) we are still calculating some kind of average overlap density but now we are conditioning on the event that $A$ and $B$ both contain some random element $x$ . But one would expect this to increase the expected density of the overlap of $A$ and $B$ . Thus, knowing that the average overlap densities of the $\mathcal{A}_x$ are large does not seem sufficient to obtain that the average overlap density of $\mathcal{A}$ is large.
  
  It may be possible to get round this problem somehow. For example, the information that all the sets in $\mathcal{A}_x$ contain $x$ should enable us to say something stronger about the average overlap density of $\mathcal{A}_x$ than that it is at least 1/2. Indeed, there are two natural set systems to consider here: one is $\mathcal{A}_x$ and the other is $\mathcal{A}_x'=\{A\setminus\{x\}:A\in\mathcal{A}_x\}$ . If $\mathcal{A}_x'$ has average overlap density at least $1/2$ , then $\mathcal{A}_x$ should have average overlap density a bit bigger than this.
Alec Edgington Says:
January 30, 2016 at 11:34 am | Reply
I’ve done some more experimentation with Igor’s conjecture (7 above), this time following Tim’s suggestion of starting with a random upward-closed family and successively removing random abundant elements from random sets until one loses the desired property (or finds a counterexample). There are several tweakable parameters here, of course. But it seems difficult with this method to get the maximum abundance of the smaller set anywhere near $\frac12$ while maintaining the property.
- Alec Edgington Says:
  January 30, 2016 at 5:15 pm
  That’s not quite correct: it is easy to get the maximum abundance close to $\frac12$ by taking $n = \lvert \mathcal{A}\rvert = \lvert \mathcal{B}\rvert$ close to $2^m$ where $m$ is the size of the ground set. Then $\mathcal{A}$ and $\mathcal{B}$ approach the power set, and the maximum abundance approaches $\frac12$ . But I’ve found no counterexamples to the conjecture.
Tom Eccles Says:
January 30, 2016 at 12:34 pm | Reply
In the hunt for a strengthening amenable to induction, I really want to combine strengthenings 3 (off-diagonal) and 6 (average overlap density). It seems to me that there are two issues that immediately arise with an induction argument where we split the cube into the sets contain x and the sets not containing x:

1) The property of “having an abundant element” doesn’t play nicely with the split. If $\mathcal A'_x = \{A\setminus\{x\}:A\in \mathcal A_x\}$ and $\mathcal A_{\bar x} = \{A\in\mathcal A: x\not\in A\}$ have an abundant element, we know little about abundance in $\mathcal A$ .
2) When we split into $\mathcal A'_x$ and $\mathcal A_{\bar x}$ , the condition of “union-closed” becomes complicated – in fact, it becomes a few off-diagonal statements like $\mathcal A'_x + \mathcal A_{\bar x} \subseteq \mathcal A'_x$ .

2) is the problem that led me to want an off-diagonal conjecture. And 1) could be solved by a suitable averaging strengthening, like average overlap density.
- Igor Balla Says:
  January 30, 2016 at 9:22 pm
  I had the same thought regarding problem 2) a while back, but I didn’t know how to deal with problem 1). It would indeed be interesting to engineer an “off-diagonal” and “averaged” conjecture that we could apply induction to.
- gowers Says:
  January 31, 2016 at 10:16 am
  Maybe a way to tackle the complication of the union-closed property when one splits is to do so head on. That is, perhaps one could take a subset $E\subset X$ and for each $D\subset E$ let $\mathcal{A}_D=\{A\setminus D:A\in\mathcal{A}, A\cap E=D\}$ . Then we could try to work out what properties the set systems $\mathcal{A}_D$ must have. Actually, maybe that’s not so hard: I think we get that $\mathcal{A}_D+\mathcal{A}_{D'}\subset\mathcal{A}_{D\cup D'}$ . That looks as though it might conceivably be a condition one could work with, perhaps by generalizing the original conjecture a lot. Note that if we set $E=X$ , then $\mathcal{A}_D=\{D\}$ if $D\in\mathcal{A}$ and $\emptyset$ otherwise, so in that case the condition above is just the condition that $\mathcal A$ is union closed.
- Tom Eccles Says:
  January 31, 2016 at 3:20 pm
  One idea along these lines that doesn’t work out: I wondered whether $\mathcal A + \mathcal B$ being small meant that one of the average overlap densities $\mathbb E_{A\in\mathcal A, B\in\mathcal B} |A\cap B|/|A|$ and $\mathbb E_{A\in\mathcal A, B\in\mathcal B} |A\cap B|/|B|$ had to be large.
  
  But that’s not true, even for $\mathcal A$ and $\mathcal B$ union-closed. If $Y_1\subset X_1$ and $Y_2 \subset X_2$ , we can take $\mathcal A = \{X_1 \cup Y : Y \subseteq Y_2$ and $\mathcal B = \{X_2 \cup Y : Y \subseteq Y_1$ . The $|\mathcal A + \mathcal B| = 1$ , but both the average overlap densities are very small if the $Y_i$ are much smaller than the $X_i$ .
Uwe Stroinski Says:
January 31, 2016 at 9:35 am | Reply
I have now started to generate intersection closed set systems via strong divisibility sequences. While it was clear from the beginning that we cannot expect to get easy counter examples here I thought that the larger the sets get the closer to a counter example they go. This is false and the reason is quite obvious. I just do not have enough sets in my set system and thus run inside the regime where FUNC is known to be true.

To give you an idea of what is going on. If I take the sets of prime divisors of the first 10,000 numbers I get a system with 6,083 sets with 1,229 elements. Let $\mathcal{A}$ denote the set system and $E$ the set of primes used. The concept of average overlap densitiy should translate like

$\frac{1}{|\mathcal{A}|^2}\sum_{A\in \mathcal{A}\setminus\{E\}} \sum_{B\in\mathcal{A}}\frac{|E|-|A\cup B|}{|E|-|A|}$

If that is true the above set system has average overlap density > 99.8%.

How to proceed? Let me take out (from $\mathcal{A}$ ) the sets that contain elements with the lowest frequency as long as this frequency is less or equal to 1/2. Then I check whether I get a counter example or the empty set. If this is not the case I repeat. Does such an (inductive) approach have a chance to achieve something? In our situation we are ultimately talking about taking numbers from sets and so there might be some (very small) chance that we can describe the algorithm by some sort of sifting procedure.
Polymath10-post 4: Back to the drawing board? | Combinatorics and more Says:
January 31, 2016 at 3:36 pm | Reply
[…] discuss together what directions to peruse. It is a pleasure to mention that in parallel Tim Gowers is running polymath11 aimed for resolving Frankl’s union closed conjecture. Both questions were offered along with […]
Thomas Bloom Says:
January 31, 2016 at 9:22 pm | Reply
Another potential variant/weakening of FUNC:

Let $\mathcal{A}$ be a union-closed family of $m$ sets, and define the abundancy of a set of elements to be the proportion of sets of $\mathcal{A}$ which contain all elements of that set.

FUNC says that some set of size $1$ has abundancy at least $1/2$ , which trivially implies that, for every $k\leq \log_2 m$ , there exists some $k$ -set which has abundancy at least $1/2^k$ .

Let $k$ -FUNC be this generalised statement, so that regular FUNC is $1$ -FUNC, and we conjecture that $k$ -FUNC holds for all union closed families with at least $2^k$ sets. Note that the other extremal case, when $k=\log_2m$ , is trivially true.

There are a number of possible ways to fiddle with this setup to produce weaker, more asymptotic, statements. For example, how about the following family of conjectures.

Fix a decreasing function $F:\mathbb{N}\to (0,1]$ . For every $k$ and union-closed family of at least $F(k)^{-1}$ sets some $k$ -set has abundancy at least $F(k)$ .

FUNC is then equivalent to this statement with $F(k)=2^{-k}$ . As a weakening, can this conjecture be established with any function such that $F(k)\to 0$ as $k\to\infty$ ?
- Alec Edgington Says:
  February 1, 2016 at 8:46 pm
  I like this $k$ -FUNC conjecture. It seems a natural generalization, and a little experimentation with random union-closed families suggests it stands a chance of being true.
- Alec Edgington Says:
  February 2, 2016 at 8:11 am
  Just as for strengthening 6 above, one could recklessly strengthen this further to the conjecture that if you choose a random $A \in \mathcal{A}$ with $\lvert A \rvert \geq k$ and a random $k$ -element subset $S \subseteq A$ , the number of $B \in \mathcal{A}$ containing $S$ is at least $\lvert \mathcal{A} \rvert / 2^k$ on average. This is equivalent to the statement that $\mathbb{E}_{A \in \mathcal{A}, \lvert A \rvert \geq k} \mathbb{E}_{B \in \mathcal{A}} \binom{\lvert A \cap B \rvert}{k} / \binom{\lvert A \rvert}{k} \geq 2^{-k}$ .
Thomas Says:
February 1, 2016 at 6:36 am | Reply
Does anyone know where to find the article by Sarvate and Renaud on the conjecture? Or, more specifically, what is the counter-example they gave to 3 element ground set case?
- Anonymous Says:
  February 1, 2016 at 8:05 am
  I could not find it also but I believe the example you look for is also on Poonen’s paper in the non-theorems section
- Alec Edgington Says:
  February 1, 2016 at 8:57 am
  Tried to post the example but something went wrong. It is also quoted here: http://mathoverflow.net/q/228124
- gowers Says:
  February 1, 2016 at 9:46 am
  Since the ground set in this example has seven elements, it can’t be the set system that Thomas Bloom obtains by putting together two power sets using construction method 7. It would be good to have it clarified exactly what the relationship between these two examples is. In particular, is the exact example of Sarvate and Renaud (as listed on mathoverflow) obtainable by a nice construction method?
- Alec Edgington Says:
  February 1, 2016 at 10:13 am
  Which example do you mean when you say it has a ground set of 7 elements? Is this in Poonen’s paper?
  
  The survey article (on p.15) describes a general construction for a UC family with a $k$ -element set none of whose elements are abundant. I haven’t checked whether this gives the Sarvate–Renaud example for $k = 3$ (but it does give an example with 9 elements).
- gowers Says:
  February 1, 2016 at 12:42 pm
  Oops, sorry, I meant the one on Mathoverflow, which has nine elements in its ground set.
- Thomas Says:
  February 1, 2016 at 4:05 pm
  Actually, never mind, I worked that one out. I’m now working on the idea of induction on the original problem. If we have a family of union closed sets F with one element x in at least half of them, we can extend this to a different set G such that if S is in F then either S or SU{y}, or both, are in G, and make sure that G is union closed. All that needs to be shown is that the number of sets in G containing both x and y is greater than the number of sets containing neither of them, and the induction will be complete. Unfortunately, I don’t think that last step will be that easy to prove (or even true).
Tobias Fritz Says:
February 1, 2016 at 1:29 pm | Reply
Here’s another idea at a generalization that somebody else might be able to shoot down. As explained in the survey, one way to look for a proof of FUNC is to find $x$ and an injective map from $\mathcal{A}_{\bar{x}} = \{A\in\mathcal{A}\:|\: x\not\in A\}$ to $\mathcal{A}_x$ .

Now I wonder whether it is always possible to find such an injection $f:\mathcal{A}_{\bar{x}}\to\mathcal{A}_x$ which in addition preserves unions, i.e. which satisfies $f(A\cup B) = f(A)\cup f(B)$ . It’s easy to see that this is indeed the case in the examples 1. to 3. of the original post, is unaffected by 5. (duplicating elements), and also invariant under the union-sets construction 6., at least in the case of disjoint ground sets.

In terms of the lattice formulation of the survey, I’m asking whether one can always find a meet-preserving map $[a)\to L\setminus[a)$ . The proof of Theorem 3, which shows that FUNC holds for all lower semimodular lattices, proceeds via constructing the injection $x\mapsto x\wedge b$ . This trivially preserves meets.
- Tobias Fritz Says:
  February 1, 2016 at 1:42 pm
  Also the Sarvate-Renaud example has a union-preserving injection: the union-presering map $A\mapsto A\cup\{4,5,8,9\}$ injects $\mathcal{A}_{\bar{4}}$ into $\mathcal{A}_4$ .
  
  Inspired by this, here’s a further strengthening: does there always exist $x$ and $B\in\mathcal{A}$ with $x\in B$ such that the map
  $\mathcal{A}_{\bar{x}}\to\mathcal{A}_x,\qquad A\mapsto A\cup B$
  is injective?
  
  Now this certainly looks much too strong to be true, doesn’t it…?
- gowers Says:
  February 1, 2016 at 3:14 pm
  It certainly does. But it would be very nice to have a counterexample, given that the recipes in the post don’t work. (Of course, I’d settle for a proof …)
- Uwe Stroinski Says:
  February 1, 2016 at 3:51 pm
  Do we know a small example of a lattice that is not lower semimodular ?
- Tobias Fritz Says:
  February 1, 2016 at 4:12 pm
  The smallest nonmodular lattice is $N_5$ : https://en.wikipedia.org/wiki/Lattice_%28order%29#/media/File:N_5_mit_Beschriftung.svg
  It’s easy to see $N_5$ isn’t semimodular either. But it’s also not a counterexample to my strong conjecture. In its lattice version, the conjecture would state that there exists a join-irreducible element $a$ and a lattice element $b$ such that $x\mapsto x\wedge b$ is an injection from $[a)$ into $L\setminus[a)$ . To see this for $N_5$ , just take $a$ and $b$ as labelled in the picture. (I’m using the notation from the survey, where $L$ is the lattice and $[a) = \{x\in L|x\geq a\}$ the upper set.)
  
  I don’t know any less trivial examples. As far as I understand, semimodularity of a lattice (very) roughly means that its Hasse diagram contains plenty of diamonds and that it permits a ‘dimension function’ stratifying the Hasse diagram into ‘levels’. So it might help to come up with lattices that don’t have these features.
- gowers Says:
  February 1, 2016 at 5:17 pm
  An attempt at a counterexample. In Polymath spirit I’ll start writing this comment before finding out whether it has any chance of working. Let’s just take all subsets of $\{1,2,\dots,n\}$ of size $n-k$ , where $k$ is some fairly small number like 2. Let’s try $k=2$ . Without loss of generality $x=1$ . Then there are $n-1$ sets in $\mathcal{A}$ that do not contain $x$ . Hmm, this fails miserably since we can take $B=\{x\}$ . What on earth made me think it could possibly work?
  
  I wanted to exploit the fact that the union of two very large sets is almost always $X$ . Here’s a second attempt. Take a random bunch of quite a lot, but not too many, sets of size $k$ , and let $\mathcal{A}$ consist of their complements and all unions of their complements. Let $\mathcal{K}$ be the collection of $k$ -sets.
  
  For a set $B$ to satisfy the conclusion of the strengthened conjecture, we need in particular that $(X\setminus K)\cup B$ is a union of sets of the form $X\setminus K'$ for every $K\in\mathcal{K}$ . That is, we need $K\setminus B$ to be an intersection of sets in $\mathcal{K}$ for each $K\in\mathcal{K}$ . For the injectivity property we need the sets $K\setminus B$ to be distinct.
  
  Suppose, in an attempt to make that hard to achieve, we take $\mathcal{K}$ to be a Steiner triple system. That is, every pair of elements of $X$ is contained in exactly one set in $\mathcal{K}$ . If we take $B$ to be a singleton $\{x\}$ , then some of the sets $K\setminus B$ are pairs, and no pair is an intersection of sets in $\mathcal{K}$ . If we take $B$ to be a pair $\{b,b'\}$ , then at most one set will contain $B$ , so there will be many sets that contain $b$ but not $b'$ , so again there will be many sets $K\setminus B$ that are pairs, and so not intersections of sets in $\mathcal{K}$ .
  
  What if $B$ is quite a lot bigger? Then there is a significant danger that we will be able to find some $x\in X$ and elements $b_1,b_2,b_3,b_4\in B$ such that $\{x,b_1,b_2\}$ and $\{x,b_3,b_4\}$ both belong to $\mathcal{K}$ .
  
  That’s not exactly a proof, but I think it might be an idea worth pursuing.
- gowers Says:
  February 1, 2016 at 5:22 pm
  Maybe it’s easier than I thought. We have problems if there is ever a set $K\in\mathcal{K}$ such that $|K\cap B|=1$ , since then $K\setminus B$ is a pair. But in that case if we look at all the sets that contain some element $x\notin B$ , we find that their union is all of $X$ (since we must cover each pair $xy$ ) and they all intersect $B$ either in a set of size 2 or an empty set. Also, they are disjoint apart from their intersection at $x$ . So we get exactly the situation I described when I asked about what happens when $B$ is quite a lot bigger.
  
  So I think this is a counterexample to the ludicrously strong conjecture, but as always there’s at least a 40% chance that I’ve made a silly mistake, as I have not checked this argument carefully.
- gowers Says:
  February 1, 2016 at 9:11 pm
  I suppose I should also check whether this example disposes of the first conjecture. So let $x\in X$ . Then looking at complements, we would like to find an injection from the sets in $\mathcal K$ that contain $x$ to the sets in $\mathcal K$ that don’t contain $x$ , and this injection needs to preserve intersections.
  
  Now the intersection of two sets that contain $x$ is just $\{x\}$ , so if $|X|=2m+1$ , then this says that we need to find $m$ sets in $\mathcal{K}$ none of which contain $x$ and all of which have the same intersection. That intersection can’t be $\emptyset$ because we don’t have $3m$ elements to play with. It can’t be a singleton because we don’t have $2m+1$ elements to play with. It can’t be a pair because no pairs occur as intersections. And it can’t be a triple because no triple occurs as an intersection (of distinct sets in $\mathcal K$ , that is).
  
  So I think this example shows that even the first conjecture is false, which suggests that finding a “structural” proof may be hard.
- Tobias Fritz Says:
  February 2, 2016 at 8:48 am
  Wow! I’ve tried to walk through these arguments in the case of the Fano plane as the smallest nontrivial Steiner triple system. Confusingly, I seem to have found that the Fano plane *does* satisfy even the ludicrously strong conjecture. Following your idea, the intersection-closed set system consists of the 7 Fano lines, the 7 vertices and the empty set. When I say ‘set’ in the following paragraph, I’m referring to one of these.
  
  In terms of the standard way of drawing the Fano plane, suppose that the rare element $x$ is the central vertex. Then there are four sets that contain $x$ , namely the three interior lines and $\{x\}$ itself. By taking the intersection with the circular Fano line, we map these four sets to sets that don’t contain $\{x\}$ in an injective manner, namely to three vertices plus the empty set. This verifies the ludicrously strong conjecture. Or am I just being dense…?
- gowers Says:
  February 2, 2016 at 12:15 pm
  The density was entirely mine. I was unthinkingly assuming that each triple in $\mathcal K$ would have to map to a triple in $\mathcal K$ , but it can map to a singleton, as your counter-counterexample shows. However, I think my basic idea may not be completely dead. I’ll start a separate comment thread below and have another try.
Thomas Bloom Says:
February 1, 2016 at 3:17 pm | Reply
I agree that, put like that, your second conjecture seems too strong to be true, but I can’t find a counterexample.

if this strengthened version were true, however, it would fix the gap in the argument I had on the last blog post, so it would imply the strengthened FUNC with arbitrary weight functions (i.e. version 2 in this blog post).
- Thomas Bloom Says:
  February 1, 2016 at 4:27 pm
  This was, of course, intended to be a reply to Tobias Fritz’s comment above.
gowers Says:
February 2, 2016 at 12:45 pm | Reply
Here is another attempt to disprove Tobias Fritz’s strengthenings of FUNC. I shall take complements and discuss the following equivalent problems.

1. Let $\mathcal{A}$ be an intersection-closed set system. Then there exists $x$ and an intersection-preserving injection $\phi$ from $\mathcal{A}_x$ to $\mathcal{A}_{\overline x}$ .

2. As 1 but with the added conclusion that $\phi$ is of the form $A\mapsto A\cap B$ for some fixed $B$ .

I thought I had shown that a Steiner triple system is a counterexample to 1 (and therefore 2), but my proof was wrong, because I accidentally assumed that triples had to map to triples. Now I want to explore what happens if I take a quadruple system — that is, a collection of 4-sets that covers each 2-set exactly once. (If this basic approach works, I think it should be possible to get a similar proof that doesn’t require results from design theory by taking suitable random collections of $k$ -sets and taking their intersections. But I may as well try to keep the proof simple by relying on whatever I want — even Keevash’s big theorem if necessary.)

What does $\mathcal{A}_x$ look like in this case? Well, we know that each pair that contains $x$ is in exactly one 4-set from $\mathcal{A}$ , so this tells us that the sets $A\setminus\{x\}$ with $A\in\mathcal{A}_x$ of size 4 form a partition of $X\setminus\{x\}$ . Also, $\mathcal{A}_x$ contains all sets of the form $\{x,y\}$ , and the singleton $\{x\}$ .

I would now like to argue that if $\phi:\mathcal{A}_x\to\mathcal{A}_{\overline x}$ preserves intersections, then $\{x\}$ cannot map to the empty set. So let’s assume for a contradiction that it does.

Observe first that if $A=\{x,y,z,w\}$ is a quadruple in $\mathcal{A}_x$ , then the pairs $xy,xz,xw$ map to disjoint non-empty sets. Moreover, these sets must be subsets of $\phi(A)$ . Since $\phi(A)$ must be a quadruple if it has size at least 3, it must be a quadruple. (This is the key new ingredient to the argument.)

At this point, letting $n=|X|$ , we have $(n-1)/3$ quadruples in $\mathcal{A}_x$ that must map to disjoint quadruples in $X\setminus\{x\}$ , which requires that $4(n-1)/3\leq n-1$ , which ain’t gonna happen. (I think we can allow ourselves not to worry about the case $n=1$ .)

So I think we now have that $\{x\}$ must map to a non-empty set $S$ . Again let’s think about what must happen to the quadruples in $\mathcal{A}_x$ . For any two of these, the intersection is $\{x\}$ , so we need to find $(n-1)/3$ sets in $\mathcal{A}_{\overline x}$ such that any two of them intersect in $S$ .

If $S$ is a singleton $\{y\}$ and all the sets we take are quadruples, then we don’t have enough elements (since we can’t use $x$ or $y$ for the remaining three elements). What happens if some quadruple $A$ in $\mathcal{A}_x$ maps to a pair $B$ that contains $y$ ? That looks to me like a problem because the three pairs in $A$ that contain $x$ must map to distinct subsets of $B$ that properly contain $y$ , and we don’t have that. So I think quadruples have to go to quadruples still.

Let me just check whether that is a general lemma. My claim is that (without assuming that $\{x\}$ goes to the empty set) quadruples have to go to quadruples. The idea is that if $A=\{x,y,z,w\}$ is a quadruple in $\mathcal{A}$ , then the images of the sets $xy, xz, xw$ and $x$ (omitting the set brackets because I’m getting tired of writing them) have to go to distinct subsets of $\phi(A)$ and if $|\phi(A)|\leq 2$ then we don’t have an intersection-preserving bijection that does the job.

However, I’m not out of the woods quite yet. I think I’ve shown that $S$ can’t be empty or a singleton, but what if it is a pair? Ah, that is completely impossible, since I can find at most one quadruple in $\mathcal{A}$ that contains $S$ .

OK, as cranks like to say, if you think this is wrong, then can you find a counter-counterexample? That is, can you exhibit a Steiner $(4,2)$ -system $\mathcal A$ and an intersection-preserving injection from some $\mathcal{A}_x$ to $\mathcal{A}_{\overline x}$ ?
- Tobias Fritz Says:
  February 2, 2016 at 2:39 pm
  I would perfectly agree with this argument, if it wasn’t for the statement “Also, $\mathcal{A}_x$ contains all sets of the form $\{x,y\}$ “. How is this compatible with working with a Steiner $(4,2)$ -system…?
  
  In fact, I suspect that the projective plane $PG(2,3)$ over the field with three elements is a counter-counterexample. It’s a Steiner $(4,2)$ -system since any two points lie on a unique line, and all lines are $PG(1,3)$ ‘s, so that they contain four points. Now for any point $x$ , the resulting $\mathcal{A}_x$ is also a $PG(1,3)$ , meaning that it consists of four lines that only intersect in $x$ . Now choose any other line that doesn’t contain $x$ . Intersecting the sets in $\mathcal{A}_x$ with this line results in the desired map $\phi:\mathcal{A}_x\to\mathcal{A}_{\bar{x}}$ , which apparently verifies the ludicrously strong conjecture in this case.
  
  For what it’s worth, there’s an illustration of $PG(2,3)$ on p.42 of this beautiful book: http://www.uwyo.edu/moorhouse/handouts/incidence_geometry.pdf
  
  The gist of why this seems to work is probably that $\mathcal{A}_x$ doesn’t have any interesting order structure: all the nontrivial sets in there are incomparable. In other words, the lattice for which we’re probing the conjecture has a height of only 4 (bottom, top, a level of atoms and a level of coatoms), and this seems to be too small.
  
  Thinking along these lines, it might be better to consider lattices of height 5, such as the face lattice of a 3-dimensional polytope. Consider e.g. the dodecahedron: simply by visual inspection, I have the impression that the ludicrously strong conjecture can’t possibly hold for its face lattice, but I haven’t yet found a rigorous and complete proof.
  
  Of course, any pointers to errors in my reasoning will be very welcome.
- Tobias Fritz Says:
  February 2, 2016 at 2:41 pm
  To clarify my question about the sets of the form $\{x,y\}$ : I don’t understand how those are supposed to arise as intersections of blocks in the Steiner system.
- gowers Says:
  February 2, 2016 at 3:04 pm
  Oh dear, I need to get my brain properly into gear before writing out long arguments. This time I somehow fooled myself into thinking that the pairs were all in $\mathcal{A}$ because they are all covered, despite making crucial use of the fact that they were not intersections of sets in the system later on in the argument.
  
  I still feel that something along these lines ought to work though. Back to the drawing board.
gowers Says:
February 2, 2016 at 3:26 pm | Reply
I’m not necessarily going to finish this comment, but let me see whether I can prove that a Steiner $(r,s)$ -system $\mathcal K$ works for some $r,s$ . For now I won’t specify the values of $r$ and $s$ .

Since each $s$ -set is covered exactly once, the number of sets in $\mathcal K$ is $\binom ns/\binom rs$ . Given any $(s-1)$ -set $E$ , let $A\in\mathcal K$ contain $E$ and let $u\notin A$ . Then $E\cup\{u\}$ must be covered by some set $B\in\mathcal{K}$ , which gives us two sets in $\mathcal K$ that intersect in $E$ . So the intersection closure of $\mathcal K$ is, if I’m not much mistaken (a highly non-trivial assumption) $\mathcal K$ together with all sets of size at most $s-1$ . Let this intersection closure be $\mathcal A$ .

Now let $\phi$ be an intersection-preserving injection from $\mathcal{A}_x$ to $\mathcal{A}_{\overline x}$ .

From my last, failed, attempt, it seems like a good idea to try to prove that the image of a set of size $r$ must have size $r$ . So let $A\in\mathcal{A}_x$ have size $r$ .

We know that if $B\subset A$ belongs to $\mathcal{A}_x$ , then $\phi(B)\subset\phi(A)$ . Therefore, we have an injection from subsets of $A$ of size at most $s-1$ that contain $x$ to proper subsets of $\phi(A)$ . There are at least $\binom {r-1}{s-2}$ subsets of the first kind. If $|\phi(A)|\leq s-1$ , then there are at most $2^{s-1}$ sets of the second kind. So this is impossible if $\binom {r-1}{s-2}>2^{s-1}$ , something we can easily arrange to happen by choosing appropriate $r$ and $s$ .

As a sanity check, let me see what happens with $r=4$ and $s=2$ . There I get $\binom 30$ versus $2^1$ and the condition does not hold, which is reassuring …

So now I know (in the “know until Tobias points out my stupid mistake” sense) that the $r$ -sets in $\mathcal{A}_x$ have to map to $r$ -sets in $\mathcal{A}_{\overline x}$ . Moreover, their images must all contain the set $\phi(\{x\})$ .

I’ll think for a moment and then continue.
- gowers Says:
  February 2, 2016 at 3:56 pm
  I’m now going to make an additional assumption about $\mathcal K$ , which is that for each $x$ we can find sets in $\mathcal K$ with union $X$ and with all intersections equal to $\{x\}$ . This doesn’t follow from the definition of a design, but my guess is that it is achievable if one runs Keevash’s argument carefully or modifies it slightly.
  
  In that case, the arguments I gave in my wrong proof show that $\phi(\{x\})$ cannot be empty or a singleton, since in both cases one has a system of disjoint sets with cardinalities that add up to something too big. (In the first case we get $(n-1)/(r-1)$ disjoint subsets of $X\setminus\{x\}$ of size $r$ , and in the second case we get that number of disjoint subsets of a set $X\setminus\{x,y\}$ of size $r-1$ .)
  
  But I still need to rule out $\phi(\{x\})$ having cardinality greater than 1, which is no longer trivial since we have sets in the system of sizes up to $s-1$ .
  
  Let’s suppose that $\phi(\{x\})=B$ is a set of size 2. There are $\binom{n-1}{s-2}$ sets of size $s-1$ that contain $x$ , and these must inject to sets in $\mathcal{A}_{\overline x}$ that contain $B$ . If they map to sets of size $s-1$ , then we have problems because $\binom{n-2}{s-3}<\binom{n-1}{s-2}$ . They can’t map to sets of size less than $s-1$ because all their subsets need to map nicely to subsets as well.
  
  The one case I don’t yet see how to rule out is that some sets of size $s-1$ map to sets of size $r$ . But I think that should be impossible. I’ll post this comment and think further.
- gowers Says:
  February 2, 2016 at 4:03 pm
  Ah, that’s easily shown to be impossible. If a set of size $s-1$ maps to a set of size $r$ , then there is nowhere for any superset of size $r$ to map to.
  
  So I now have yet another argument that feels right but may well be wrong. In this case, I have made a further assumption about the Steiner system but (i) I think that systems satisfying this further assumption probably exist and (ii) if this proof is correct, then probably one can find another proof that avoids this extra assumption, which I made mainly out of laziness.
- gowers Says:
  February 2, 2016 at 4:21 pm
  I forgot to mention that if $B$ above has size bigger than 2, then things get even worse, so I think the argument is complete. However, I won’t feel happy about it unless someone OKs it.
- Tobias Fritz Says:
  February 2, 2016 at 5:01 pm
  Very nice! Now I don’t see anything wrong with the argument. As far as I can see, it should be possible to choose $s=3$ and $r=5$ . So what is the smallest $n$ for which a $(3,5)$ -Steiner system exists? The following webpage has examples with $n=17$ and $n=26$ . Does anyone know interesting ways of constructing these?
- Tobias Fritz Says:
  February 2, 2016 at 5:02 pm
  Sorry, I forgot the link: https://www.ccrwest.org/cover/steiner.html
- gowers Says:
  February 2, 2016 at 5:11 pm
  Phew!
- gowers Says:
  February 2, 2016 at 5:17 pm
  I’ve just checked the example with $n=17$ and luckily it satisfies the extra condition, since it contains the sets {1,2,3,7,14}, {1,4,9,11,13}, {1,5,12,16,17} and {1,6,8,10,15} and is cyclically symmetric.
- Tobias Fritz Says:
  February 2, 2016 at 5:27 pm
  For another concrete example, projective 3-space over $\mathbb{F}_2$ should work, with $\mathcal{K}$ being the collection of projective planes (=Fano planes). I think that this would have parameters $s=3$ (three points determine a unique plane), $r=7$ (size of the Fano plane), and $n=(2^4-1)/(2-1)=15$ . Off the top of my head I’m not totally sure about the extra condition, though.
  
  In any case, I’m glad that the conjecture seems to be resolved! But unfortunately, since the intersection-closed families constructed this way feel quite ‘bottom-heavy’, this doesn’t look like a good way to look for counterexamples to FUNC itself, or does it?
- gowers Says:
  February 2, 2016 at 6:28 pm
  I thought about that earlier today. I think it should probably be possible to prove that no Steiner $(r,s)$ -system can work and have done a few calculations with that in mind. It would probably be a worthwhile thing to complete them, just to make sure. At some point soon I’ll try to say where I got to.
  
  I also wonder whether it might be possible to prove a weakening of FUNC where one assumes that the set system has quite a lot of symmetry — an obvious hypothesis being that its symmetry group acts transitively on the ground set. Is there some easy argument that does this case?
  
  The two questions are loosely related, since a design, though not necessarily symmetric, is at least highly balanced. Maybe one could prove a fairly general result that FUNC is true for sufficiently balanced systems, for some suitable notion of “balanced”.
- Tobias Fritz Says:
  February 3, 2016 at 6:49 am
  Forget about projective 3-space (in my last comment): it’s not even a Steiner system! It’s true that every triple of points is contained in a plane, but this plane is not unique if the points are collinear…
- Tobias Fritz Says:
  February 3, 2016 at 12:35 pm
  If we want to take this a bit further still, we could try to find examples in which not even an injective and /monotone/ map $\phi : \mathcal{A}_{\bar{x}}\to\mathcal{A}_x$ exists.
  
  Tim’s argument already goes quite some way to proving this: the only case for which he actually needs the preservation of unions–as opposed to mere monotonicity–is in the paragraph where he shows that $\phi(\{x\})$ can’t be empty or a singleton.
mixedmath Says:
February 2, 2016 at 5:38 pm | Reply
On sort of a whim, I decided to program a naive random union-closed family generator and see if it led me to anything interesting. My initial process is very simple, but it does work. I start by choosing a universe (i.e. choosing an $n$ , and having everything live in the integers from $1$ to $n$ ), a probability parameter $p$ , and a number $m$ of sets. Then I create these $m$ sets in the following (possibly too simple) way: each integer up to $n$ has probability $p$ of being included. Finally, I take the closure under unions of the family.

I’ve learned a few things, and some thoughts have jumped out at me. I think I’d like to carry on this experiment forward a bit and implement checkers on some of the proposed strengthenings mentioned above [if possible].

But one thing is very obvious to me — this is not a good way of generating “interesting” union-closed families, and almost always the resulting families have over half of the elements as being in at least half of the sets. I’m not quite sure what to change yet, but it’ll be hanging around my thoughts.
- gowers Says:
  February 2, 2016 at 6:48 pm
  I agree that it would be very interesting to try to come up with a random model that produces “promising” examples. One feature I would expect such a model to have is that if you take a minimal generating set $A_1,\dots,A_k$ , then there are many coincidences amongst the unions of the $A_i$ , so that in some sense we don’t get too many large sets. This seems unlikely to happen when the $A_i$ are chosen purely randomly, but perhaps there is some clever way of choosing a random object and then converting it deterministically into a “low-dimensional” system, or something like that.
- gowers Says:
  February 3, 2016 at 11:00 am
  To be a little more explicit about this, let’s suppose that $A_1,\dots,A_k$ is a generating set for a set-system $\mathcal A$ . That is, $\mathcal A$ consists of all unions (including the empty union) that can be formed out of the $A_i$ .
  
  Suppose now that all those unions are distinct. In that case, it is trivial that $\mathcal{A}$ has an element in half the sets. Indeed, we have $2^k$ different unions, and each $A_i$ is involved in half of them, so every element of every $A_i$ is in at least half the unions.
  
  So to have any hope of creating a counterexample to FUNC, one must find a generating set with the property that many unions coincide.
  
  Can we be slightly more precise about this? For each set $E\subset\{1,\dots,k\}$ , write $A_E$ for the set $\bigcup_{i\in E}A_i$ . And let’s say that $E\sim F$ if $A_E=A_F$ . Then the number of sets in $\mathcal{A}$ that contain $A_i$ is the number of equivalence classes that contain a representative $E$ with $i\in E$ . And FUNC is satisfied if for some $i$ this is at least half the total number of equivalence classes.
  
  It’s worth making the trivial remark that there exist equivalence relations for which no such $i$ exists. For example, if each $A_i$ is the singleton $\{i\}$ , we could define $E$ and $F$ to be equivalent if they are either equal or both have size at least $2$ .
  
  Actually, I’ve just noticed that this equivalence relation can occur. Let $A_i=\{1,2,\dots,k\}\setminus\{i\}$ . Then any two distinct $A_i$ have union $\{1,2,\dots,k\}$ , so each $A_i$ is contained in precisely two sets in $\mathcal{A}$ .
  
  So what I needed to say earlier was not just that there should be many coincidences, but also that the sets should be small. To put it another way, I’ve just given a simple counterexample to the following strengthening of FUNC: every generating set of a union-closed family contains a set that is a subset of at least half the sets in $\mathcal{A}$ .
  
  So it seems as though what we’re looking for is lots of coincidences, but for those coincidences to occur for a “clever” reason, and not just because the sets we have taken are very large.
- Alec Edgington Says:
  February 3, 2016 at 11:54 am
  I’m not quite convinced that ‘to have any hope of creating a counterexample to FUNC, one must find a generating set with the property that many unions coincide’. In the extreme case where they’re all disjoint, we get (effectively) the power set, but is the power set a ‘worst case’ or a ‘best case’? In terms of minimizing the maximum abundance, it’s (conjecturally) optimal. It’s not clear (to me) whether counterexamples are more ‘likely’ in relatively small or large families (though there are results that rule out both very small and very large ones).
- Tobias Fritz Says:
  February 4, 2016 at 12:30 pm
  In order to produce better random examples, how about starting with a fixed set of candidate generators $\mathcal{G}\subseteq 2^X$ , and then choosing randomly for every $A\in\mathcal{G}$ independently whether it will become an actual generator or not? For example, one could take $\mathcal{G}$ to consist of the 3-sets associated to a finite group as suggested in the other thread: https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154131
  Similarly, one could choose some finite group $G$ and randomly select a bunch of 3-sets $\{x,y,z\}$ (with each element in the corresponding copy of $G$ , and $xyz=e$ ). At the moment I find it hard to say whether this is likely to generate better examples or not.
  
  It has also been suggested to me by Benjamin Matschke to look for counterexamples to FUNC in terms of the probabilistic method. Along these lines, I’ve been wondering whether something like the above prescription for generating union-closed families would let us apply the Lovász local lemma to the family of events “ $x$ has abundance at least 1/2″ in order to show that there is positive probability for all $x$ to have abundance less than 1/2.
  
  So far, I don’t know of an interesting way to guarantee the necessary independence conditions on these events (or negative correlation conditions for the lopsided LLL).
- Alec Edgington Says:
  February 4, 2016 at 1:00 pm
  It might be interesting to explore generating random ‘normalized’ examples. These are discussed in section 3.5 of the survey article: a separating union-closed family is normalized if it contains the empty set and its size is one more than the size of its ground set; and FUNC is equivalent to the conjecture that every normalized family includes a basis set of at least half this size (a basis set being one that’s not a union of two other sets in the family). For example, one could generate random candidates by repeatedly adding sets that are just under half the target size and forming the union-closure until one either gets a family of the right size, or exceeds it (in which case start again).
- Tobias Fritz Says:
  February 4, 2016 at 4:47 pm
  Interesting idea! I have implemented essentially this here:
  https://cloud.sagemath.com/projects/da1aee8f-701b-4aa8-bc45-1a0a5e3f0d15/files/random_examples.sagews
  Feel free to play with the program and improve the (very amateurish) code.
  
  After a couple of runs, the smallest separating union-closed families with generators of size less than half of the ground set are as follows: for a ground set of size 15, the smallest family found has size 22; for a ground set of size 21, it’s 28. For all other sizes of the cardinalities the gaps are larger.
  
  For a counterexample to the Salzborn formulation of FUNC, one would need a family whose cardinality is equal to the size of the ground set. My count is off by one with respect to the survey since my families don’t include the empty set.
  
  I think that with a more intelligent selection of the generators these bounds will improve, but I have no good intuition for how low they can eventually get.
- Tobias Fritz Says:
  February 4, 2016 at 5:07 pm
  For finding other ways to randomly generated union-closed families, it may be worth mentioning that every union-closed family has a ‘dual’ description, very much analogous to how every convex polytope has a description as the convex hull of its vertices, or dually as the intersection of a bunch of half-spaces.
  
  Concretely, what I claim is that every union-closed family is equal to the solution set of a bunch of Horn clauses. Here, a Horn clause is an implication looking like this:
  $x\in A\:\Rightarrow y_1\in A\lor\ldots\lor y_k\in A.$
  It’s easy to check that the set of all $A\subseteq X$ that satisfy such a Horn clause is union-closed; more generally, the set of all $A$ ‘s that satisfy a bunch of Horn clauses is union-closed.
  
  The nontrivial part is to show that every union-closed family can be written in this form. If this turns out to be relevant, I can dig into some long forgotten memories and try to explain the details. There’s also these old notes of mine: http://personal-homepages.mis.mpg.de/fritz/2011/horn_formulas.pdf
  The relevant part starts in the middle of p.5. The last page shows that I’ve already been obsessed with FUNC back then 😉
  
  The reason that I’m mentioning this is that it provides another way to generate random union-closed families by randomly generating Horn clauses. However, whether this has the potential to result in more interesting union-closed families is totally unclear to me. Any thoughts?
gowers Says:
February 2, 2016 at 6:44 pm | Reply
One thought I had a little while ago was the following question. Suppose we could find a union-closed family with all abundances at most $\alpha$ for some $\alpha<1/2$ . Might there be some complicated product construction that would allow us to create for each $n$ a new union-closed family with all abundances at most $2^{n-1}\alpha^n$ , and thus to show that if the conjecture itself is false, then so is the weaker conjecture that asks merely for an abundance of at least $c$ for some fixed positive $c$ ? It would be nice if one could, because then it would be sufficient to prove the weaker conjecture.

An obvious product construction is to take two union-closed families $\mathcal A$ and $\mathcal B$ defined on disjoint ground sets and take the union-closure of the collection of sets of the form $A\times B$ with $A\in\mathcal A$ and $B\in\mathcal B$ . But this feels far too naive to work. For obvious reasons, it isn’t easy to find a counterexample, but perhaps one can show that this naive product construction tends to behave in a way that makes it highly unlikely to work.
- Thomas Says:
  February 4, 2016 at 2:58 pm
  I strongly suspect that if the conjecture is false and a construction method for generating a counterexample is found, then it could probably be used to generate union closed sets of arbitrarily small abundance, by continuing to use that construction. However, I don’t think your product construction would work, because just having a set of size x in A implies that one of the elements has abundance at least 1/2^x. So for this product to work, it would somehow have to go back and remove some of the elements.
- gowers Says:
  February 4, 2016 at 4:41 pm
  Ah, that’s a useful remark.
  
  Actually, the most natural “product” of two families $\mathcal A$ and $\mathcal B$ is probably the one where we make the ground sets disjoint and just take $\mathcal A+\mathcal B$ . This has size $|\mathcal A||\mathcal B|$ and is union closed, so the word “product” seems quite appropriate. Of course, it doesn’t change any abundances, so isn’t especially helpful for the conjecture or for the question of what one can deduce if the conjecture is false.
  
  A more complicated version of the construction is to take union-closed families $\mathcal{A}_1,\dots,\mathcal{A}_m$ and a union-closed family $\mathcal K$ with ground set $\{1,2,\dots,m\}$ and then take all possible unions of the form $\bigcup_{i\in K}A_i$ , where $K\in\mathcal{K}$ and $A_i\in\mathcal{A}_i$ for each $i$ .
  
  Suppose that the maximum abundance of an element of $\{1,2,\dots,m\}$ in $\mathcal K$ is $\alpha$ , and the maximum abundance in any of the $\mathcal{A}_i$ is $\beta$ . Then if the ground set of $\mathcal{A}_i$ is $X_i$ and $x\in X_i$ , we get that $x$ is involved in at most $\beta\prod_{i\in K}|\mathcal{A}_i|$ of the sets in $\prod_{i\in K}\mathcal{A}_i$ .
  
  Unfortunately, this looks as though it is not going to give anything interesting, because if all the $\mathcal{A}_i$ are fairly large, this set system hugely favours sets where $K$ is large. I haven’t quite ruled out that it does something useful though. I’ll think a tiny bit and then write another comment.
- Tobias Fritz Says:
  February 5, 2016 at 7:30 pm
  Here’s an even more general ‘fibre bundle’ construction. Suppose that we have a union-closed family $\mathcal{K}$ as well as a family of union-closed families $\mathcal{A}_K$ indexed by $K\in\mathcal{K}$ , and such that for every inclusion $K\subseteq L\in\mathcal{K}$ we have a homomorphism $\phi_{K,L} : \mathcal{A}_K\to\mathcal{A}_L$ , such that $\phi_{L,M}\circ\phi_{K,L} = \phi_{K,M}$ for every double inclusion $K\subseteq L\subseteq M$ . The ground sets are irrelevant.
  
  An element of the resulting combined family, denoted $\int_{\mathcal{K}}\mathcal{A}$ , is defined to be a pair $(K,A)$ consisting of a $K\in\mathcal{K}$ and an $A\in\mathcal{A}_K$ . The ‘union’ of a pair $(K,A)$ with another $(L,B)$ is defined to be $(K\cup L,\phi_{K,K\cup L}(A)\cup\phi_{L,K\cup L}(B))$ . In words: first transport both $A$ and $B$ to their ‘common context’ $K\cup L$ , and then take their union there. It may help to visualize all this in a bundle sort of way, especially since there’s a canonical homomorphism $\int_{\mathcal{K}}\mathcal{A}\to\mathcal{K}$ , which plays the role of the projection to the base space.
  
  Tim’s previous construction is the special case of this where $A_K = \cup_{i\in K} \mathcal{A}_i$ for all $K$ . Oh, and when I said ‘union’, I really meant ‘join’: since the ground sets have been abstracted away, this is really all about join-semilattices. Maybe there is a nice way to implement all this in terms of the ground sets, but I haven’t thought about it.
  
  (Where did this come from? It’s secretly the Grothendieck construction from category theory, which turns a pseudofunctor into an opfibred category, specialized to the case of join-semilattices…)
  
  I haven’t yet thought about what this does to abundances.
- gowers Says:
  February 5, 2016 at 11:26 pm
  I like this construction. It also seems to be closely related to a construction I gave in this comment, which I think makes it possible to carry out your implementation in a way that provides a ground set.
  
  Given your construction above, let $Y$ be the union of all the sets in $\mathcal K$ and let $\mathcal B$ be the union of all the set systems $\phi_{K,Y}\mathcal A_K$ . We may take the ground set of $\mathcal B$ to be some set $X$ that is disjoint from $Y$ . Now take a set system $\mathcal A$ that consists of all sets of the form $\phi_{K,Y}A\cup K$ such that $A\in\mathcal A_K$ . This is union closed, and the map $C\mapsto C\cap X$ is a homomorphism from $\mathcal A$ to $\mathcal K$ .
  
  Conversely, given a union-closed family $\mathcal A$ of subsets of $X\cup Y$ that projects to $\mathcal K$ , let $\mathcal A_K=\{A\subset Y:A\cup K\in\mathcal A\}$ for each $K\in\mathcal K$ . Then … oh wait, this doesn’t seem to work. I don’t think we necessarily have a natural homomorphism from $\mathcal A_K$ to $\mathcal A_L$ when $K\subset L$ . For example, it could be that the only set that contains $L$ is $L\cup Y$ .
  
  OK, so maybe this fibre bundle construction is more specific than just finding a homomorphism to $\mathcal K$ .
- gowers Says:
  February 6, 2016 at 11:01 am
  Maybe I can get round the small difficulty I was having in the previous comment by insisting, in the converse direction, that each $\mathcal A_K$ should contain the set $K$ itself. Then we can define $\phi_{K,L}A$ to be $A\cup L$ .
- Tobias Fritz Says:
  February 7, 2016 at 10:53 am
  “let $\mathcal B$ be the union of all the set systems $\phi_{K,Y}\mathcal A_K$ ”
  
  Since $\phi_{K,Y}\mathcal{A}_K\subseteq\mathcal{A}_Y$ and the union includes the case $K=Y$ itself, I think that we get $\mathcal{B}=\mathcal{A}_Y$ , no?
  
  When all the $\phi_{K,Y}$ ‘s are injective, then what you describe yields a nice concrete implementation of my abstract fibre bundle construction. But maybe it could also be interesting to consider some non-injective $\phi_{K,Y}$ ?
  
  Then you were asking what property characterizes those homomorphisms $\mathcal{A}\to\mathcal{K}$ that arise from the fibre bundle construction, right? That’s an interesting question, and I think that the answer is: it’s precisely those for which for every double inclusion $K\subseteq L\subseteq M$ and every $A\in\psi{-1}(K)$ , $A''\in\psi^{-1}(M)$ with $A\subseteq A''$ in $\mathcal{A}$ there is $A'\in \psi^{-1}(L)$ with $A\subseteq A'\subseteq A''$ . (Think of ‘lifting’ the ‘path’ $K\subseteq L\subseteq M$ in the base space to the total space, given lifts of the endpoints.) In particular, this implies that $\psi$ must preserve meets as well.
  
  The condition is clearly necessary for a homomorphism to arise from the fibre bundle construction. Concerning sufficiency, I again only know how to show this in the abstract (without ground sets), as follows.
  
  Given $\psi:\mathcal{A}\to\mathcal{K}$ , let $\mathcal{A}_K:=\psi^{-1}(K)$ . For $K\subseteq L$ and $A\in\mathcal{A}_K$ , let $\phi_{K,L}(A)$ be given by the meet of all the $A'\in\mathcal{A}_L$ with $A\leq A'$ in $\mathcal{A}$ . (Recall that every finite semilattice is a lattice, so that this meet exists.) It’s straightforward to see that this preserves unions (by virtue of these being least upper bounds). It satisfies the required composition law $\phi_{L,M}\circ\phi_{K,L} = \phi_{K,M}$ on double inclusions due to the assumption on $\psi$ . Applying the fibre bundle construction to this recovers the original $\psi:\mathcal{A}\to\mathcal{K}$ essentially by definition.
  
  (As before, I’ve been abusing set-theoretic notation to talk about join-semilattices.)
  
  I suspect that one can relax the assumed composition law $\phi_{L,M}\circ\phi_{K,L}=\phi_{K,L}$ in the fibre bundle construction to $\phi_{L,M}\circ\phi_{K,L}\geq \phi_{K,M}$ (understood pointwise), and then it’s conceivable that every (surjective) homomorphism $\mathcal{A}\to\mathcal{K}$ arises in this way.
Thomas Bloom Says:
February 3, 2016 at 11:09 am | Reply
Here is, if my calculations are correct, a simpler(?) counterexample to Tobias Fritz’s extreme strengthening, without using Steiner systems (or have I accidentally introduced them in disguise?)

Take the union-closed family generated by the sets $\{1,2,3,4,5,6\}$ , all $2$ -subsets of $\{7,8,9,10\}$ , and the 6 sets $\{1,7,8\}$ , $\{2,7,9\}$ , $\{3,7,10\}$ ,
$\{4,8,9\}$ , $\{5,8,10\}$ , $\{6,9,10\}$ , which has (I think) 119 sets. The elements $1\leq i\leq 6$ are in 52 sets each, and the elements $7\leq i\leq 10$ are in 100 sets each.

Suppose this strong form is true, so there is some $B$ and $x\in B$ such that $A\mapsto A\cup B$ is an injection over all $x\not\in A$ . Without loss of generality, $x=10$ , say. Then $\{7,8\}\cup B,\{8,9\}\cup B,\{7,9\}\cup B,\{7,8,9\}\cup B$ must all be distinct. It follows that $7,8,9\not\in B$ . But every set $B$ which contains $10$ contains at least one of $7,8,9$ .
- Tobias Fritz Says:
  February 3, 2016 at 12:29 pm
  Cool! Trying to take $B$ to be a set outside of the set system doesn’t work either: your argument shows $B\subseteq\{1,2,3,4,5,6,10\}$ , which results in $\{1,2,3,4,5,6\}\cup B$ not belonging to the set system.
- gowers Says:
  February 3, 2016 at 12:36 pm
  I feel bound to ask whether it is possible to describe this example in a less rabbit-out-of-hat way …
- Tobias Fritz Says:
  February 3, 2016 at 2:10 pm
  I think that the example’s structure is as follows: the elements 1 to 6 index the 2-subsets of $\{7,8,9,10\}$ , and this is where the 3-sets come from.
  
  I’ve written some (extremely inefficient!) Sage code for forming the union closure of a given set system. It confirms that the union closure has cardinality 119. I’ll try to quote it below and now move on to drawing some Hasse diagrams for this example.
```
A = [{1,2,3,4,5,6},{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}]

done = False
while done == False:
    newset_found = False
    for i in range(len(A)):
        for j in range(i+1,len(A)):
            candidate_union = A[i].union(A[j])
            already_there = False
            for k in range(len(A)):
                if candidate_union == A[k]:
                        already_there = True
            if already_there == False:
                A.append(candidate_union)
                newset_found = True
    if newset_found == False:
        done = True
            
print len(A)
```
- gowers Says:
  February 3, 2016 at 2:38 pm
  Ah of course.
- Tobias Fritz Says:
  February 3, 2016 at 4:14 pm
  Here’s the complete (and absolutely horrible) Sage code for building union-closed families and drawing Hasse diagrams, applied to Thomas’s example:
  https://cloud.sagemath.com/projects/da1aee8f-701b-4aa8-bc45-1a0a5e3f0d15/files/first%20experiments.sagews
  
  The resulting Hasse diagrams are here:
  http://personal-homepages.mis.mpg.de/fritz/A10bar.svg
  http://personal-homepages.mis.mpg.de/fritz/A10.svg
  
  Now I wonder: can the first diagram be made to fit into the second? This would check my earlier question whether one can at least find an order-preserving injection $\phi:\mathcal{A}_{\bar{x}}\to\mathcal{A}_x$ in the case of Thomas’s example.
- Tobias Fritz Says:
  February 3, 2016 at 5:49 pm
  Did my earlier comment with the link to the Hasse diagrams end up in the spam filter? (Feel free to delete this useless comment.)
- Thomas Bloom Says:
  February 5, 2016 at 9:25 am
  A little late, but yes, I generated this example precisely as Tobias Fritz described.
  
  In polymath style: I was looking at the Renaud-Sarvate example, and was wondering how they came up with it. That example is generated by the family 123, 4567, 4589, 6789, 16789, 24589, 34567, 45678, 45689, 46789. Since 45, 67, and 89 are naturally paired, this seemed to come from starting with the family generated by 123, 45, 56, 46, 145, 256, 346. That is, take all 2-subsets of a 3-set, add in unique ‘indices’ for each 2-subset as well, and also throw in the set of all indices for good measure.
  
  In general, we can try this for any combination – so doing this with all k-subsets of an l-set produces a $(k,l)$ -family (say). The Renaud-Sarvate example is the $(2,3)$ -family with an extra ‘splitting’ operation.
  
  I tried plugging in a few different values, and in particular noticed that the $(2,4)$ -family in my comment above provides the counterexample described.
  
  Given this success, and the relationship to the Renaud-Sarvate example, it looks like $(k,l)$ -families in general are a promising source of counterexamples to FUNC-like statements.
- gowers Says:
  February 5, 2016 at 11:53 am
  Thanks for that interesting answer! Let me try to make part of it more explicit (for my own benefit, but perhaps for someone else’s) by saying precisely what the extra “splitting” operation is. That is, how do we get from the set system 123, 45, 56, 46, 145, 256, 346 to the set system 123, 4567, 4589, 6789, 16789, 24589, 34567, 45678, 45689, 46789?
  
  Note first that Renaud and Sarvate needed to do this because they wanted their set system to contain a unique set of size at most 3.
  
  As a first step, let’s bracket together the pairs you draw attention to. So now the second system looks like this: 123, (45)(67), (45)(89), (67)(89), 1(67)(89), 2(45)(89), 3(45)(67), (45)(67)8, (45)6(89), 4(67)(89)
  
  So it looks as though to get from the first system to the second we need 4 to correspond to 67, 5 to correspond to 89, and 6 to correspond to 45. If we just do that to the first system we get this: 123, (45)(67), (45)(89), (67)(89), 1(67)(89), 2(45)(89), 3(45)(67). The remaining three sets come (slightly puzzlingly to me) from taking the set (45)(67)(89) and for each pair in turn removing one element — by symmetry it doesn’t matter which. The thing I find puzzling is that one doesn’t produce six extra sets by taking all possible ways of removing one element from 456789, but presumably that tips the abundances of 1,2,3 over the edge for some reason.
- Thomas Bloom Says:
  February 5, 2016 at 1:29 pm
  Actually, I forgot to check that, which is silly. If one does the more natural splitting (and adds six extra sets, rather than just 3, as you mention at the end of your comment), then this is still an example suitable for Renaud-Sarvate purposes – and the abundancies of 1,2,3 actually go down.
  
  That is, it is a union-closed family (now with 36 sets), with a unique set of size 3, and every element in that set has abundancy 17/36<1/2.
  
  So I suppose that your more natural splitting is the 'right' trick to use here (although, clearly, if one splits a little less naturally then you can get away with a slightly smaller family that still works).
  
  Indeed, the three abundancies of the Renaud-Sarvate system are (roughly) 0.48, 0.74 and 0.85, while in your more natural construction they are 0.47 and 0.8 – so the abundancies of the 3-set actually becomes smaller in this second construction, but the less natural version manages to unbalance some of the higher abundancies as well (and the 'average higher abundancy' has gone down slightly in the less natural version).
- Thomas Bloom Says:
  February 5, 2016 at 1:43 pm
  I should note that I haven’t been able to access the original paper of Renaud and Sarvate, so have no idea if this line of thinking is actually how they generated their example – it’d be great if someone with access could check if they remark in their paper how they came up with it.
- Tobias Fritz Says:
  February 7, 2016 at 4:53 pm
  I’d like to explain how Thomas’s example can be obtained via the fibre bundle construction developed here: https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154199
  
  Take $\mathcal{K} := 2^{\{7,8,9,10\}}$ minus the singletons, or equivalently the family generated by the 2-subsets of $\{7,8,9,10\}$ plus the empty set. In specifying the $\mathcal{A}_K$ , I’ll restrict myself to only writing down a subset from which the others can be inferred by symmetry.
  
  $\mathcal{A}_{\emptyset} := \{\emptyset,\{1,\ldots,6\}\}$
  $\mathcal{A}_{\{7,8\}} := \{\emptyset,\{1\},\{1,\ldots,6\}\}$
  $\mathcal{A}_{\{7,8,9\}} := \{\emptyset,\{1\},\{2\},\{1,2\},\{1,\ldots,6\}\}$
  $\mathcal{A}_{\{7,8,9,10\}} := 2^{\{1,\ldots,6\}}$
  
  The maps $\phi$ are just those that take every element to itself.
  
  I need to go now and haven’t checked this in as much detail as I’d like to. But even if some minor detail is off, it should be clear that Thomas’s example is an instance of the general construction.
gowers Says:
February 3, 2016 at 12:49 pm | Reply
Prompted by a remark of Alec Edgington’s just above I have thought of the following suggestion for a weaker result that it might be fruitful to try to prove.

I was about to write something that I then realized was known, but let me modify it. Can we prove FUNC for set systems that are generated by collections of sets of size 3? (I was going to write 2, but then $\mathcal{A}$ would contain a set of size 2, and any such set has an element in at least half the sets.)

The reason I quite like this is that it can be thought of as a question about 3-uniform hypergraphs. Indeed, let $H$ be a 3-uniform hypergraph with vertex set $X$ . Then unions of edges of $H$ are subsets $Y\subset X$ that induce subhypergraphs of $H$ with no isolated vertices. (This condition means that every element of $Y$ is contained in an edge of $H$ that is a subset of $Y$ , which implies that $Y$ is a union of edges. And the converse is clear too.)

Let us call an induced subhypergraph “sociable” if it contains no isolated points.

So we can ask: given a 3-uniform hypergraph, must there be a vertex that belongs to at least half the sociable induced subhypergraphs?

Maybe experiments would be interesting here. What happens if we choose $H$ randomly? Of course, this is equivalent to using a random collection of 3-sets to generate a union-closed family. In particular, what happens if we make $H$ fairly sparse?
- Thomas Says:
  February 3, 2016 at 4:32 pm
  In the paper “The 11-element case of Frankl’s conjecture”, by Ivica Bosnjak and Petar Markovic, they show that certain configurations of sets of size 3 imply FUNC, in particular, they show that if 3 sets of size 3 are in A and they are all subsets of the same 5 element set, then FUNC holds for A. This result can probably be extended to other configurations of sets of size 3.
- gowers Says:
  February 3, 2016 at 6:04 pm
  Here’s a reasonably nice example of a system of 3-sets such that no five elements span three sets in the system. (It may have other reasons for not working though.) Let $X,Y,Z$ be disjoint copies of a finite group $G$ and take the set of all triples $\{x,y,z\}$ with $x\in X,y\in Y$ and $z\in Z$ such that $xyz=e$ . To have three such triples all living in a 5-set, no two of them could be disjoint. But we also know that no two of them can intersect in more than one element. But it is impossible to have three 3-sets inside a 5-set without two of them intersecting in at least two elements.
  
  The obvious question in relation to this example is whether it gives a counterexample to Frankl’s conjecture. The set system we get is the collection of all subsets of $X\cup Y\cup Z$ that contain a triple that multiplies to the identity. By symmetry (since if $xyz=e$ , then $yzx=zxy=e$ ), the question can be formulated as follows. Let $A$ be a random subset of $X\cup Y\cup Z$ and let $u\in X$ . Is the conditional probability that $u\in A$ given that $A$ contains a triple $xyz$ that multiplies to the identity at least 1/2?
  
  I think (but haven’t checked carefully) that a further symmetry argument can be used to show that it is enough to answer the problem in the case that $u$ is the identity element in $X$ .
  
  I’m not sure how to go about answering this question in general, because random sets that contain triples that multiply to the identity seem like fairly hard things to handle. But probably it is easy to show for some small groups $G$ that this construction does not give rise to a counterexample to FUNC. Also, for large groups the construction seems to rule out small sets but keep big sets, so it doesn’t look a promising way of building a counterexample.
- Thomas Says:
  February 4, 2016 at 2:27 am
  If G is a finite group, we need to prove that if G is a cyclic group of prime order, then if the triples are in A (even if they are not the full generating set), then FUNC holds. The simplest case is the cyclic group of order 2. I’m working on a proof along the lines of the paper to show that if {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in A, then FUNC holds for A.
- Thomas Says:
  February 4, 2016 at 3:57 am
  I am able to show that FUNC holds for any union closed set containing {1, 2, 3}, {1, 4, 5}, (2, 4, 6}, and {3, 5, 6} (which are the triples you get from X={1, 6}, Y={2, 5}, Z={3, 4} and G is the cyclic group of order 2).
  
  Let K be any set disjoint from {1, 2, 3, 4, 5, 6}, and let C be the set of all subsets s of {1, 2, 3, 4, 5, 6} such that KUs is in A. We need to show that for all K, the average size of the sets in C is at least 3 (then you can use the weight function that assigns 1 to all of 1, 2, 3, 4, 5, 6). The empty set {} may or may not be in C, but if C is nonempty (and there is no point in considering a K for which C is empty), then the full set {1, 2, 3, 4, 5, 6} is in C. We say that a set has deficit n if the set has n less elements than the target average (in this case 3), and surplus n if it has n elements more than the average. If for every K the total surplus is at least the total deficit, then FUNC holds for A.
  
  Assume that FUNC does not hold for A, then for some K the total deficit of C is more than the total surplus of C.
  
  Case 1: {} is in C: The surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of the empty set. Since {} is in C, then {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, along with all their unions, which together make up all the sets of size 5. The total surplus of these sets is 12 (there are 6 sets of size 5, and each has surplus 2, and we’re ignoring the full set), therefore the total deficit must be at least 13. However, for every set of size 1 in C, there are two sets of size 4 in C, as follows:
  1: {1, 2, 4, 6}, {1, 3, 5, 6}
  2: {1, 2, 4, 5}, {2, 3, 5, 6}
  3: {1, 3, 4, 5}. {2, 3, 4, 6}
  4: {1, 2, 3, 4}, {3, 4, 5, 6}
  5: {1, 2, 3, 5}, {2, 4, 5, 6}
  6: {1, 2, 3, 6}, {1, 4, 5, 6}
  Therefore, the total deficit of the size two sets must make up the 13. But then there must be at least 13 sets of size 2 in C (since they only have deficit 1), and together, these 13 sets generate all of the sets of size 4 (since each set of size 4 can be generated in 3 ways, you need to remove 3 sets before you can’t generate a set of size 4). Therefore, the total surplus is 27, which is the maximum that the total deficit can be.
  
  Case 2: {} is not in C. In this case, since {} is not in C, we consider the set {1, 2, 3, 4, 5, 6} as counting towards the total surplus (as the empty set isn’t there to cancel it out). Now, each set of size 1 in C means that two of {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, and the union of those is a size 5 set, so each size one set cancels out with a size 5 set. Now, every set of size 2 in C forces a set of size 4 to be in C, except {1, 6}, {2, 5}, {3, 4}. We just need a bijection from the sets of size 2 (excluding the above) to the sets of size 4 (excluding {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}), such that if a set of size 2 is in C, then the associated set of size 4 is in C. Such a bijection is given below:
  {1, 2}->{1, 2, 4, 5}
  {1, 3}->{1, 3, 5, 6}
  {1, 4}->{1, 2, 4, 6}
  {1, 5}->{1, 2, 3, 5}
  {2, 3}->{2, 3, 4, 6}
  {2, 4}->{1, 2, 3, 4}
  {2, 6}->{2, 3, 5, 6}
  {3, 5}->{1, 3, 4, 5}
  {3, 6}->{1, 2, 3, 6}
  {4, 5}->{3, 4, 5, 6}
  {4, 6}->{1, 4, 5, 6}
  {5, 6}->{2, 4, 5, 6}
  
  So, the surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of {1, 6}, {2, 5}, {3, 4}, and every other set of size 2 has an associated set of size 4. Therefore, the surplus is at least the deficit. Q.E.D.
  
  So this proves that if your finite group G has a subgroup of order 2, then FUNC holds on the set generated by the triples. Sorry about the long post, if any of it is unclear, the paper I mentioned earlier should straighten things out.
- Thomas Says:
  February 4, 2016 at 4:29 am
  Also, I would say that your intuition is right about the large groups (and probably all groups in general), that they have very large numbers of sets of size 3, more than I think could “fit”, in the sense that they’re very likely to contain a configuration that automatically implies Frankl’s conjecture. The number of sets of size 3 is the square of the order of the group (you can pick x and y, but then z is determined), which in my opinion is far too large.
  
  This makes me think of Hamming codes and other error correcting codes, where the strings of 0’s and 1’s (which could be interpreted as which elements are in the set and which aren’t), could not be too close together (although I doubt it will work with the union closed condition).
- Tobias Fritz Says:
  February 4, 2016 at 7:40 am
  With respect to the group example, I’m a bit puzzled by the statement “The set system we get is the collection of all subsets of $X\cup Y\cup Z$ that contain a triple that multiplies to the identity”. Isn’t this suggesting that the set system is upper closed, so that FUNC holds trivially? Also, a 4-set of the form $\{x,y,z,z'\}$ with $xyz=e$ and $z'\in Z$ different from $z$ satisfies the condition, but can’t arise as a union of triples that multiply to the identity, no?
  
  [Sorry for not having anything constructive to say at the moment…]
- gowers Says:
  February 4, 2016 at 7:53 am
  Ah yes, that statement is wrong. The system consists of all subsets $A\cup B\cup C$ of $X\cup Y\cup Z$ such that for every $a\in A$ there exist $b\in B, c\in C$ with $abc=e$ , and similarly for $B$ and $C$ .
- Thomas Says:
  February 4, 2016 at 7:54 am
  I assume that only the sets of size exactly 3 are included in the definition, because he is considering generating sets that contain only sets of order 3.
- Thomas Says:
  February 4, 2016 at 8:04 am
  Never mind, I posted before I saw the previous comment. My above argument shows that no group of even order works, so the next case is the cyclic group of order 3. It may be possible (but beyond my ability) that given enough configurations of 3-sets that imply FUNC, we can find a sub-quadratic bound on the number of 3-sets that can occur for a given m.
Gil Kalai Says:
February 4, 2016 at 8:05 pm | Reply
Let $\mu_p(F)$ be the probability that a random set $S$ belongs to $F$ when $S$ is chosen as follows: every element belongs to $S$ with probability $p$ and these probabilities are statistically independent.

If $F$ is a symmtric union-closed family, namely if it is invariant under some transitive group of permutations on the elements then Frankl’s conjecture is equivalent to the statement that $\mu_p(F)$ has nonnegative derivative at $p=1/2$ . We can extend it and ask if $\mu_p(F)$ is monotone non-decreasing for every $p$ . Maybe we can juggle between different $p$ s by modifyig the family $F$ e.g. by replacing every element by say $k$ elements and asking that a set in the new ground set in in the modified family if for some set in the original family it has at least one new element for every original element. (Or something like this.) So maybe a counterexample for $p \ne 1/2$ (say $p$ very close to 1) can be modified into a counterexample for $p=1/2$ .

It will be interesting to looks at examples like “union of lines in projective spaces”. I dont know if for such examples $\mu_p(F)$ is monotone increasing for $p$ for every $p$ .
- Gil Kalai Says:
  February 5, 2016 at 4:00 am
  For example, for the Fano plane $\mu_p(F)=7p^3(1-p)^4+21p^5(1-p)^2+7p^6(1-p)+p^7$ . Is it monotone with $p$ ?
  
  Frankl’s conjecture says that every point is in more than half the sets which gives that the derivative of $\mu$ at 1/2 is positive. But it looks that having some $p$ for which the derivative is negative will allow to replace the family with another and push the non-monotonicity to p=1/2. (Maybe such a reduction can work even for the non-symmetric case and even for different product measures based on diffrent $p_i$ s.)
- Eckhard Says:
  February 5, 2016 at 9:44 am
  The function $p\mapsto\mu_p(F)$ is monotonic with respect to $p$ because its derivative is given by $\mu_p'(F)=\frac{7p^2(1-p)^2}{22}\left[41+(22p-5)^2\right]>0$ .
- Gil Kalai Says:
  February 7, 2016 at 2:24 am
  Actually, we can add the empty set to $F$ and thus the additional term $(1-p)^7$ to $\mu_p(F)$ and then $\mu_p$ cannot be monotone so it will be decreasing for some $p$ . (For this you can take the family with all sets of 0,2,3 elements from $\{1,2,3\}$ .) Now, it looks that the methods described above by replacing each element by a threshold on many elements so that the probability to reach the threshold is p, will transfer the non monotomicity from p to 1/2 as we want.
- Gil Kalai Says:
  February 7, 2016 at 7:42 pm
  Indeed, for union-closed families with transitive symmetry, monotonicity fails for general values of $p$ . (We can have the empty set and full set in the family giving $\mu_0(F)=\mu_1(F)=1$ .) But I don’t see a reason that this will lead to examples that it fails for $p=1/2$ which is what Frankl’s conjecture gives. In particular, trying to augment the family with threshold families (as I suggested above) causes violation of the union-closed property. (Maybe, the conjecture extends to all $p \ge p_0$ for some $p_0$ , perhaps $p_0=1/2$ but I am not sure it is “truer” for larger p. For the simple example of 0- 2-3- subsets of a 3-element set, monotonicity is violated when $p<1/3$ .)
gowers Says:
February 5, 2016 at 12:28 pm | Reply
This is presumably a familiar concept to people who have thought about FUNC a lot, but it seems as though it should be mentioned here. Let’s define a homomorphism from a union-closed set system $\mathcal B$ to a union-closed set system $\mathcal A$ to be a function $\phi:\mathcal B\to\mathcal A$ such that $\phi(B\cup B')=\phi(B)\cup\phi(B')$ for every $B,B'\in\mathcal B$ .

Given a union-closed family $\mathcal{A}$ , it is quite interesting to think about what homomorphism exist to $\mathcal{A}$ . An easy example is to let $A_1,\dots,A_k$ be a generating set for $\mathcal{A}$ and to take $\mathcal B$ to be the power set of $\{1,2,\dots,k\}$ . Then we can map $B$ to $\bigcup_{i\in B}A_i$ . Another obvious example is to duplicate elements of the ground set of $\mathcal A$ : then the resulting set system $\mathcal B$ has an obvious homomorphism to $\mathcal A$ .

In general, suppose we have a union-closed system $\mathcal B$ and it has a generating set $B_1,\dots,B_k$ . Then we could try mapping $B_i$ to $A_i$ . This would force $B_E=\bigcup_{i\in E}B_i$ to map to $A_E=\bigcup_{i\in E}A_i$ , which is fine provided we don’t find that there exist $E,F$ such that $B_E=B_F$ but $A_E\ne A_F$ . So the condition we need is roughly that there are fewer set-theoretic relations amongst the $B_i$ than there are amongst the $A_i$ — which is why taking the $B_i$ above to be (distinct) singletons works easily.

I thought about this while thinking about Thomas Bloom’s comment above. I haven’t checked, but it would be interesting to me to know whether the kinds of splitting operations he talks about are a special case of finding a new family and a homomorphism to the old family. I would also be interested to see whether anything interesting can be said about what homomorphisms do to abundances.
- gowers Says:
  February 5, 2016 at 1:08 pm
  A rather general way of constructing homomorphisms is as follows. Let $A_1,\dots,A_k$ be a generating set for $\mathcal{A}$ and let $Y$ be some set disjoint from $X$ . Now let $\mathcal{K}$ be an arbitrary family of subsets of $Y$ and let $\psi:\mathcal K\to\{A_1,\dots,A_k\}$ be an arbitrary function. Finally, let $\mathcal{B}$ be generated by the sets $K\cup\phi(K)$ such that $K\in\mathcal{K}$ .
  
  I claim that the map $\phi(B)=B\setminus Y$ is a homomorphism from $\mathcal B$ to $\mathcal A$ . It’s trivial that it preserves unions, but we need to be sure that $B\setminus Y$ actually belongs to $\mathcal A$ . But each $B\in\mathcal B$ is the union of a union of subsets of $Y$ and a union of some of the sets $A_i$ , so that is easy too.
  
  This construction is a way of “duplicating” sets in $\mathcal A$ , by turning them into all their inverse images in $\mathcal B$ . Something reasonably promising about this is that it looks easy to do this in such a way that smaller sets in $\mathcal A$ get duplicated more, since the more sets in $\mathcal K$ that you union together, the more chance (at least for certain choices of $\mathcal K$ ) of coincidences. But this is presumably at the cost of introducing elements of $Y$ that may have large abundances.
  
  This feels very similar to comments I have already seen, I think by Thomas Bloom. I hope it is a mild generalization, but apologies if it is in fact identical.
Tobias Fritz Says:
February 5, 2016 at 2:13 pm | Reply
Inspired by the other thread on generating random examples, I’ve now written some code that computes the average overlap density:
http://personal-homepages.mis.mpg.de/fritz/overlap_density.sage

Upon downloading the file, you can run it in Sage using this command:
```
load("overlap_density.sage")
```
The file’s header contains the three parameters that control the search for examples with low overlap density: size of the ground set, size of each generating set, and number of generating sets. There are no checks for the set system to cover the entire ground set or even to separate points.

The results are mildly encouraging: it’s easy to find examples with overlap density $\approx 0.6$ and lower, but no example with overlap density $< 0.53$ has been found so far. The smallest overlap densities of around $0.53$ are observed in those examples in which the generating sets are pairwise disjoint, i.e. when the union-closed family is a Boolean algebra (and therefore very far from separating points). Using smaller generating sets typically results in smaller overlap densities.
- Thomas Bloom Says:
  February 5, 2016 at 2:31 pm
  Playing around with the overlap density and the $(k,l)$ -families I described above in Python, it looks the following is true:
  
  Let $F(k,l)$ be the average overlap density of the $(k,l)$ -family. Then, for $1\leq k<l-1$ , we have $F(k,l)<F(k+1,l)$ and $F(k,l)0.5 (the furthest my computer can go is the$ latex (1,7)$-family, which has average overlap density of 0.55514…
- Thomas Bloom Says:
  February 5, 2016 at 2:32 pm
  Playing around with the overlap density and the $(k,l)$ -families I described above in Python, it looks the following is true:
  
  Let $F(k,l)$ be the average overlap density of the $(k,l)$ -family. Then, for $1\leq k<l-1$ , we have $F(k,l)<F(k+1,l)$ and $F(k,l)0.5$ (the furthest my computer can go is the $(1,7)$ -family, which has average overlap density of 0.55514…
Alec Edgington Says:
February 5, 2016 at 2:51 pm | Reply
Can anyone explain why Frankl’s conjecture implies the Salzborn formulation? (Apparently the proof is in P. Wojcik, ‘Union-closed families of sets’, Disc. Math. 199 (1999), 173–182, but I can’t find that article.)

I’ve been playing with randomly-generated normalized families, with a view to looking for structure in the tightest examples, and observed that the mimimum maximum-basis-set-size as a function of the size of the ground set for normalized families seems to match the minimum maximum-abundance as a function of the size of the ground set for all union-closed families (the function called $\phi(n)$ in the survey article, which starts uncannily like Sloane A004001). So I guess there must be an exact correspondence.
- André Says:
  February 5, 2016 at 3:06 pm
  You can find the paper here:
  http://www.sciencedirect.com/science/article/pii/S0012365X98002088
  
  There is also a way to do it using some dual families defined by Johnson and Vaughan. Let F be a normalized family and J(F) be the set of join-irreducible sets in the family F, $\{A_1,...A_n\}$ . For every x let J(x) be the set of the indexes of join-irreducible sets that have x and take D(F) the dual family of F as the family generated (so that it becomes union-closed) by {J(x): x in U}, where U is the ambient set. They prove this family has the same cardinality as F and it is clear that if this family has an element in at least half the sets that implies Salzburg holds for F.
- Alec Edgington Says:
  February 5, 2016 at 3:21 pm
  Thanks!
André Says:
February 5, 2016 at 4:06 pm | Reply
No problem !
Actually, I believe you can see that a normalized separating family has an universal element and an element in n-1 sets because the family $\mathcal{G} = \{J(x):x \in U\}$ is already union-closed because if your initial family is normalized then $|\mathcal{G}|=n$ before (and after generating) and so it has a set {1,2,…,t}, where t is the number of join irreducible sets and another set $\{1,2,....,t\}-\{a\}$ for some $a\in [t].$
aaaatos Says:
February 5, 2016 at 4:24 pm | Reply
This may be a question that has already been answered, or has a trivial answer, but I’m curious enough to ask it anyway: what is known about Frankl’s conjecture if we assume the family is BOTH union-closed and intersection-closed (i.e. is isomorphic to a topology on some finite set)?
- Thomas Says:
  February 5, 2016 at 4:31 pm
  If the family is both union closed and intersection closed, then the family either contains a set of size one, or it is not separable (in which case, you can combine elements in the set so that it is separable. Therefore, every union and intersection closed set satisfies FUNC.
- aaaatos Says:
  February 5, 2016 at 4:33 pm
  I guess that counts as a trivial answer. Thanks!
- Thomas Says:
  February 5, 2016 at 4:38 pm
  If you’re interested, there is an equivalent conjecture (which you’ve probably heard of by now) about intersection closed sets, that there is always an element in at mot half of the sets. This equivalent conjecture might be easier to solve.
gowers Says:
February 5, 2016 at 11:36 pm | Reply
I have another question, this time not comparable to FUNC, in that proving it won’t prove FUNC and finding a counterexample won’t give a counterexample to FUNC. But I still find it interesting.

Suppose we take the conjecture about average overlap density. One way we might try to disprove it is to take an ordering on the elements of the ground set, and then duplicate the elements in such a way that each successive element of the ground set is duplicated far more times than its predecessor. Equivalently, let us weight the elements in such a way that the weights increase rapidly.

What will this do to the overlap densities? Well, if $A$ and $B$ are sets in $\mathcal A$ , then the weight of $A$ is almost entirely in its maximal element, so $\mu(A\cap B)/\mu(A)$ will be approximately 1 if $\max A\in B$ and approximately 0 otherwise.

So let us define a new sort of overlap density. I’ll say that $B$ beats $A$ if $\max A\in B$ . I now want to know whether if you pick a random non-empty set $A\in\mathcal A$ and independently a random set $B\in\mathcal A$ , the probability that $\max A\in B$ is always at least 1/2.

A nice thing about this is that we can fix the order to be just the usual order on $\{1,2,\dots,n\}$ and then choose the set system to try to make it as unlikely as possible that the maximal element of one set is contained in another set. The relationship between this and FUNC is that both statements follow from the conjecture that the average overlap density is always at least 1/2. So it is a special case of a fairly natural strengthening. I think it’s a special case worth considering, because it looks fairly clean to investigate computationally, so there’s a chance that we may be able to use it to dispose of the average-overlap-density strengthening. Perhaps one can even find an example by hand.
- Alec Edgington Says:
  February 6, 2016 at 8:55 am
  If I’ve understood correctly, I think this is a counterexample with $n = 3$ : take the 6-set family $\{\emptyset, \{1\}, \{2\}, \{1,2\}, \{1,3\}, \{1,2,3\}\}$ . The number of pairs $(A, B)$ where $A \neq \emptyset$ and $\max(A) \in B$ is 14, which is less than half of $5 \times 6$ .
- gowers Says:
  February 6, 2016 at 10:00 am
  That looks right. So it should convert into a counterexample to the average-overlap-density “conjecture” (the inverted commas because it always seemed a bit unlikely to be true). Let $A,B,C$ be disjoint sets with $A$ a singleton, $B$ a set of size $m$ and $C$ a set of size $m^2$ . Then the counterexample should be
  
  $\{\emptyset, A, B, A\cup B, A\cup C, A\cup B\cup C\}$
  
  for sufficiently large $m$ .
- Alec Edgington Says:
  February 6, 2016 at 10:39 am
  Yes, that works.
- gowers Says:
  February 6, 2016 at 10:44 am
  I suppose an obvious challenge at this point is to try to find a counterexample that separates points. However, what I would prefer to try to find is a general method for converting set systems that don’t separate points into set systems that do separate points, while keeping the abundances approximately the same (in some sense). I may well be wrong, but it feels to me as though it ought to be possible somehow. A slightly weaker requirement that would still do fine would be to find a way of achieving what can be achieved with duplication but with just a few more sets thrown in so that points are separated.
gowers Says:
February 6, 2016 at 2:47 pm | Reply
Advance warning: this comment and the first two replies to it give a detailed description of a construction that ends up not working.

Here’s a rough proposal for a method of construction that is aimed at showing, roughly speaking, that adding the condition that a set system should separate points doesn’t help, in the sense that it won’t magically make false conjectures true. (Obviously it makes some statements true — e.g. the statement that your family separates points. I haven’t thought about how to characterize the statements that I’m talking about.)

Let $\mathcal{A}$ be a set system that does not necessarily separate points. Let $X$ be the ground set of $\mathcal A$ . Now let $G$ be the cyclic group of order $N$ and form a new set system $\mathcal A\times G$ that consists of all sets of the form $A\times G$ with $A\in\mathcal A$ . I am assuming that $N$ is much bigger than $|X|$ .

Now choose two random functions $\phi,\psi:X\to G$ . For each $g\in G$ and each $A\in\mathcal{A}$ , let $B(A,g)$ be the set
$(A\times G)\setminus\{(x,\phi(x)+g):x\in A\}$
and let $C(A,g)$ be the set
$(A\times G)\setminus\{(x,\psi(x)+g):x\in A\})$ .
I now want to let $\mathcal B$ be the set system generated by the sets $B(A,g)$ and $C(A,g)$ .

The two things I want to prove about $\mathcal B$ are as follows.

1. It separates points.

2. The abundance of any element $(x,h)\in X\times G$ in $\mathcal B$ is approximately the same as the abundance of $x$ in $\mathcal A$ .

I will post this comment to make it easier to look at what I’ve just defined and what I want to prove. Of course, this risks that I will find that I’ve got it wrong. (I haven’t written this out in advance.)
- gowers Says:
  February 6, 2016 at 3:00 pm
  Let me start with 1. Let $(x,g)$ and $(y,h)$ be distinct elements of $X\times G$ . (I’m assuming that $X=\bigcup\mathcal A$ of course.) If $x=y$ , then choose $u\in G$ such that $\phi(x)+u=g$ . Then $(x,g)\notin B(A,u)$ , but since $\phi(x)+u\ne h$ , $(x,h)\in B(A,u)$ .
  
  If $x\ne y$ , then this does not work because we might find that $\phi(x)+u=g$ and $\phi(y)+u=h$ . That would imply that $\phi(x)-\phi(y)=g-h$ . But then we can use the set $C(A,g-\psi(x))$ instead. The only thing that can go wrong is if there exist $x$ and $y$ with $\phi(x)-\phi(y)=\psi(x)-\psi(y)$ . But if $N$ is much larger than $|X|$ , then this happens with very low probability. (All I need for this argument is that there exist functions $\phi$ and $\psi$ such that it doesn’t happen.)
  
  The above argument, I forgot to say, was dealing with the case where there is some set $A$ that contains both $x$ and $y$ . If no such $A$ exists, then $x$ and $y$ are already separated.
  
  I’ll deal with abundances in a separate comment.
- gowers Says:
  February 6, 2016 at 3:26 pm
  OK, let $(x,g)\in X\times G$ . I want to estimate its abundance.
  
  First let’s see how many sets in $\mathcal B$ are subsets of a given set $A\times G$ but not of any set $A'\times G$ with $A'\in\mathcal A$ a proper subset of $A$ . What I need for this construction to work is that I should get roughly the same answer for all $A$ .
  
  Unfortunately, I realize as I write this that it doesn’t work. My basic problem is that if $A$ and $B$ are disjoint sets in $\mathcal{A}$ , then if I do a construction that creates, in some sense, approximately $m$ copies of $A$ and another $m$ copies of $B$ , then when I take their unions I will have to create $m^2$ copies of $A\cup B$ . I thought I could somehow “couple” the copies of $A$ with the copies of $B$ , but I can’t.
- gowers Says:
  February 6, 2016 at 4:13 pm
  I think I can convert that failure into a lemma. Let $\mathcal A$ be a union-closed set system. I claim that if $\mathcal A$ contains two disjoint non-empty sets, then it is not possible to find a union-closed set system $\mathcal B$ and a surjective homomorphism $\phi:\mathcal B\to\mathcal A$ such that every $A\in\mathcal A$ has approximately the same number of preimages — except if that number is 1.
  
  The proof is trivial. If $A$ and $A'$ are disjoint elements of $\mathcal A$ and $B$ and $B'$ are preimages, then $B\cup B'$ is a preimage of $A\cup A'$ . Actually, for this argument to be properly trivial I need to assume that $B$ and $B'$ are disjoint, which they don’t have to be, so it’s back to the drawing board yet again — maybe there is some clever way of getting sets to overlap in order to compensate for this effect.
gowers Says:
February 6, 2016 at 7:33 pm | Reply
Here’s a ludicrously optimistic strengthening of FUNC. Normally I’d try a little bit to find a counterexample before posting it, but I’m otherwise occupied this evening. The strengthening is the claim that if $\phi:\mathcal B\to\mathcal A$ is a surjective homomorphism (meaning that it preserves unions), then the maximum abundance of an element with respect to $\mathcal A$ is at least as big as the maximum abundance of an element with respect to $\mathcal B$ . This would imply FUNC, because we could just take a generating set $A_1,\dots,A_k$ for $\mathcal A$ and take $\mathcal B$ to be the power set of $\{1,2,\dots,k\}$ and map $E$ to $\bigcup_{i\in E}A_i$ .

Why is this “conjecture” even slightly plausible? Well, if we try to disprove it by taking $\mathcal B$ to consist of large sets, then we are likely to find coincidences amongst the unions of sets in $\mathcal B$ that do not correspond to coincidences in $\mathcal A$ .

Actually, writing that sentence has made me realize just how false this “conjecture” is. We can take $\mathcal B$ to be generated by random subsets $B_1,\dots,B_k$ of $\{1,2,\dots,N\}$ for some very large $N$ , each of density $\alpha$ for some $\alpha<1$ . (The closer $\alpha$ is to 1, the larger we need to take $N$ .) Then as long as $N$ is large enough, all unions of the $B_i$ will be distinct, so the map that takes $\bigcup_{i\in E}B_i$ to $\bigcup_{i\in E}A_i$ will be a homomorphism, and we can make the average abundance in $\mathcal B$ as large as we like.
- Tobias Fritz Says:
  February 7, 2016 at 8:37 am
  That $\mathcal{B}$ is arguably not a very good counterexample, since all abundances are 0, 1/2 or 1 (again just because there are no coincidences among the unions of the generators). The average abundance becomes large only due to the large number of elements with abundance 1. I want to argue that we shouldn’t really count elements with abundance 1: one reason is that the lattice formulation of FUNC doesn’t even ‘see’ them and would consider your $\mathcal{B}$ to have a maximal abundance of 1/2. So if one excludes elements of abundance 1 from the strengthened conjecture, then that counterexample doesn’t work.
  
  For a different family of counterexamples that still work, take $\mathcal{B}$ to be any union-closed family containing the empty set and with maximal abundance greater than 1/2. Take $\mathcal{A} = \{\emptyset,\{1\}\}$ , and $\phi$ to be given by the empty set mapping to the empty set and everything else mapping to $\{1\}$ . Then $\phi$ is surjective, but decreases maximal abundance.
- gowers Says:
  February 7, 2016 at 12:47 pm
  Ah yes, that’s a good point (and one that I had to think about for a while before understanding why it was correct).
  
  Although I still very much doubt whether any conjecture like this can be true, let me try to refine the conjecture slightly to rule out the two examples so far but to leave something that still implies FUNC.
  
  The refined conjecture says the following. Let $A_1,\dots,A_k$ be a minimal generating set for a union-closed system $\mathcal A$ (which by convention I will take to include the empty set). Let $B_1,\dots,B_k$ be some other sets and suppose that the following two statements hold.
  
  (i) The map $\bigcup_{i\in E}B_i\to\bigcup_{i\in E}A_i$ is a homomorphism.
  
  (ii) If any element is removed from any of the $B_i$ , then the map ceases to be a homomorphism.
  
  Then the maximum abundance of $\mathcal B$ is at most the maximum abundance of $\mathcal A$ .
- Thomas Bloom Says:
  February 8, 2016 at 9:14 am
  I must be missing something – isn’t a map of the form $\cup_{i\in E}B_i\to \cup_{i\in E}A_i$ always a homomorphism, whatever we do to the the $B_i$ , so the second condition is never satisfied? Also, presumably this is intended to rule out Tobias’ example with $A_1=\emptyset$ and $A_2=\{1\}$ , but I’m afraid I don’t see how?
- gowers Says:
  February 8, 2016 at 10:28 am
  It’s always a homomorphism if it’s well-defined, but it may not be well-defined. I should have made it clearer that that was the main constraint on $\mathcal B$ .
  
  As for ruling out Tobias’s example, the unique minimal generating set of $\mathcal A$ in his example is $\{\{1\}\}$ , which forces $k$ to equal 1, which forces $\mathcal B$ to be a very boring set system — it has to consist of just one set and the empty set, and then by minimality that set has to be a singleton.
- gowers Says:
  February 8, 2016 at 10:32 am
  Having said that, the second condition doesn’t feel right, since removing elements from some of the $B_i$ can sometimes turn a homomorphism into a non-homomorphism, but it can also sometimes turn a non-homomorphism into a homomorphism. So it doesn’t seem to capture the idea of minimality that I was trying to capture.
  
  Maybe I should have stuck with something simpler like removing all elements with abundance 1.
Polymath 11 is Now Open | The polymath blog Says:
February 7, 2016 at 3:45 am | Reply
[…] element that belongs to at lease half the sets in the family. Here are links to Post number 0 and Post number 1. (Meanwhile polymath10 continues to run on “Combinatorics and […]
Michael Brunnbauer Says:
February 24, 2016 at 3:50 pm | Reply
I wonder if something like this might lead to interesting questions: http://brunni.de/ucf/stats.cgi (abundance statistics for randomly generated and breeded families).
A title – to be defined Says:
February 29, 2016 at 6:02 am | Reply
[…] discuss together what directions to peruse. It is a pleasure to mention that in parallel Tim Gowers is running polymath11 aimed for resolving Frankl’s union closed conjecture. Both questions were offered along with the […]
Karthik Thyagarajan Says:
April 22, 2016 at 9:49 am | Reply
A possible construction is using independent finite sets. Lets say of m independent sets. Now for union over any r of these must belong to the family.

so we have a total of 2^m sets in total

now assume x belongs to one of the sets then there are 1+2^(m-1)
sets to which x belongs

which is clearly greater than 1/2

this can generalized for overlaping sets by removing all the independent sets from the family
the family is still union closed
in this case the total number of sets become (2^m) – m

but now x belongs 2^(m-1)

which is still greater than 1/2.

clearly, the new family is conformable to any union closed family
MO Polymath question: Summary of Proposals | The polymath blog Says:
August 13, 2016 at 8:23 pm | Reply
[…] 14) Frankl’s union closed set conjecture (Proposed by Dominic van der Zypen; Also one of the proposals by Gowers in this post). (Launched) […]
Frankl’s Conjecture for Large Families: Ilan Karpas’ Proof | Combinatorics and more Says:
March 8, 2018 at 9:33 pm | Reply
[…] the problem in our very first post, and Tim Gowers ran polymath 11 in attempt to solve it (first post, wikipage). See also this post over GLL and this […]