Archive for February, 2016

FUNC4 — further variants

February 22, 2016

I’ve been in Paris for the weekend, so the number of comments on the previous post got rather large, and I also fell slightly behind. Writing this post will I hope help me catch up with what is going on.

FUNC with symmetry

One question that has arisen is whether FUNC holds if the ground set is the cyclic group \mathbb Z_n and \mathcal A is rotationally invariant. This was prompted by Alec Edgington’s example showing that we cannot always find x and an injection from \mathcal A_{\overline x} to \mathcal A_x that maps each set to a superset. Tom Eccles suggested a heuristic argument that if \mathcal A is generated by all intervals of length r, then it should satisfy FUNC. I agree that this is almost certainly true, but I think nobody has yet given a rigorous proof. I don’t think it should be too hard.

One can ask similar questions about ground sets with other symmetry groups.

A nice question that I came across on Mathoverflow is whether the intersection version of FUNC is true if \mathcal A consists of all subgroups of a finite group G. The answers to the question came very close to solving it, with suggestions about how to finish things off, but the fact that the question was non-trivial was quite a surprise to me.
(more…)

Posted in polymath11 | 158 Comments »

FUNC3 — further strengthenings and variants

February 13, 2016

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

A proposal for a rather complicated averaging argument

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

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

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

Posted in polymath11 | 154 Comments »

FUNC2 — more examples

February 8, 2016

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

Standard “algebraic” constructions

Quotients

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

Subfamilies

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

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

Products

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

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

Posted in polymath11 | 104 Comments »