FUNC4 — further variants

http://ift.tt/1QVmsBR

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.

A weakening of Gil’s conjecture

In response to Alec’s counterexample, Gil Kalai asked a yet weaker question, which is whether one can find $x$ and an injection from $\mathcal A_{\overline x}$ to $\mathcal A_x$ that increases the size of each set. It is easy to see that this is equivalent to asking that the number of sets of size at least $r+1$ in $\mathcal A_x$ is always at least the number of sets of size at least $r$ in $\mathcal A_{\overline x}$ . One aspect of this question that may make it a good one is that it permits one to look at what happens for particular values of $r$ , such as $n-2$ (where $n$ is the size of the ground set), and also to attempt induction on $n-r$ . So far this conjecture still seems to be alive.

Ternary FUNC

Another question that is I think alive still is a “ternary version” of FUNC. I put forward a conjecture that had a very simple counterexample, and my attempt to deal with that counterexample led to the following question. Let $\mathcal F$ be a collection of functions from a finite set $X$ to $\{0,1,2\}$ and suppose that it is closed under the following slightly strange multivalued operation. Given two functions $f,g\in\mathcal F$ , let $A_{ij}$ be the set where $f(x)=i$ and $g(x)=j$ . (Thus, there are potentially nine sets $A_{ij}$ . We now take the set of all functions that are constant on each $A_{ij}$ , and either lie between $f$ and $f\vee g$ or lie between $g$ and $f\vee g$ . For example, if $f=11000$ and $g=02222$ then we get $12000$ , $11111$ , $12111$ , $11222$ , $12222$ , $12222$ and $f$ and $g$ themselves.

This definition generalizes to alphabets of all sizes. In particular, when the alphabet has size 1, it reduces to the normal FUNC, since the only functions between $f$ and $f\vee g$ that are constant on the sets where $f$ and $g$ are constant are $f$ and $f\vee g$ themselves. The conjecture is then that there exists $x$ such that $f(x)=k$ (where the functions take values in $\{0,1,\dots,k\}$ ) for at least $|\mathcal F|/(k+1)$ of the functions in $\mathcal F$ . If true, this conjecture is best possible, since we can take $\mathcal F$ to consist of all functions from $X$ to $\{0,1,\dots,k\}$ .

The reason for the somewhat complicated closure operation is that, as Thomas pointed out, one has to rule out systems of functions such as all functions that either take all values in $\{0,1\}$ or are the constant function that takes the value 2 everywhere. This set is closed under taking pointwise maxima, but we cannot say anything interesting about how often functions take the largest value. The closure property above stops it being possible to “jump” from small functions to a large one. I don’t think anyone has thought much about this conjecture, so it may still have a simple counterexample.

Weighted FUNC

Another conjecture I put forward also had to be significantly revised after a critical mauling, but this time not because it was false (that still seems to be an open question) but because it was equivalent to a simpler question that was less interesting than I had hoped my original question might be.

I began by noting that if we think of sets in $\mathcal A$ has having weight 1 and sets not in $\mathcal A$ as having weight 0, then the union-closed condition is that $w(A\cup B)\geq w(A)\wedge w(B)$ . We had already noted problems with adopting this as a more general conjecture, but when weights are 0 or 1, then $w(A)\wedge w(B)=w(A)^{1/2}w(B)^{1/2}$ . So I wondered whether the condition $w(A\cup B)\geq w(A)^{1/2}w(B)^{1/2}$ would be worth considering. The conjecture would then be that there exists $x$ such that $\sum_{x\in A}w(A)\geq\sum_A w(A)$ , where we sum over all subsets of the ground set $X$ . I had hoped that this question might be amenable to a variational approach.

Alec Edgington delivered two blows to this proposal, which were basically two consequences of the same observation. The observation, which I had spotted without properly appreciating its significance, was that if $A,B$ have non-zero weight, then $w(B)\geq w(A)^{1/2}w(B)^{1/2}$ , and therefore $w(A)\leq w(B)$ . One consequence of this is that a weighting $w$ with $w(A)=0$ is usually not close to a weighting with $w(A)>0$ . Indeed, suppose we can find $B$ with $w(B)>0$ and $w(A\cup B)=0$ . Then the moment $w(A)$ becomes non-zero, $w(A\cup B)$ is forced to jump from $0$ to at least $w(B)$ .

A second consequence is that talking about geometric means is a red herring, since that condition implies, and is implied by, the simpler condition that the family $\mathcal A$ of sets with non-zero weight is union closed, and $w(A)\leq w(B)$ whenever $A,B\in\mathcal A$ with $A\subset B$ .

However, this still leaves us with a strengthening of FUNC. Moreover, it is a genuine strengthening, since there are union-closed families where it is not optimal to give all the sets the same weight.

Incidentally, as was pointed out in some of the comments, and also in this recent paper, it is natural to rephrase this kind of problem so that it looks more like a standard optimization problem. Here we would like to maximize $\sum_{A\in\mathcal A}w(A)$ subject to the constraints that $w(A)\leq w(B)$ whenever $A\subset B$ and $\sum_{x\in A}w(A)\leq 1$ for every $x$ in the ground set. If we can achieve a maximum greater than 2, then weighted FUNC is false. If we can achieve it with constant weights, then FUNC is false.

However, this is not a linear relaxation of FUNC, since for the weighted version we have to choose the union-closed family $\mathcal A$ before thinking about the optimum weights. The best that might come out of this line of enquiry (as far as I can see) is a situation like the following.

Weighted FUNC is true.
We manage to understand very well how the optimum weights depend on the union-closed family $\mathcal A$ .
With the help of that understanding, we arrive at a statement that is easier to prove than FUNC.

That seems pretty optimistic, but it also seems sufficiently non-ridiculous to be worth investigating. And indeed, quite a bit of investigation has already taken place in the comments on the previous post. In particular, weighted FUNC has been tested on a number of families, and so far no counterexample has emerged.

A quick remark that may have been made already is that if $G$ is a group of permutations of the ground set that give rise to automorphisms of $\mathcal A$ , then we can choose the optimal weights to be $G$ -invariant. Indeed, if $w$ is an optimal weight, then the weight $v(A)=\mathbb E_{g\in G}w(gA)$ satisfies the same constraints as $w$ and $\sum_{A\in\mathcal A}v(A)=\sum_{A\in\mathcal A}w(A)$ . However, the optimal weight is not in general unique, and sometimes there are non- $G$ -invariant weights that are also optimal.

Where next?

I wonder whether it is time to think a bit about strategy. It seems to me that the (very interesting) discussion so far has had a “preliminary” flavour: we have made a lot of suggestions, come up with several variants, some of which are false and some of which may be true, and generally improved our intuitions about the problem. Should we continue like that for a while, or are there promising proof strategies that we should consider pursuing in more detail? As ever, there is a balance to be struck: it is usually a good idea to avoid doing hard work until the chances of a payoff are sufficiently high, but sometimes avoiding hard work means that one misses discoveries that could be extremely helpful. So what I’m asking is whether there are any proposals that would involve hard work.

One that I have in the back of my mind is connected with things that Tom Eccles has said. It seems to me at least possible that FUNC could be proved by induction, if only one could come up with a suitably convoluted inductive hypothesis. But how does one do that? One method is a kind of iterative process: you try a hypothesis and discover that it is not strong enough to imply the next case, so you then search for a strengthening, which perhaps implies the original statement but is not implied by smaller versions of itself, so a yet further strengthening is called for, and so on. This process can be quite hard work, but I wonder whether if we all focused on it at once we could make it more painless. But this is just one suggestion, and there may well be better ones.

from Gowers

Search This Blog

Carry The Two